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