数据结构与算法--队列

提要

1. 队列的定义
2. 队列的抽象数据类型
3. 队列的链式存储结构与基本运算的实现
4. 队列的顺序存储结构与基本运算的实现

队列的定义

• 队列是一种受限的线性表，只能在一端插入，在另一端删除
• 队尾（rear）：允许插入的一端
• 队头（front）：允许删除的一端
• 入队（enqueue）：在队尾进行的插入操作
• 出队（dequeue）：在队头进行的删除操作
• 队列特点：先进先出（FIFO）
• 栈的应用非常广泛，在CPU内部就有提供栈这个机制。主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫等等。在CPU内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。在编程语言中：主要用来进行函数的调用和返回。在计算机中，可以说，只要数据的保存满足先进后出的原理，都优先考虑使用栈，所以栈是计算机中不可缺的机制。
  

队列的认识

• 队列是生活中排队的抽象
• 插队是不允许的
• 队列的主要特点是先进先出，所以又把队列称为先进先出表。

队列的应用

• 记录访问或操作的顺序
• 对独占资源的调度安排，如打印机
• 电子商务网站的秒杀功能
• 大型信息系统中的消息队列

队列的抽象数据类型

• 数据元素集合：具有相同性质数据元素的有限序列,且只能在称为队尾的一端进行插入操作和在队头的一端进行删除操作。
• 基本操作：
  • 初始化队列 (InitQueue)
  • 求队列长度 (QueueLength)
  • 入队 (EnQueue)
  • 出队 (DeQueue)
  • 判队空 (QueueEmpty)

队列的存储结构

• 顺序队列
• 链队列
• 

队列的链式存储结构与实现

• 链队：采用不带头结点的单链表实现
• 队头指针和队尾指针
  
  
  链队组成:
  （1）存储队列元素的单链表结点
  （2） 指向队头和队尾指针的链队头结点

链队的进队和出队操作

• （a）空队
  
• （b）a、b、c进队
  
• （c）出队一次
• 
• 链队的4要素：
• 队空条件：front=rear=NULL
• 队满条件：不考虑
• 进队e操作：将包含e的结点插入到单链表表尾
• 出队操作：删除单链表首数据结点

链队的数据类型

• front指针指向头结点
• rear指针指向最后一个元素结点
  
  

初始化链队列

• 构造一个只有空头结点的链式队列
• 头尾指针均指向头结点
• 
• 

入队操作

• 生成新结点并插入到链表尾部
  
  

出队操作

• 判断队列是否为空

• 

• 删除队头元素结点

• 

• 若被删结点是队尾结点，则更新队尾指针指向头结点。

• 
  

队列的顺序存储结构与实现

• 使用数组实现队列

• 

• 头尾指针分别表示队头和队尾

顺序队列的假溢出问题

• 解释了假溢出现象和解决方法

• 当rear超出数组最大下标后，队列的空间就用尽了。
  即使数组下标较小的位置还有空闲空间，也不能进行入队操作

队列上溢

真上溢 (rear-front=MaxSize)：队列真正满，无空位。
假上溢：rear已指向队尾，但队列前端仍有空位置。
解决假上溢的方法：
方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）
方法二：（构造）循环队列

循环队列

• 首尾相接的队列实现：把数组的首尾两个存储单元看成位置相邻的单元，即允许队列直接从数组中下标最大的位置前进到下标最小的位置。(设数组长度为Max)

循环队列取下一相邻单元下标运算

• 数组第一个单元的下标为 0
  与下标1的单元相邻
  (0+1)％ Max＝1
  数组最后一个单元的下标为Max－1
  其下一相邻的单元的下标为0
  (Max-1+1)％ Max＝0
  任一位置 X (0≤X≤Max-1)
  X的下一相邻的单元的下标为 (X+1)％Max

• 数据入队前
  
  

队满与队空的问题

• 解释了如何判断队列满和队空
• 

解决方法

• 少用一个存储单元来区分队满和队空
• 队空：front==rear
• 队满：(rear + 1) % MaxSize == front
• 队列长度：(rear–front+MaxSize) % MaxSize

循环队列入队操作

• 
  

循环队列出队操作

• 
  

总结

• 循环队列和链队列的比较
  • 时间性能：基本操作都需要常数时间 O(1)
  • 空间性能：循环队列有存储元素个数的限制和空间浪费问题；链队列没有队列满的问题，但有结构性开销