数据结构与算法-队列

队列的概念

队列(Queues)是生活中“排队” 的抽象

排队只能排在尾部, 排在对头的先得到服务;
“插队”是不允许的. 换言之, 插入和删除只能在线性表的两头分别进行;
插入的一端称为队尾, 删除的一端称为队头;
其特点是: 先进先出(FIFO)

队列的定义

队列（Queue）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表
队尾(rear)——允许插入的一端
队头(front)——允许删除的一端
在队尾进行的插入操作称为入队
在队头进行的删除操作称为出队
队列的特点：先进先出

队列的抽象数据类型

ADT Queue
数据元素集合：
具有相同性质数据元素的一个有限序列，且只
能在称为队尾的一端进行插入操作和在队头的
一端进行删除操作。
基本操作：
构造队列
求队列长度(QueueLength)
入队(EnQueue)：在队尾插入新的数据元素
出队(DeQueue)：删除队头的数据元素
判队空(QueueEmpty)
队列上溢：
真上溢 (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
(x+1)％Max

区别循环队列空、满状态（了解）
设置一个标志位
标识前一个操作是入队，还是出队操作。
初始标志位tag置为0；执行入队操作后，把标志位置为1；执行出队操作后，把标志位置为0。
队空：frontrear && tag0
队满：frontrear && tag1
设置一个计数器
计数队列中的元素数，同时还能起到标志位的作用。
初始计数器count置为0；执行入队操作后，使计数器count增一；执行出队操作后，使计数器count减一。
队空：count0
队满：count > 0 && frontrear
解决方法：少用一个存储单元（常用）
队空：front==rear
队满：(rear + 1) % MaxSize == front
队列长度：(rear–front+MaxSize) % MaxSize
时间性能:
循环队列和链队列的基本操作都需要常数时间 O(1)。
空间性能:
循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。
链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个地址域，从而产生了结构性开销。