数据结构-队列

一、概念

1、队列的定义

队列是仅限在一端进行插入，另一端进行删除的线性表。

队列又被称为先进先出（First In First Out） 的线性表，简称 FIFO 。

2、队首

允许进行元素删除的一端称为队首

3、队尾

允许进行元素插入的一端称为 队尾

二、接口

1、可写接口

（1）数据入队

队列的插入操作，叫做 入队。它是将 数据元素 从 队尾 进行插入的过程

（2）数据出队

队列的删除操作，叫做 出队。它是将 队首 元素进行删除的过程

（3）清空队列

队列的清空操作，就是一直 出队，直到队列为空的过程，当 队首 和 队尾 重合时，就代表队尾为空了

2、只读接口

（1）获取队首数据

对于一个队列来说只能获取 队首 数据，一般不支持获取 其它数据。

（2）获取队列元素个数

 队列元素个数一般用一个额外变量存储，入队 时加一，出队 时减一

（3）队列的判空

当队列元素个数为零时，就是一个 空队，空队 不允许 出队 操作

三、队列的顺序表实现

1、结构体

struct Queue {             // 队列结构体

    DataType data[maxn];   // 队列存储方式，数组

    int head, tail;        // 队首，队尾指针，head == tail代表空队

};

2、入队

void QueueEnqueue(struct Queue *que, DataType dt) {  

    que->data[ que->tail ] = dt;                     // 将传参的元素入队

    que->tail = que->tail + 1;                       // 队尾指针加一

}

可以写成下面这样

void QueueEnqueue(struct Queue *que, DataType dt) {

    que->data[ que->tail++ ] = dt;

}

3、出队

void QueueDequeue(struct Queue* que) {

    ++que->head;//队首指针加一

}

4、清空队列

清空队列的操作只需要将 队首指针 和 队尾指针 都归零即可

void QueueClear(struct Queue* que) {

    que->head = que->tail = 0;

}

5、只读接口

DataType QueueGetFront(struct Queue* que) {

    return que->data[ que->head ];      // 得到队首元素

}

int QueueGetSize(struct Queue* que) {

    return que->tail - que->head;       // 队列的元素个数

}

int QueueIsEmpty(struct Queue* que) {

    return !QueueGetSize(que);          // 判空

}

6、队列的顺序表实现的源码

#define DataType int

#define maxn 100005


struct Queue {

    DataType data[maxn];

    int head, tail;

};


void QueueClear(struct Queue* que) {

    que->head = que->tail = 0;

}

void QueueEnqueue(struct Queue *que, DataType dt) {

    que->data[ que->tail++ ] = dt;

}

void QueueDequeue(struct Queue* que) {

    ++que->head;

}


DataType QueueGetFront(struct Queue* que) {

    return que->data[ que->head ];

}

int QueueGetSize(struct Queue* que) {

    return que->tail - que->head;

}

int QueueIsEmpty(struct Queue* que) {

    return !QueueGetSize(que);

}

四、队列的链表实现

1、结构体

typedef int DataType;               

struct QueueNode;                  

struct QueueNode {                  // 结点

    DataType data;

    struct QueueNode *next;

};


struct Queue {

    struct QueueNode *head, *tail;  // 队首、队尾指针

    int size;                       // 队列元素个数

};

2、入队

链表入队类似尾插法

void QueueEnqueue(struct Queue *que, DataType dt) {

    struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) );            
    insertNode->data = dt;                  // 给入队的元素赋值

    insertNode->next = NULL;

    if(que->tail) {                         // 不为空

        que->tail->next = insertNode;

        que->tail = insertNode;

    }else {

        que->head = que->tail = insertNode; // 为空直接首队尾指针指向新入队的元素

    }

    ++que->size;                            // 元素个数加一

}

3、出队

出队 操作，由于链表头结点就是 队首，其实就是删除这个链表的头结点的过程

void QueueDequeue(struct Queue* que) {

    struct QueueNode *temp = que->head;  // 将队首保存到temp

    que->head = temp->next;              // 队首指向temp的下一个结点，也就是队首的下一个结点

    free(temp);                          // 释放temp

    --que->size;                         // 长度减一

    if(que->size == 0) {                 // 如果长度为0，队尾置空

        que->tail = NULL;

    }  
}

4、清空队列

对于链表而言，清空队列 的操作需要删除每个链表结点

void QueueClear(struct Queue* que) {

    while(!QueueIsEmpty(que)) {     // 队列不为空

        QueueDequeue(que);          // 出队

    }

}

5、只读接口

DataType QueueGetFront(struct Queue* que) {

    return que->head->data;              // 得到队首元素

}

int QueueGetSize(struct Queue* que) {

    return que->size;                    // 队列元素个数

}

int QueueIsEmpty(struct Queue* que) {

    return !QueueGetSize(que);           // 是否为空

}

6、队列的链表实现源码

typedef int DataType;


struct QueueNode;

struct QueueNode {

    DataType data;

    struct QueueNode *next;

};


struct Queue {

    struct QueueNode *head, *tail;

    int size;

};


void QueueEnqueue(struct Queue *que, DataType dt) {

    struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) );

    insertNode->data = dt;

    insertNode->next = NULL;

    if(que->tail) {

        que->tail->next = insertNode;

        que->tail = insertNode;

    }else {

        que->head = que->tail = insertNode;

    }

    ++que->size;

}


void QueueDequeue(struct Queue* que) {

    struct QueueNode *temp = que->head;

    que->head = temp->next;

    free(temp);

    --que->size;

    if(que->size == 0) {

        que->tail = NULL;

    }  
}


DataType QueueGetFront(struct Queue* que) {

    return que->head->data;

}

int QueueGetSize(struct Queue* que) {

    return que->size;

}

int QueueIsEmpty(struct Queue* que) {

    return !QueueGetSize(que);

}

void QueueClear(struct Queue* que) {

    que->head = que->tail = NULL;

    que->size = 0;

}

五、优缺点

1、顺序表

入队 和 出队 的常数时间复杂度低，且 清空队列 操作相比 链表实现 能做到O(1),

不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容

2、链表

入队 和 出队 的常数时间复杂度略高，主要是每插入一个队列元素都需要申请空间，每删除一个队列元素都需要释放空间，且 清空队列 操作是 O(n)，直接将 队首指针 和 队尾指针 置空会导致内存泄漏

好处就是：不需要预先分配空间，且在内存允许范围内，可以一直 入队

六、队列的入门

1、滑动窗口

LeetCode933最近的请求次数

2、广度优先搜索

LeetCode542.01矩阵

LeetCode994腐烂的橘子

七、队列的进阶

1、辅助队列

LeetCode225用队列实现栈

LeetCode 1696. 跳跃游戏 VI

LeetCode 1438. 绝对差不超过限制的最长连续子数组

LeetCode 239. 滑动窗口最大值