与向量和列表一样，栈(stack)和队列(queue)保存的数据对象之间也具有线性次序，他们也属于线性序列结构。相对于一般的序列结构，栈与队列的数据操作对象仅限于逻辑上的特定某端。然而得益于其简洁性与规范性，它们既成为构建更复杂、更高级数据结构的基础，同时也是算法设计的基本出发点，甚至常常作为标准配置的基本数据结构以硬件形式直接实现。
相较于向量和列表，栈与队列的外部接口更为简化和紧凑，故亦可视作向量与列表的特例，借助于C++的继承与封装机制，可以轻松实现这两种数据结构。
栈中把可操作的一端叫做栈顶，而另一无法操作的盲端叫做栈底。对栈可行的操作只能在栈顶进行，由此不难看出栈中元素接受操作的次序必然始终遵循所谓后进先出(last-in-first-out, LIFO)的规律，即更早(晚)入栈的元素更晚(早)出栈。
1 template<typename T> 2 class Stack : protected Vector<T> 3 { 4 public: 5 void push(const T& e) 6 { 7 this->insert(e); 8 } 9 void pop() 10 { 11 this->remove(); 12 } 13 T& top() 14 { 15 return (*this)[size() - 1]; 16 } 17 size_t size()const 18 { 19 return Vector<T>::size(); 20 } 21 bool empty()const 22 { 23 return Vector<T>::empty(); 24 } 25 };
以上便是基于已经实现的向量结构通过派生实现的栈数据结构。
push、pop分别是入栈、出栈操作，top返回栈顶元素的引用，size返回栈内元素个数，empty判断栈是否为空。
与栈一样，队列(queue)中的元素也按线性的逻辑次序排列。队列结构同样支持对象的插入和删除，但两种操作的范围分别被限制于队列的两端——若约定新对象只能从某一端插入其中，则只能从另一端删除已有的元素。允许取出元素的一端称作队首，而允许插入元素的一端称为队尾。元素的插入与删除是修改队列结构的两种方式，站在被操作对象的角度，则分别称入队和出队。由此可以看出，与栈结构恰好相反，队列中各对象的操作次序遵循所先进先出(first-in-first-out,FIFO)的规律：更早(晚)入队者，更早(晚)出队。
与栈结构一样，队列也同样可以借由列表或向量实现。以下是基于已经实现的列表结构实现的队列结构。
template<typename T> class Queue:protected List<T> { public: size_t size()const { return List<T>::size(); } bool empty()const { return List<T>::empty(); } void push(const T& e) { this->push_back(e); } void pop() { this->pop_back(); } T& front() { return List<T>::front(); } T& back() { return List<T>::back(); } };
push、pop分别是入队、出队操作，front、back分别返回队首、队尾元素的引用，size返回队列内元素个数，empty判断队列是否为空。
原文：https://www.cnblogs.com/sxzh/p/14749128.html