数据结构的概念大合集04（队列）

1、队列

1.1 队列的定义

• 队列限制为仅允许在表的一旦进行插入操作，而在表的另一端进行删除操作。
• 将进行插入的一端称为队尾，进行删除的一端称为队头或对首。
• 将插入新元素称为入队或进对。
• 将删除元素称为出队或离队。

队列的特点是：先进队的先出队，即先进先出表（first in first out，FIFO）

1.2队列的顺序存储

1.2.1 顺序队

采用顺序存储的列表称为顺序队

1.2.2 顺序队的基本运算的基本思想

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 双端队列

指的是两端都可以进行进队和出队的操作的队列

进队时，从前端进的元素排列在从后端进的元素的前面；
出队时，无论是从前端出还是从后端出，都是先出的元素排列在后出的元素前面。

注：
本文将主要探讨队列的概念，其中提及的各个函数操作已经发布，欢迎朋友们继续观看。

本篇文章的相关算法
数据结构大合集04——队的相关函数运算算法

上一篇文章
数据结构的概念大合集03（栈）

下一篇文章
数据结构的概念大合集05（串）