文章目录
- 队列
- 1. 定义
- 2. 基本操作
- 顺序队列
- 循环队列
- 1. 头文件和常量
- 2. 队列结构体
- 3. 队列的初始化
- 4. 判断队列是否为空
- 5. 判断队列是否已满
- 6. 入队
- 7. 出队
- 8. 存取队首元素
- 9. 获取队列中元素个数
- 10. 打印队列中的元素
- 9. 主函数
- 10. 代码整合
堆栈Stack 和 队列Queue是两种非常重要的数据结构,两者都是特殊的线性表:
- 对于堆栈,所有的插入和删除(以至几乎所有的存取)都是在表的同一端进行;
- 对于队列,所有的插入都是在表的一端进行,所有的删除(以至几乎所有的存取)都是在表的另一端进行。
队列
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. 头文件和常量
#include <stdio.h>
#define MAX_SIZE 100
-
头文件
stdio.h
用于输入输出操作 -
通过
#define
指令定义了一个常量MAX_SIZE
,它表示顺序队列中数组的最大容量为100。
2. 队列结构体
typedef struct {int data[MAX_SIZE]; // 存储队列元素的数组int front; // 队头指针int rear; // 队尾指针int count; // 队列规模
} CircularQueue;
- 整型数组
data
,用于存储队列元素; front
和rear
分别表示队头指针和队尾指针;count
:队列中元素的个数。
3. 队列的初始化
void initQueue(CircularQueue *queue) {queue->front = 0;queue->rear = 0;queue->count = 0;
}
initQueue
函数:初始化队列,它将队头、队尾和元素个数都设置为0,表示队列为空。
4. 判断队列是否为空
bool isEmpty(CircularQueue *queue) {
// return queue->front == 0;return queue->count == 0;
}
通过检查队列中元素的个数来判断队列是否为空。
5. 判断队列是否已满
bool isFull(CircularQueue *queue) {return queue->count == MAX_SIZE;
}
通过比较队列中元素的个数和最大容量 MAX_SIZE
来判断队列是否已满。
6. 入队
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. 出队
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. 存取队首元素
int peek(CircularQueue *queue) {if (isEmpty(queue)) {printf("Queue is empty. Cannot peek.\n");return -1;}return queue->data[queue->front];
}
peek
函数用于查看队头元素,但不移除它。如果队列为空,则打印提示信息并返回 -1。
9. 获取队列中元素个数
int size(CircularQueue *queue) {return queue->count;
}
10. 打印队列中的元素
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. 主函数
int main() {CircularQueue queue;initQueue(&queue);enqueue(&queue, 1);enqueue(&queue, 2);enqueue(&queue, 3);display(&queue);printf("Queue size: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));dequeue(&queue);printf("Dequeued element.\n");display(&queue);printf("Queue size: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));return 0;
}
10. 代码整合
#include <stdio.h>#define MAX_SIZE 100typedef 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: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));dequeue(&queue);printf("Dequeued element.\n");display(&queue);printf("Queue size: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));return 0;
}