大家在学习编程时或程序开发中，经常涉及数据结构中的“队列”和“栈”。那么他们分别具有什么结构特点？底层实现原理是什么？他们在STL中是如何实现的呢？都有哪些应用场景呢？
备注：因为篇幅限制，本文先讲解数据结构中的栈(stack)。
1.引言
栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。
通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
举例：
线性表Insert(L, i, x)1≤i≤n+1Delete(L, i) 1≤i≤n
栈Insert(S, n+1, x) Delete(S, n)
队列Insert(Q, n+1, x)Delete(Q, 1)
2.栈的定义和特点
栈(stack)是一种先进后出的数据结构。它只有一个出口。stack允许新增元素、删除元素、取得最顶端元素。但是除了最顶端外，没有任何其它方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。
定义：限定仅在表尾进行插入或删除操作的线性表。表尾是栈顶，表头是栈底，不含元素的空表称空栈。
特点：先进后出（FILO）或后进先出（LIFO）
3.栈的实现原理
类似于线性表的顺序映象实现，利用一组存储单元依次存放自栈底到栈顶的数据元素，同时附设指向表尾的指针top，指示栈顶元素在顺序栈中的位置，称为栈顶指针，连续存储单元的基址用指针base指示，称为栈底指针。
//----- 栈的顺序存储表示 -----
#define STACK_INIT_SIZE 100;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
top的初值指向栈底：top=base，此条件也可作为判栈空的条件；
在实际使用中，top 始终指向栈顶元素的下一个位置上；
入栈（插入新的栈顶元素）：top增1；
出栈（删除栈顶元素）： top减1。
3.1.顺序栈
利用一组"地址连续"的存储单元依次存放自栈底到栈顶的数据元素
数据结构和入栈出栈示意图：
3.2.链栈
利用一组链表依次存放自栈底到栈顶的数据元素。
链表节点定义：
typedef struct node
{
int data;
struct node *link;
} node;
数据结构和入栈出栈示意图：
4.STL中的栈实现
在c++开发中，我们常常直接使用STL中封装好的容器。那么，对于栈在STL中是如何实现的呢？又有哪些特点呢？
①SGI STL的stack默认是以deque为底层数据容器的。(对应前面提到的“顺序栈”，也可以使用vector为底层数据容器)
以某种既有容器作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个stack,是很容易做到的。deque是双向开口的数据结构，若以deque为底部结构并封闭其头端开口，便轻而易举地形成了一个stack。因此，SGI STL便以deque作为缺省情况下的stack底部结构，stack的实现因而非常简单，源代码十分简短。
template <class T, class Sequence = deque<T> >
class stack {
friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;// 底层容器
public:
// 以下完全利用 Sequence c 的操作，完成 stack 的操作。
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
// deque 是两头可进出，stack 是末端进，末端出（所以后进者先出）。
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c < y.c;
}
②stack没有提供迭代器
stack所有元素的进出都必须符合“先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stck不提供走访功能，也不提供迭代器。
③可以使用list作为stack的底层容器。(对应前面提到的“链栈”)
除了deque之外，Iist也是双向开口的数据结构。上述stack源代码中使用的底层容器的函数list都具备。因此，若以list为底部结构并封闭其头端开口，一样能够轻易形成一个stack。
测试代码：
参考文章最后的附录。
测试程序运行效果：
分别使用STL的deque、list、vector作为stack的底层容器，进行同样数据的入栈和出栈。
5.栈的应用举例
①数制转换
例如：（1348)10 = (2504)8 ，其运算过程如下：
②括号匹配的检验
例如：假设在表达式中，只有［］（）两种括号，如：（［］（））、［（［ ］［ ］）］等为正确的格式，［（ ］）或（［（ ））或 （（） ］ ）均为不正确的格式。检验括号是否匹配。
算法的设计思想：
1）凡出现左括号，则进栈；
2）凡出现右括号，首先检查栈是否空：
若栈空，则表明该“右括号”多余不匹配，
否则和栈顶元素比较，
若相匹配，则“左括号出栈”，否则表明不匹配
3）表达式检验结束时，
若栈空，则表明表达式中匹配正确
否则表明“左括号”有余，不匹配
③回文游戏
例如：顺读与逆读字符串一样（不含空格）
比如，字符串：“madam im adam”
算法设计思想：
1.读入字符串
2.去掉空格（原串）
3.压入栈
4.原串字符与出栈字符依次比较
若不等，非回文
直到栈空都相等，回文
④行编辑程序问题、迷宫求解、表达式求值、实现递归等
这些场景就不给大家一一举例了，感兴趣的同学可以再评论区留言，我再留言区回复大家。
6.附录
测试代码源码。
#include<iostream>
#include <stack>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
template <class T, class Sequence = deque<T> >
void stack_fun_test(stack<T, Sequence> & list_stack)
{
//入栈
list_stack.push(1);
list_stack.push(3);
list_stack.push(5);
list_stack.push(7);
if (true != list_stack.empty())
{
}
// 元素依次出栈
while (true != list_stack.empty())
{
// 打印栈顶元素
// 出栈
list_stack.pop();
}
}
//以deque作为缺省情况下的stack底部结构
void stack_fun_deque_test()
{
stack<int> list_stack; //创建stack
stack_fun_test(list_stack);
}
//以list作为stack底部结构
void stack_fun_list_test()
{
stack<int, list<int>> list_stack; //创建stack
stack_fun_test(list_stack);
}
//以vector作为stack底部结构
void stack_fun_vector_test()
{
stack<int, vector<int>> list_stack; //创建stack
stack_fun_test(list_stack);
}
int main(int argc, char* argv[])
{
stack_fun_deque_test();
stack_fun_list_test();
stack_fun_vector_test();
return 0;
}
原创不易，欢迎关注、收藏、转发！