Tim的资源站

一、队列的基本概念

队列是一种特殊的线性表，是限制在表的一端进行插入，而在另一端进行删除的线性表。允许插入的一端成为队尾（rear），允许删除的一端称之为队头（front）。

当表中没有元素时，称为空队列。队列的插入运算称之为进队列或入队列，队列的删除运算称为退队列或出队列。

队列示意图：

图中，入队列的顺序为e₁、e₂、e₃、e₄、e₅，出队列的顺序也是一样。
所以，队列又称之为先进先出线性表（First In First Out），简称FIFO表。

二、队列的抽象数据类型

对于队列，常用的基本运算有入队、出队、取队头元素等。下面给出队列的抽象数据类型的定义：

ADT Queue {
	数据：存储队列的元素的数据结构		// 可以用顺序表或者单链表存储
		队头位置
		队尾位置
	操作：
		Queue()	 	// 构造一个空队列
		~Queue()	// 销毁一个已存在的队列
		Empty_Queue()	// 判断队列是否为空
		EnQueue(e)		// 将元素e插入队尾
		DeQueue(&e)		// 从队头删除一个元素到e中返回
		FrontQueue(e)		// 从队头去除一个元素到e中返回
}