3.4 数据结构队列

01抽象数据类型队列的定义

1、和栈相反，队列是一种先进先出（FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。

2、在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。

3、双端队列：是限定插入和删除操作在表的两端进行的线性表。

02链队列-队列的链式表示和实现

1、用链表示的队列简称为链队列，一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。

2、链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。

3、一般情况下，删除队列头元素时仅需修改头结点中的指针，但当队列中最后一个元素被删除后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。

03循环队列-队列的顺序表示和实现

1、和顺序栈想类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。

2、在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

C语言 | 大写字母A转换为小写a​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/337365112