一、队列的基本概念
队列是一种特殊的线性表,是限制在表的一端进行插入,而在另一端进行删除的线性表。允许插入的一端成为队尾(rear),允许删除的一端称之为队头(front)。
当表中没有元素时,称为空队列。队列的插入运算称之为进队列或入队列,队列的删除运算称为退队列或出队列。
队列示意图:
图中,入队列的顺序为e1、e2、e3、e4、e5,出队列的顺序也是一样。
所以,队列又称之为先进先出线性表(First In First Out),简称FIFO表。
二、队列的抽象数据类型
对于队列,常用的基本运算有入队、出队、取队头元素等。下面给出队列的抽象数据类型的定义:
ADT Queue {
数据:存储队列的元素的数据结构 // 可以用顺序表或者单链表存储
队头位置
队尾位置
操作:
Queue() // 构造一个空队列
~Queue() // 销毁一个已存在的队列
Empty_Queue() // 判断队列是否为空
EnQueue(e) // 将元素e插入队尾
DeQueue(&e) // 从队头删除一个元素到e中返回
FrontQueue(e) // 从队头去除一个元素到e中返回
}