队列和栈一样，是一种操作受限的线性表数据结构，具有先进先出的特点。队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。队列支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取出一个元素。
一、顺序队列
顺序队列采用数组实现，由于数组初始化时需要一个容量，所以顺序队列声明是也需要提供一个队列的容量。除此之外，顺序队列维护了两个指针：front指向队列头部数据的前一个下标，rear指向队列尾部数据的下标。
数据存入时称为 入队enqueue()，包含两个步骤：
- 将尾指针后移：rear+1，当rear=front时表示队列为空；
- 若尾指针rear小于队列的最大下标maxSize-1，表示队列未满，则将数据存入数组中下标为rear的位置，否则无法插入数据。
数据取出时称为 出队dequeue()，也包含两个步骤：
- 将头指针后移：front+1，当rear=front时表示队列为空；
- 若队列不为空，取出数组中下标为front的数据。
图解
①队列初始化
②队空队满判断条件
③入队出队操作
代码实现
二、链式队列
链式队列采用链表实现，链式队列不需要指定容量，理论上只要内存足够，可以一直添加。链式队列同样需要维护两个指针：front指向队列的头部数据结点，rear指向队列的尾部数据结点。
入队 enqueue()：
- 如果队列为空：front==null，front和rear指针都指向新的数据结点
- 如果队列不为空：
- rear的next域指向新的数据结点
- rear指针后移
出队 dequeue()：
- 将front指针所指结点保存在临时变量，避免丢失
- 判断front的next域是否为空
- 如果是，说明该结点为最后一个结点，出队时将rear指针置空，front指针后移
- 如果不是，front指针后移
- 然后返回临时变量保存的数据值
图解
①链式队列初始化及判空条件
②链式队列入队出队操作
代码实现：
定义结点类型
链式队列实现
三、环形队列
上面实现的队列中，即使数据出队了，空出来的空间也是无法重复利用的，特别是顺序队列，初始化时就定义了队列容量，为了实现空间的重复利用，可以将上面的队列调整成环形队列。
思路分析：
- 为了解决这个问题，可以少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志
- front变量的含义进行调整，由指向队列头的前一个元素改为指向队列的第一个元素,front的初始值为0；
- rear变量的含义进行调整，由指向队列尾元素改为指向队列尾的后一个元素，rear的初始值为0；
- 当队列为空时：rear==front不变;
- 当队列满时，条件是(rear+1)%maxSize==front
- 当这样分析时，队列中有效的数据个数为：(rear+maxSize-front)%maxSize
图解：
我们通过一个特殊情况说明为什么判断队列满的条件是：(rear+1)%maxSize==front：
从上面的定义中，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志，如果我们直接定义队满条件是：rear+1==front，那么上图这种情况下，队列是满的，但是：rear=7，front=0，rear+1=8!=0；所以用rear+1的值对容量maxSize取余，让rear+1的值保证在0到maxSize-1之间；同理，在入队和出队移动rear和front指针时，也要对容量maxSize取余。
代码实现：
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/41076.html