队列ADT

队列 Queue ADT

1. 前提条件

队列是一种线性表。
它的特点是：先进先出 FIFO

也就是：First In First Out

先进入队列的元素，先出队。

例如：

入队顺序：1 2 3

出队顺序：1 2 3

队列通常支持 EnQueue 入队、DeQueue 出队、GetFront 取队头、IsEmpty 判空等操作；队列一般可以用数组或链表实现。

2. 核心概念

队列只允许：

队尾 rear 插入
队头 front 删除

图示：

front rear
↓ ↓
1 -> 2 -> 3 -> 4

操作规律：

入队：从 rear 进去
出队：从 front 出来

3. ADT 操作定义

队列常见 ADT 操作：

InitQueue 初始化队列
IsEmpty 判断队列是否为空
EnQueue 入队
DeQueue 出队
GetFront 获取队头元素
DestroyQueue 销毁队列

一、顺序队列

1. 前提条件
   顺序队列就是：用数组实现队列

需要两个下标：

front：队头位置
rear：队尾后一个位置
2. 存储结构

#define MAXSIZE 100

struct Queue {
int data[MAXSIZE];
int front;
int rear;
};

这里：

data：存放元素
front：队头下标
rear：队尾后一个位置
3. 初始化
void InitQueue(struct Queue* q) {
q->front = 0;
q->rear = 0;
}

此时：

front == rear

表示队列为空。

4. 判空
   int IsEmpty(struct Queue* q) {
   return q->front == q->rear;
   }

5. 入队
   int EnQueue(struct Queue* q, int x) {
   if (q->rear >= MAXSIZE) {
   return 0;
   }

   q->data[q->rear] = x;
   q->rear++;

   return 1;
   }

含义：
先把元素放到 rear 位置；
再让 rear 后移。

6. 出队
   int DeQueue(struct Queue* q, int* x) {
   if (IsEmpty(q)) {
   return 0;
   }

   *x = q->data[q->front];
   q->front++;

   return 1;
   }

含义：

先取 front 位置元素；
再让 front 后移。

7. 取队头
   int GetFront(struct Queue* q, int* x) {
   if (IsEmpty(q)) {
   return 0;
   }

   *x = q->data[q->front];
   return 1;
   }

注意：

GetFront 只读取，不删除。
DeQueue 读取并删除。

8. 顺序队列的问题

普通数组队列会有一个问题：假溢出

例如数组长度是 5：

下标：0 1 2 3 4
元素：1 2 3 4 5

出队两个：

下标：0 1 2 3 4
元素：_ _ 3 4 5
front = 2
rear = 5

虽然前面有空位，但：

rear == MAXSIZE

不能继续入队。

这就是顺序队列浪费空间的问题。

所以更常用的是：循环队列

二、循环队列

1. 前提条件：循环队列用数组实现，但把数组看成一个环。

当 rear 到达数组末尾后，可以回到下标 0。

循环队列可以避免普通顺序队列前面出队后留下的空位不能继续使用的问题；数组循环队列通常可以让入队和出队都保持 O(1)。

2. 存储结构
   #define MAXSIZE 100

struct Queue {
int data[MAXSIZE];
int front;
int rear;
};

仍然是：

front：队头
rear：队尾后一个位置
3. 循环移动

普通后移：

q->rear++;

循环后移：

q->rear = (q->rear + 1) % MAXSIZE;

同理：

q->front = (q->front + 1) % MAXSIZE;
4. 初始化
void InitQueue(struct Queue* q) {
q->front = 0;
q->rear = 0;
}
5. 判空
int IsEmpty(struct Queue* q) {
return q->front == q->rear;
}
6. 判满

循环队列通常故意空出一个位置。

队满条件：

int IsFull(struct Queue* q) {
return (q->rear + 1) % MAXSIZE == q->front;
}

为什么要空一个位置？

因为如果不空位置：

front == rear

既可能表示空，也可能表示满。

所以用：

空一个位置

来区分空和满。

7. 入队
   int EnQueue(struct Queue* q, int x) {
   if (IsFull(q)) {
   return 0;
   }

   q->data[q->rear] = x;
   q->rear = (q->rear + 1) % MAXSIZE;
   //这里把rear++改成了循环到下一位
   return 1;
   }

8. 出队
   int DeQueue(struct Queue* q, int* x) {
   if (IsEmpty(q)) {
   return 0;
   }

   *x = q->data[q->front];
   q->front = (q->front + 1) % MAXSIZE;

   return 1;
   }

9. 取队头
   int GetFront(struct Queue* q, int* x) {
   if (IsEmpty(q)) {
   return 0;
   }

   *x = q->data[q->front];
   return 1;
   }

10. 循环队列核心
    队空：
    front == rear

队满：
(rear + 1) % MAXSIZE == front

入队：
data[rear] = x
rear = (rear + 1) % MAXSIZE

出队：
x = data[front]
front = (front + 1) % MAXSIZE
三、链式队列

