概念大合集04
- 1、队列
- 1.1 队列的定义
- 1.2队列的顺序存储
- 1.2.1 顺序队
- 1.2.2 顺序队的基本运算的基本思想
- 1.2.3 顺序队的4要素的基本思想
- 1.3 环形队列
- 1.3.1 环形队列的定义
- 1.3.1 环形队列的实现
- 1.4 队列的链式存储
- 1.4.1 链队
- 1.4.2 链队的实现方式
- 1.4.3 链队的4要素的基本思想
- 1.5 双端队列
1、队列
1.1 队列的定义
- 队列限制为仅允许在表的一旦进行插入操作，而在表的另一端进行删除操作。
- 将进行插入的一端称为队尾，进行删除的一端称为队头或对首。
- 将插入新元素称为入队或进对。
- 将删除元素称为出队或离队。
队列的特点是：先进队的先出队，即先进先出表（first in first out，FIFO）
1.2队列的顺序存储
1.2.1 顺序队
采用顺序存储的列表称为顺序队
1.2.2 顺序队的基本运算的基本思想
| 函数名 | 函数作用 |
|---|---|
| InitQueue(&q) | 初识化队列，构造一个空队列 |
| DestroyQueue(&q) | 销毁队列，释放为队列q分配的内存空间 |
| QueueEmpty(q) | 判断队列是否为空表，若L为空队列，则返回true，否则返回false |
| enQueue(&q,e) | 进队列，将元素e插入作为对尾元素。 |
| deQueue(&q,e) | 出队列，从队列q中出队一个元素，并将其赋值给e |
1.2.3 顺序队的4要素的基本思想
- 空队：q -> front == q -> rear;
- 队满：q -> rear == MaxSize - 1;
- 进队：先将rear增1，然后将元素e放在data数组的rear位置。即data[++rear] = e;
- 出队：先将front增1，然后取出data数组中front位置的元素。即e = data[++front];
1.3 环形队列
1.3.1 环形队列的定义
环形队是顺序队的衍生。
衍生原因，由上面的基本思想可知，队满的情况是q -> rear == MaxSize - 1，而队列的出队，是从队头出队，当出队两次后，队列空出两个元素，但是这时候，仍旧是q -> rear == MaxSize - 1，所以会出现假队队满的情况。为避免这种情况，于是就衍生出环形队列，这种特殊的队列。
所以将顺序队的前后端连接起来就形成了环形队列
1.3.1 环形队列的实现
环形队列相连后，当队尾指针rear = MaxSize - 1后，再前进一个位置到0，让 rear == 0，即从队尾变成队头，为此，可采用求余（%）运算来实现：
队尾指针rear从队尾指向队头，形成循环：rear = (rear + 1)%MaxSize
同理：队头指针front循环增1：front = (front + 1)%MaxSize
1.4 队列的链式存储
1.4.1 链队
采用链式存储结构的队列
采用单链表的方式实现链队
1.4.2 链队的实现方式
链队的实现方式与链表不同，链队的头结点，存放两个指针，一个指向队首结点，一个指向队尾结点，而里面的数据结点还是与单链表相同，存在一个数据域和一个指针域
1.4.3 链队的4要素的基本思想
- 队空：q->rear == NULL || q->front == NULL;
- 队满：不考虑
- 进队：新建一个结点存放元素，将其作为尾结点插入
- 出队：取出队首结点的data值，并将其删除
1.5 双端队列
指的是两端都可以进行进队和出队的操作的队列
进队时，从前端进的元素排列在从后端进的元素的前面；
出队时，无论是从前端出还是从后端出，都是先出的元素排列在后出的元素前面。
注：
本文将主要探讨队列的概念，其中提及的各个函数操作将在后续的文章中详细展示，敬请读者期待。
上一篇文章
数据结构的概念大合集03（栈）
下一篇文章
数据结构的概念大合集05（串）
