大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

六、队列的实现

队列的定义及实现

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

附件


当前标题:六、队列的实现
本文网址:http://dzwzjz.com/article/piedgs.html
在线咨询
服务热线
服务热线:028-86922220
TOP