C++ 数据结构(四)栈与队列(3)队列接口与实现
     发布在:C/C++      浏览:37      评论:0 条评论

上一篇:《C++ 数据结构(四)栈与队列(2)栈应用(4)逆波兰表达式》

操作与接口

C++ 数据结构(四)栈与队列(3)队列接口与实现

队列(queue)也是受限的序列:先进先出(FIFO)、后进后出(LILO)

只能在队尾插入(查询):enqueue() + rear()

只能在队头删除(查询):dequeue() + front()

操作实例

C++ 数据结构(四)栈与队列(3)队列接口与实现

模板类

队列既然属于序列的特列,故亦可直接基于向量或列表派生

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) 时间

下一篇:《C++ 数据结构(五)二叉树(1)树》

Responses