队列的定义及实现

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

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

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

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

创新互联建站主营镇远网站建设的网络公司,主营网站建设方案,手机APP定制开发,镇远h5小程序开发搭建,镇远网站营销推广欢迎镇远等地区企业咨询

队列的优化实现

顺序队列
线性表的第一个元素作为队头
线性表的最后一个元素作为队尾
入队的新元素是在线性表的最后,时间复杂度为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文件夹

附件

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网站栏目：六、队列的实现-创新互联
文章源于：http://njwzjz.com/article/phocj.html