六、队列的实现

队列的定义及实现

 队列的定义
 队列是一种特殊的线性表
 队列仅在线性表的两端进行操作
  队头(Front)：取出数据元素的一端
  队尾(Rear)：插入数据元素的一端
队列的性质
 先进先出(FIFO,First In First Out)

队列的一些常用操作
 创建队列
 销毁队列
 清空队列
 进队列
 出队列
 获取队头元素
 获取队列的长度
队列的顺序存储实现

实现代码：附件中SeqQue文件夹
队列的链式存储实现

实现代码：附件中ListQue文件夹

专注于为中小企业提供网站建设、网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业西安免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了上千多家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

队列的优化实现

 顺序队列
 线性表的第一个元素作为队头
 线性表的最后一个元素作为队尾
入队的新元素是在线性表的最后,时间复杂度为O(1)
出队时需要将后续的所有元素向前移动，时间复杂度O(n)
问题：如何将出队操作的时间复杂度降低到O(1)?
顺序队列的优化方案
定义front使其始终代表队头的下标
 出队时将队头元素返回，且front++
定义rear使其始终代表队尾下一个元素的下标
 入队时将新元素插入，且rear++
没有必要只将下标为0的位置定义为队头

顺序队列的关键状态
初始状态：length == 0, front == 0, rear == 0;
空队列状态：length == 0, front == rear;
满队列状态：length == capacity, front == rear;
循环使用队列中的空间
入队：rear = (rear + 1) % capacity;
出队：front = (front + 1) % capacity;
实现代码：附件中SeqQue_2文件夹
链式队列的瓶颈
链式队列
 线性表的第一个元素作为队头
 线性表的最后一个元素作为队尾
入队的新元素是在线性表的最后，时间复杂度为O(n)
出队的元素即链表的第一个元素，时间复杂度O(1)
问题：如何将入队操作的时间复杂度降低到O(1)?
链式队列的优化方案
定义rear指针始终指向链表中的最有一个元素
 入队时将新元素通过rear插入队尾，且将rear指向新元素

链式队列的关键状态
空队列状态：front == NULL, rear == NULL;
关键操作
入队：
 rear->next = node;
 rear = node;
 node->next = NULL;
出队：
 front = front->next;
实现代码：附件中ListQue_2文件夹

队列的特别实现

栈与队列：用栈实现队列

实现思路
准备两个栈用于实现队列：inStack和outStack
当有新元素入队时：将其压入inStack中
当需要出队时：
 当outStack为空时：
  1. 将inStack中的元素逐一弹出并压入outStack中
  2. 将outStack的栈顶元素弹出
 当outStack不为空时：
  – 直接将outStack的栈顶元素弹出
算法框架

实现代码：附件中NewQue文件夹

附件