1 队列的基本概念 队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行 删除。 队首(front) ：允许进行删除的一端称为队首。 队尾(rear) ：允许进 行插入的一端称为队尾。

2 队列的抽象数据类型定义 ADT Queue{ 数据对象：D ={ ai|ai∈ElemSet, i=1, 2, …, n, n >= 0 数据关系：R = { | ai-1, ai∈D, i=2,3,…,n } 约定a1端为队首， an端为队尾。 基本操作： Create()：创建一个空队列； EmptyQue()：若 队列为空，则返回true ，否则返回flase ； ⋯⋯ InsertQue(x) ：向队尾插 入元素x； DeleteQue(x) ：删除队首元素x； } ADT Queue 3.2.2 队列的顺序表示和实现

队列的顺序存储结构 利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元 素，称为顺序队列。 设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾 元素。 ◆ 初始化：front=rear=0。 ◆ 入队：将新元素插入rear所指的位 置，然后rear加1。 ◆ 出队：删去front所指的元素，然后加1并返回被删元 素。 ◆ 队列为空：front=rear。 ◆ 队满：rear=MAX_QUEUE_SIZE-1或 front=rear。 

循环队列

为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配 的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列 (Circular Queue)。 采用循环队列**后，进行入队和出队运算时，头、尾指针加1操作应如 下进行：** 出队： sq ®**front=(sq** ®**front+1)%** maxsize**;** 入队： sq ®**rear=(sq** ®**rear+1)%** maxsize**;** 循环队列如何判断队空和队满**?** 即**：** ◆ rear**所指的单元始终为空。** ◆ 循环队列为空**：front=rear** 。

◆ 循环队列满**：(rear+1)%MAX_QUEUE_SIZE** =front**。**