[数据结构与算法]数据结构学习（栈与队列：五（队的接口与实现））

队

队的接口与实现

与栈一样队也是一种存放数据对象的一种容器，且也是按线性的逻辑次序排列。队列结构同样支持对象的插入与删除，但这两种操作是被限制在队的两端，若约定对象只能从一段插入，则只能从另一端删除已有的元素。允许取出元素的一端被称为队头。允许插入的一端的元素被称作队尾。
一般将元素的插入和删除操作分别称作入队和出队。

有以上的约定不难看出，与栈的结构恰好相反，队列中各元素的操作次序遵循所谓的先进先出（first-in-first-out，FIFO）。更早（晚）出队的元素应为更早（晚）入队者。

ADT接口：
既然队列可视作序列的特例，故可将队列视作列表的派生类：

template <typename T> class Queue : public List<T>
{//队列模板类（继承List原有接口）
	public: //size、empty以及其它开放接口均可直接沿用
		void enqueue(T const& e) {insertAsLast(e);}//入队：尾部插入
		T denqueue() {return remove(first());} //出队：首部删除
		T& front() {return first() -> data;}//队首
}；

队的入队和出队操作都是队列表中一个元素进行插入和删除操作，所以复杂度均为常数。