写在前面：这一系列文章我会采用“广度优先”的书写原则，即主要更新发布标号为xy.00的文章，标号为xy.ab的比较细化的文章需要较长的写作时间。
基于我们构架过的顺序表数据结构(动态数组)，限制它的随机访问、增加元素、删除元素操作的操作位置，即可构成“限制访问线性表”数据结构。典型的例子是栈和队列。
栈和队列相比于链表这种较为抽象的数据结构来讲要直观得多，但是这可能是我们接触的最后两个如此直观的数据结构了（悲）。各种树结构还在等着大家！
由于栈和队列有着大量的相同点，不同于一般的数据结构教程将栈和队列分章节讲的叙述逻辑，我将把栈和队列同时同地表述。
什么是栈？什么是队列？
吃过自助餐吗？没有的话就去吃一次！在吃自助餐之前，如果餐厅的人气比较火爆，您可能需要排队。现实中的排队情境就是一种逻辑上的队列：越早进入的人一般情况下会越早出去(对于程序中的栈而言，越早进入的元素会一定越早出去，没有例外)。作为新来的顾客，你只能看到(访问)并且加入(push)队尾，而作为叫号的老板，你只能看到并且使队首的人进入餐厅(pop)。这种模式被称为“先进先出”（FIFO: first in first out）。这种模式表现在程序设计中，就称为队列数据结构。
等你进入自助餐厅之后，在盛菜品之前，你需要从一摞盘子中拿一个。一般的话正常的食客都会拿取放在最上边的盘子，而一般的服务生也都会把洗好的盘子放在最上边，也就是说，你拿取的盘子是这一摞盘子里最晚被放上去的，而最下边的盘子是最先被放进去的，同时一般情况下会最晚被拿走。(这个例子中排除那些喜欢抽取中间的盘子的奇奇怪怪的人。)(对于程序而言同样没有例外)即：对于食客和服务生而言，只有最上边的盘子会被访问，也只能在最上边加入(push)新盘子，这一摞盘子就是一个逻辑上的栈。这种模式被称为“先进后出”（FILO: first in last out）。这种模式表现在程序设计中，就称为栈数据结构。
队列支持访问队首和队尾的元素、在队首删除元素、在队尾加入元素；栈支持访问栈顶的元素、在栈顶加入或删除元素。很明显，队列和栈所定义的操作是我们之前实现的动态数组所支持的操作的真子集，它只是限制了我们对动态数组内元素的可见范围，因此我们可以认为它是一种限制访问的线性表，那么我们可以将动态数组重新封装为一个派生类来实现这两个数据结构。
动态数组派生栈/队列
简单实现一下：仅需要不到10行即可写好 (我们顺便复习一下C++类继承的知识)
/*上方应有类array的实现或include包含着array的文件*/
template<class elementType>
class arrayStack : private array<elementType> {
public:
arrayStack(int initSize = 10) : array<elementType>(initSize) {}
void pop() { array<elementType>::pop(); }
void push(elementType value) { array<elementType>::push(value); }
elementType top() const { return array<elementType>::operator[](array<elementType>::size() - 1); }
int size() const { return array<elementType>::size(); }
bool empty() const { return this->size() == 0; }
};
我们不希望用户访问一部分array类的成员函数或者方法（比如在随机位置插入或删除元素、随机访问等），那么我们选择使用访问权限修饰符private来派生新的栈类。这种权限的基类继承仅能在新类(arrayStack)的成员函数中访问基类(array)的protected和public成员，而不可以在外部访问基类的一切成员，因此我们也没有必要对基类成员使用virtual关键字来避免继承带来的重载函数或方法的访问问题；也没有必要对新类成员使用override关键字来重写函数或方法（实际上编译器的静态检测程序会提示错误阻止我们使用override）。我们可以认为，我们通过封装，“删除/掩蔽掉”了array中的一些不符合我们预期的成员方法，这种写法表明我们把栈认为是一种特殊的动态数组线性表，符合我们之前“栈是一种限制访问的线性表”的认识。
再来写一下队列的实现（仅仅需要修改两个方法的参数，没什么新奇的）：
template<class elementType>
class arrayQueue : private array<elementType> {
public:
arrayStack(int initSize = 10) : array<elementType>(initSize) {}
void pop() { array<elementType>::pop(0); }
void push(elementType value) { array<elementType>::push(value); }
elementType top() const { return array<elementType>::operator[](0); }
int size() const { return array<elementType>::size(); }
bool empty() const { return this->size() == 0; }
};
但是需要注意的是，因为这类派生类实现存在着很多函数或者方法的套娃调用，而且基类多不能适应新类的实际情况来进行优化，故使用限制操作的派生类来实现新的数据结构是低效的。但是它有利于理解，所以就写了。
链表实现栈/队列
想到禁止随机访问和频繁地增/删元素(因为栈和队列基本只在增删)，我们一定会想到链表，链表可能是完成栈和队列实现的最佳基本数据结构之一。对于栈，我们只需要将表头节点的next指针指向栈顶，即可非常方便地完成增删。对于队列，我们只需要维护一个指向链表尾的节点来作为队尾的标记(因为在链表尾，插入容易而删除困难；而在链表头，插入和删除均容易)，即可完成增删操作。
同样地，说到链表，请不要成环。
我们依旧使用之前使用过的链表节点结构体：
template<class elementType>
struct node {
elementType data;
node<elementType> *next;
node(elementType _data = 0, node<elementType>* _next = nullptr) : data(_data), next(_next) {}
bool operator==(const node<elementType> &x) {
return this->data == x.data && this->next == x.next;
}
};
首先实现相对简单一点点的栈：
由于使用了链表，所以构造和析构函数须格外小心。
template<class elementType>
class stackChain {
private:
node<elementType> *head;
unsigned int _size = 0;
public:
stackChain();
~stackChain();
void clear();
void push(elementType value);
void pop();
elementType top() const { return head->next->data; }
unsigned int size() { return _size; }
bool empty() { return this->_size == 0; }
};
template<class elementType>
stackChain<elementType>::stackChain() {
head = new node<elementType>;
}
template<class elementType>
stackChain<elementType>::~stackChain() {
this->clear();
delete head;
}
template<class elementType>
void stackChain<elementType>::clear() {
node<elementType> *str = head->next;
while (str) {
node<elementType> *tempPtN = str;
str = str->next;
delete tempPtN;
}
head->next = nullptr; //千万别忘了这一句！！！
this->_size = 0;
}
template<class elementType>
void stackChain<elementType>::push(elementType value) {
node<elementType> *str = new node<elementType>(value, head->next);
head->next = str;
this->_size++;
}
template<class elementType>
void stackChain<elementType>::pop() {
node<elementType> *str = head->next;
head->next = head->next->next;
delete str;
this->_size--;
}
为什么不在top()中判断_size非零？
需要注意我们在类中维护_size变量的目的仅仅是为了通过size()函数向用户返回栈的大小，我们在top()函数中并未使用它来避免对于空栈栈顶的访问。这是为什么？
与之前实现的动态数组相比：动态数组维护长度变量的目的主要是为了防止下标越界，因为如果发生了越界，数组索引很有可能命中未知的内存块（出现在数组外部的左侧）或者未经初始化或被懒惰删除掉的部分（出现在数组内部的右侧），这些部分存储了对于动态数组而言无效的垃圾数据，但这些部分却是可能可以被程序正常访问的，除非安装了内存检测程序或者静态分析程序，否则程序会正常运行不会报错，但是可能会导致数组内容不连续（如果对越界索引使用插入操作）或者给用户返回一个令人头疼的结果（如果访问越界索引），所以我们需要阻止这样的情况发生。
但是对于栈，函数top()仅仅会在空栈时出现问题，而在这种情况下，编译器已经有了现成的检测机制。访问空栈栈顶时，由于函数请求访问NULL指针的data成员，我们的程序会抛出一个非常漂亮的红色的Segmentation fault异常来问候这个错误操作的、试图访问空栈栈顶的程序员。
接下来实现队列。队列与栈相比需要多维护一个指向链表尾的指针，这个指针我们选择将其储存在类内（如果链表不是模板类而是整形链表，则可以考虑将该指针转为整形数存在表头节点的data域中）。
template<class elementType>
class chainQueue {
private:
node<elementType> *head = nullptr;
node<elementType> *end = nullptr;
unsigned int _size = 0;
public:
chainQueue();
~chainQueue();
void clear();
unsigned int size() const { return _size; }
void push(elementType val);
void pop();
elementType getHead() const;
elementType getEnd() const;
};
template<class elementType>
chainQueue<elementType>::chainQueue() {
if (head != nullptr) {
this->clear();
delete head;
}
head = new node<elementType>;
end = head;
}
template<class elementType>
chainQueue<elementType>::~chainQueue() {
this->clear();
delete head;
}
template<class elementType>
void chainQueue<elementType>::clear() {
node<elementType> *str = head->next;
while (str != nullptr) {
node<elementType> *tempPtN = str;
str = str->next;
delete tempPtN;
}
_size = 0;
end = head;
}
template<class elementType>
void chainQueue<elementType>::push(elementType val) {
node<elementType> *newPtN = new node<elementType>(val);
end->next = newPtN;
end = newPtN;
_size++;
}
template<class elementType>
void chainQueue<elementType>::pop() {
if (_size == 0)
throw("empty queue!");
node<elementType> *tempPtN = head->next;
head->next = tempPtN->next;
delete tempPtN;
_size--;
if (_size == 0)
end = head; //否则end会成为野指针
}
template<class elementType>
elementType chainQueue<elementType>::getEnd() const {
if (_size == 0)
throw("empty queue!");
return end->data;
}
template<class elementType>
elementType chainQueue<elementType>::getHead() const {
return head->next->data;
}
本实现中由于使用了尾指针，而尾指针在长度为0时要求与一般情况不同的操作方式，故需要维护_size来指导尾指针的行为。
循环数组实现队列和栈
使用一个定长数组为存放数据的容器，维护表示数组下标的整形变量来表示栈顶、队首/队尾。
这种实现较为简单，留作练习。
栈和队列的特征对比
栈常用来表示一种层级关系，而队列常用来表示一种顺序关系。
在搜素算法方面，栈一般用作深度优先搜索、而队列一般用作广度优先搜索。这是反映它们各自特点的典型应用之一，但是由于知识的不足，关于深度优先搜索的栈实现和广度优先搜索的队列实现将在“二叉树”之后描述。
练习
1 为我们的链表栈和链表队列实现赋值运算符和复制构造函数，要求不可以仅仅复制head指针值。
2 使用循环数组法实现栈和队列
