操作与接口
队列 (queue) 也是受限的序列: 先进先出 (FIFO)、后进后出 (LILO)
只能在队尾插入 (查询): enqueue() + rear()
只能在队头删除 (查询): dequeue() + front()
操作实例
模板类
队列既然属于序列的特列，故亦可直接基于向量或列表派生
1
2
3
4
5
6
7
template <typename T>
class Queue : public List<T> { // 由列表派生的队列模板类
public: // size() 与 empty() 直接沿用
void enqueue(T const &e) { insertAsLast(e); } // 入队
T dequeue() { return remove(first()); } // 出队
T & front() { return first() -> data; } // 队首
};
确认: 如此实现的队列接口，均只需 $ O(1) $ 时间
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名
