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