队列

一、队列的基本概念

队列是一种特殊的线性表,是限制在表的一端进行插入,而在另一端进行删除的线性表。允许插入的一端成为队尾(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中返回
}
用户头像
登录后发表评论