队列
特点
- 只允许在表的一端插入，而在另一端删除
- 允许插入的一端被称为队尾（rear），允许删除的一端被称为队头（front）
- 队列遵循先进先出（FIFO）的原则
顺序表实现
建表
1
2
3
4
5
6
| typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int front;
int rear;
}Queue;
|
初始化
1
2
3
4
| void initQueue(Queue *Q){
Q->front = 0;
Q->rear = 0;
}
|
判空
判断首尾相遇即为空（并非为0）
1
2
3
4
5
6
7
8
9
10
|
int isEmpty(Queue *Q){
if (Q->front == Q->rear){
printf("Empty");
return 1;
}
else {
return 0;
}
}
|
出队
1
2
3
4
5
6
7
8
9
10
11
|
ElemType dequeue(Queue *Q){
if (isEmpty(Q)){
printf("Empty");
return 0;
}
ElemType e = Q->data[Q->front];
Q->front++;
return e;
}
|
入队
队列不满时才能入队，但有一种特殊情况：
此时队尾在最后，但队头在中间，意味着已经有数据出队，此时队列里仍有位置
这时我们需要将数据移到队头，使队尾向前以便插入元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
int queueFull(Queue *Q){
if (Q->front >0){
int step = Q->front;
for (int i = Q->front; i<=Q->rear; i++){
Q->data[i-step] = Q->data[i];
}
Q->front = 0;
Q->rear = Q->rear - step;
return 1;
}
else {
return 0;
}
}
int enqueue(Queue *Q, ElemType e){
if (Q->rear >=MAXSIZE){
if (!queueFull(Q)){
return 0;
}
}
Q->data[Q->rear] = e;
Q->rear++;
return 1;
}
|
注意，该方法时间复杂度较大，对于大量数据可能效率会很低
获取队头元素
1
2
3
4
5
6
7
8
9
|
int getHead(Queue *Q, ElemType *e){
if (isEmpty(Q)){
printf("Empty");
return 0;
}
*e = Q->data[Q->front];
return 1;
}
|
动态分配内存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| typedef int ElemType;
typedef struct {
ElemType *data;
int front;
int rear;
}Queue;
Queue* initQueue(Queue *Q){
Queue *q = (Queue*)malloc(sizeof(Queue));
q->data = (ElemType)malloc(sizeof(ElemType)*MAXSIZE);
Q->front = 0;
Q->rear = 0;
return q;
}
|
循环队列
循环队列可以避免整体移动位置的情况
即让front指向队头的前一个元素，rear指向队尾元素
入队
1
2
3
4
5
6
7
8
9
10
|
int enqueue(Queue *Q, ElemType e){
if ((Q->rear+1)%MAXSIZE == Q->front){
printf("Full");
return 0;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return 1;
}
|
取余保证在0到MAXSIZE-1的范围内循环下标
填不满的循环队列
有这么一种情况：
在上次入队后，rear+1，队尾到达0位置
此时若再进行入队操作，首先判断(Q->rear+1)%MAXSIZE，结果为1，此时正好满足rear==front意为堆满
但实际上还留有一个位置，用于判断堆满（与队空区分），若不留空则队满与队空的判断条件一样，无法判断
计算元素个数
- rear>front
此时元素个数=rear-front
- rear>front
分两块计算：0到rear与front到maxsize
即元素个数=rear+1+MAXSIZE-front-1=rear-front+MAXSIZE
综上，计算公式可以写作(rear-front+MAXSIZE)%MAXSIZE
另两种循环队列
此时front指向当前队头元素，rear指向队尾元素的后一个元素
队空：front==rear
队满：front=(rear+1)%MAXSIZE，也要空出一个位置
元素个数：与上一种一样
此时front指向队头元素，rear指向队尾元素
队空：front=(rear+1)%MAXSIZE
入队情况有两种：
第一种是先入队再判满
可以发现当rear==front时，队中有一个元素
为了留一个空位判断队空队满，所以当front==(rear+2)%MAXSIZE时有队满
元素个数：
rear>front
此时元素个数=rear-front+1
rear<front
分两块讨论，0到rear与front到maxsize
即元素个数=rear+1+MAXSIZE-front
综上，元素个数=(rear-front+1+MAXSIZE)%MAXSIZE
链表实现
构建队列
1
2
3
4
5
6
7
8
9
10
11
| typedef int ElemType;
typedef struct QueueNode{
ElemType data;
struct QueueNode *next;
}QueueNode;
typedef struct Queue
{
QueueNode *front;
QueueNode *rear;
}Queue;
|
这里多定义了一个结构体Queue，记录队头与队尾指针，而QueueNode为存储数据的链表
初始化
1
2
3
4
5
6
7
8
9
10
|
Queue* initQueue(){
Queue* q = (Queue*)malloc(sizeof(Queue));
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
node->data = 0;
node->next = NULL;
q->front = node;
q->rear = node;
return q;
}
|
入队
使用尾插法，此时认为队头为首节点，队尾为尾节点
创建新节点
让头节点的next指向该节点
尾指针后移一位
1
2
3
4
5
6
7
8
|
void enqueue(Queue *q, ElemType e){
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
node->data = e;
node->next = NULL;
q->rear->next = node;
q->rear = node;
}
|
出队
1
2
3
4
5
6
7
8
9
10
|
void dequeue(Queue *q, ElemType *e){
QueueNode* node = q->front->next;
*e = node->data;
q->front->next = node->next;
if (q->rear == node){
q->rear == q->front;
}
free(node);
}
|
单调队列
假设有一个数组(如[5,2,6,3,7,2,5,3])，使用滑动窗口，通过对l++,
r++实现让数字进入进出窗口
单调队列可以实现在滑动窗口每一时刻获得窗口中的
最大最小值，以低成本
单调队列通过双端队列实现，假设要求最大值，则双端队列从头到尾依次是从大到小，存储的是元素下标
右侧拓展：
队列为空时，第一个元素的下标进入(0->5)
若下一个元素进入满足严格从大到小，则进入，否则将最尾端元素弹出，直到满足从大到小
左侧收缩：
滑动窗口滑动，则不在指定范围内的下标从队头弹出
由此可以发现，每时最大值应为队头下标对应元素
How？
单调队列维持了每次最值的可能性
满足严格从大到小的顺序的队列保证了在前一个元素从队头弹出的情况下，下一个元素成为最大值
由于窗口不回退，当更大的数进入时，前面比它小的数便没有机会成为某时刻的最大值了，故可以弹出
时间复杂度：最坏
