队列
1. 定义
队列是一种操作受限的线性表，对于它的所有插入都在表的一端进行，所有的删除（以至几乎所有的存取）都在表的另一端进行，且这些操作又都是按照先进先出（FIFO）的原则进行的。进行删除的一端称为队头（front），进行插入的一端称为队尾（rear）。没有元素的队列称为空队列（简称空队）。
队列就像生活中排队购物，新来的人只能加入队尾（假设不允许插队），购物结束后先离开的总是队头（假设无人中途离队）。也就是说，先加入队列的成员总是先离开队列，因此队列被称为先进先出（First In First Out）的线性表，简称为FIFO表。如图，在空队列中依次加入元素a1，a2，a3，a4，a5，出队次序仍然是a1，a2，a3，a4，a5 .
2. 基本操作
- 队列是受限的线性表，其基本操作包括
IsEmpty(): 判断队列是否为空；isFull()：判断队列是否为满；enqueue()：向队尾添加元素（入队）；dequeue()：删除队首元素（出队）；peek()：获取队首的元素值（存取）；
- 同普通线性表一样，队列也可以用顺序存储和链接存储两种方式来实现：
顺序队列
参考前文：线性表（八）队列：顺序队列及其基本操作（初始化、判空、判满、入队、出队、存取队首元素）
关于顺序队列，删除队头元素有两种方式：
- ⑴ 不要求队头元素必须存放在数组的第一个位置。每次删除队头元素，只需修改队头指针front所指的位置（即队头元素在数组中的下标），令front=front 1 . 该方式的优点是无须改变诸队列元素的地址，缺点是front值随着队头元素的删除而不断增加，整个队列向数组的后端位置移动，随着队尾元素的不断加入，必然出现数组后端没有可用空间的情况，而数组前端的大量空间却被闲置。
- ⑵ 要求队头元素必须存放在数组的第一个位置。每次删除队头元素，令所有元素都向前移动一个位置。该方式的优点是不浪费空间，缺点是所有元素的地址都必须改变，效率低下。
循环队列
为了克服上述缺点，可以假定数组是循环的，即采用环状模型来实现顺序队列。这种模型将队列在逻辑上置于一个圆环上，如图3.17所示，用整型变量front存放队头位置，每删除一个队头元素，就将front顺时针移动一个位置；整型变量rear存放新元素要插入的位置（下标），每插入一个元素，rear将顺时针移动一个位置；整型变量count存放队列中元素的个数，当count等于数组规模Size时，说明队列已满，当count等于0时，说明队列为空。
1. 头文件和常量
代码语言：javascript复制#include <stdio.h>
#define MAX_SIZE 100- 头文件
stdio.h用于输入输出操作 - 通过
#define指令定义了一个常量MAX_SIZE，它表示顺序队列中数组的最大容量为100。
2. 队列结构体
代码语言：javascript复制typedef struct {
int data[MAX_SIZE]; // 存储队列元素的数组
int front; // 队头指针
int rear; // 队尾指针
int count; // 队列规模
} CircularQueue;- 整型数组
data，用于存储队列元素； front和rear分别表示队头指针和队尾指针；count：队列中元素的个数。
3. 队列的初始化
代码语言：javascript复制void initQueue(CircularQueue *queue) {
queue->front = 0;
queue->rear = 0;
queue->count = 0;
} initQueue 函数：初始化队列，它将队头、队尾和元素个数都设置为0，表示队列为空。
4. 判断队列是否为空
代码语言：javascript复制bool isEmpty(CircularQueue *queue) {
// return queue->front == 0;
return queue->count == 0;
}通过检查队列中元素的个数来判断队列是否为空。
5. 判断队列是否已满
代码语言：javascript复制bool isFull(CircularQueue *queue) {
return queue->count == MAX_SIZE;
} 通过比较队列中元素的个数和最大容量 MAX_SIZE 来判断队列是否已满。
6. 入队
代码语言：javascript复制void enqueue(CircularQueue *queue, int item) {
if (isFull(queue)) {
printf("Queue is full. Cannot enqueue.n");
return;
}
queue->data[queue->rear] = item;
queue->rear = (queue->rear 1) % MAX_SIZE;
queue->count ;
}- 判断队列是否已满
- 如果已满则打印错误信息并返回；
- 否则，将元素添加到队尾，并更新队尾指针和元素个数。
7. 出队
代码语言：javascript复制int dequeue(CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue.n");
return -1;
}
int item = queue->data[queue->front];
queue->front = (queue->front 1) % MAX_SIZE;
queue->count--;
return item;
}- 判断队列是否为空
- 如果为空则打印错误信息并返回 -1；
- 否则，将队头元素返回，并更新队头指针和元素个数。
8. 存取队首元素
代码语言：javascript复制int peek(CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot peek.n");
return -1;
}
return queue->data[queue->front];
} peek 函数用于查看队头元素，但不移除它。如果队列为空，则打印提示信息并返回 -1。
9. 获取队列中元素个数
代码语言：javascript复制int size(CircularQueue *queue) {
return queue->count;
}10. 打印队列中的元素
代码语言：javascript复制void display(CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty.n");
return;
}
printf("Queue elements: ");
int i = queue->front;
int count = 0;
while (count < queue->count) {
printf("%d ", queue->data[i]);
i = (i 1) % MAX_SIZE;
count ;
}
printf("n");
}- 如果队列为空，则打印提示信息；
- 否则，使用循环遍历队列中的元素并逐个打印。
9. 主函数
代码语言：javascript复制int main() {
CircularQueue queue;
initQueue(&queue);
enqueue(&queue, 1);
enqueue(&queue, 2);
enqueue(&queue, 3);
display(&queue);
printf("Queue size: %dn", size(&queue));
printf("Front element: %dn", peek(&queue));
dequeue(&queue);
printf("Dequeued element.n");
display(&queue);
printf("Queue size: %dn", size(&queue));
printf("Front element: %dn", peek(&queue));
return 0;
}
10. 代码整合
代码语言：javascript复制#include <stdio.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE]; // 存储队列元素的数组
int front; // 队头指针
int rear; // 队尾指针
int count; // 队列规模
} CircularQueue;
void initQueue(CircularQueue *queue) {
queue->front = 0;
queue->rear = 0;
queue->count = 0;
}
bool isEmpty(CircularQueue *queue) {
// return queue->front == 0;
return queue->count == 0;
}
bool isFull(CircularQueue *queue) {
return queue->count == MAX_SIZE;
}
void enqueue(CircularQueue *queue, int item) {
if (isFull(queue)) {
printf("Queue is full. Cannot enqueue.n");
return;
}
queue->data[queue->rear] = item;
queue->rear = (queue->rear 1) % MAX_SIZE;
queue->count ;
}
int dequeue(CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue.n");
return -1;
}
int item = queue->data[queue->front];
queue->front = (queue->front 1) % MAX_SIZE;
queue->count--;
return item;
}
int peek(CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Cannot peek.n");
return -1;
}
return queue->data[queue->front];
}
int size(CircularQueue *queue) {
return queue->count;
}
void display(CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty.n");
return;
}
printf("Queue elements: ");
int i = queue->front;
int count = 0;
while (count < queue->count) {
printf("%d ", queue->data[i]);
i = (i 1) % MAX_SIZE;
count ;
}
printf("n");
}
int main() {
CircularQueue queue;
initQueue(&queue);
enqueue(&queue, 1);
enqueue(&queue, 2);
enqueue(&queue, 3);
display(&queue);
printf("Queue size: %dn", size(&queue));
printf("Front element: %dn", peek(&queue));
dequeue(&queue);
printf("Dequeued element.n");
display(&queue);
printf("Queue size: %dn", size(&queue));
printf("Front element: %dn", peek(&queue));
return 0;
}
