六、队列的实现

队列的定义及实现

 队列的定义
  队列是一种特殊的线性表
  队列仅在线性表的两端进行操作
   队头(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文件夹

附件