1. 前提条件

链式队列就是：用链表实现队列

需要两个指针：

front：指向队头结点
rear：指向队尾结点

队列可以用链表实现，链式队列通常更适合元素数量不固定的情况，因为它可以动态申请节点。

2. 存储结构

struct Node {
int data;
struct Node* next;
};

struct LinkQueue {
struct Node* front;
struct Node* rear;
};

3. 初始化
   void InitQueue(struct LinkQueue* q) {
   q->front = NULL;
   q->rear = NULL;
   }

空队列：

front = NULL
rear = NULL

4. 判空
   int IsEmpty(struct LinkQueue* q) {
   return q->front == NULL;
   }

5. 入队

链式队列入队就是：尾插法

代码：

#include <stdlib.h>

int EnQueue(struct LinkQueue* q, int x) {
struct Node* node = malloc(sizeof(struct Node));

if (node == NULL) {
    return 0;
}

node->data = x;
node->next = NULL;

//这里就是尾插法正常链表
//下面就是判断先让两者是否正常初始化，之后都指向node
if (q->front == NULL) {
q->front = node;
q->rear = node;
} else {
q->rear->next = node;
q->rear = node;
}
//这里是让rear指向的node的next连到新的node上去，然后移动新的node给rear
return 1;
}
6. 出队

链式队列出队就是：删除头结点

代码：

int DeQueue(struct LinkQueue* q, int* x) {
if (IsEmpty(q)) {
return 0;
}

struct Node* p = q->front;

*x = p->data;

q->front = p->next;

//就是把q的front位置data的值赋给x之后front再移动到下一个位置
if (q->front == NULL) {
q->rear = NULL;
}

free(p);

return 1;

}

注意：如果删完之后队列为空，
rear 也要置 NULL。

7. 取队头
   int GetFront(struct LinkQueue* q, int* x) {
   if (IsEmpty(q)) {
   return 0;
   }

   *x = q->front->data;
   return 1;
   }

四、循环队列完整模板

#include <stdlib.h>

#define MAXSIZE 100

struct Queue {
int data[MAXSIZE];
int front;
int rear;
};

void InitQueue(struct Queue* q) {
q->front = 0;
q->rear = 0;
}

int IsEmpty(struct Queue* q) {
return q->front == q->rear;
}

int IsFull(struct Queue* q) {
return (q->rear + 1) % MAXSIZE == q->front;
}

int EnQueue(struct Queue* q, int x) {
if (IsFull(q)) {
return 0;
}

q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAXSIZE;

return 1;

}

int DeQueue(struct Queue* q, int* x) {
if (IsEmpty(q)) {
return 0;
}

*x = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;

return 1;

}

int GetFront(struct Queue* q, int* x) {
if (IsEmpty(q)) {
return 0;
}

*x = q->data[q->front];
return 1;

}

五、链式队列完整模板
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct LinkQueue {
struct Node* front;
struct Node* rear;
};

void InitQueue(struct LinkQueue* q) {
q->front = NULL;
q->rear = NULL;
}

int IsEmpty(struct LinkQueue* q) {
return q->front == NULL;
}

int EnQueue(struct LinkQueue* q, int x) {
struct Node* node = malloc(sizeof(struct Node));

if (node == NULL) {
    return 0;
}

node->data = x;
node->next = NULL;

if (q->front == NULL) {
    q->front = node;
    q->rear = node;
} else {
    q->rear->next = node;
    q->rear = node;
}

return 1;

}

int DeQueue(struct LinkQueue* q, int* x) {
if (IsEmpty(q)) {
return 0;
}

struct Node* p = q->front;

*x = p->data;

q->front = p->next;

if (q->front == NULL) {
    q->rear = NULL;
}

free(p);

return 1;

}

int GetFront(struct LinkQueue* q, int* x) {
if (IsEmpty(q)) {
return 0;
}

*x = q->front->data;
return 1;

}

六、易错点

1. front 和 rear 的含义要固定

front 指向队头元素
rear 指向队尾后一个位置

这个定义适合顺序循环队列。

2. 循环队列判满不是 rear == MAXSIZE

错误：q->rear == MAXSIZE

正确：(q->rear + 1) % MAXSIZE == q->front

3. 链式队列空队列时 front 和 rear 都要变 NULL

出队时，如果删的是最后一个节点：

if (q->front == NULL) {
q->rear = NULL;
}

否则 rear 会变成野指针。

4. 链式队列入队要区分空队列和非空队列

空队列：

q->front = node;
q->rear = node;

非空队列：

q->rear->next = node;
q->rear = node;

5. GetFront 不移动 front
   GetFront 只是看队头；
   DeQueue 才是真正删除队头。

常见应用：
BFS

二叉树层序遍历

图的广度优先搜索

拓扑排序

操作系统任务调度

队列是“从队尾进，从队头出”的先进先出结构；数组实现要注意循环队列，链表实现要注意 front 和 rear 的维护。