栈

1. 特性

栈（stack）又名堆栈，是一种操作受限的线性表，只能在表的一端进行插入和删除操作，这一端被称为栈顶，相对的，另一端被称为栈底，向栈内添加新元素的操作叫做入栈、进栈、压栈，删除元素叫做出栈、退栈。

由于栈中元素只能在一端进出，所以最先进入栈中的元素反而在最后才能出去，所以栈又被称作先进后出（FILO—first in last out）线性表。

2. 逻辑结构

3. 物理结构

同队列一样，栈可用顺序结构存储，使用数组简单模拟，但有空间浪费。使用链式存储，虽然较繁琐一点，但胜在可以空间动态增长，防止空间浪费。

4. STL中stack的使用

#include<stack>  //  引入头文件

stack<type> s;  //  新建栈s，栈中元素类型为type

s.size();  //  返回栈中元素数量
s.empty();  //  判断栈是否为空，空则返回true
s.push(node);  //  入栈操作，node元素入栈
s.pop();  //  出栈操作
s.top();  //  获取栈顶元素

5. 竞赛考题

在竞赛中，栈不只会在代码中用到，还会在非代码的选择题中遇到，做这类型题时，只要铭记任何时候都有可能出栈即可完成：

元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第一个出栈的是R3，那么第五个出栈的不可能是（    ）。
A．R1           B．R2          C．R4           D．R5

对于入栈顺序为a, b, c, d, e, f, g 的序列，下列（ ）不可能是合法的出栈序
列。
A. a, b, c, d, e, f, g   B. a, d, c, b, e, g, f
C. a, d, b, c, g, f, e   D. g, f, e, d, c, b, a

答案：BC

数组模拟栈

栈是一种操作受限的线性数据结构，可以理解为操作受限的数组，因此，我们可以自行模拟出栈。

栈的一切操作都在栈顶执行，因此设立栈顶指针（数组下标）head，栈底则为0即可。

入栈即栈顶位置赋值，然后栈顶+1。

stack[head++] = t;

出栈即栈顶-1

head--;

取栈顶即返回栈顶元素

return stack[head-1];  // stack[head]，在栈之外，始终视为空

栈大小就是head的大小（若栈底为0）

return head - 0;

判断栈空就看head是否大于0

return head <= 0;  // 空则返回true

结构体栈

stack本质上是数组，所以可以存放各种数据类型，包括结构体。

stack存放了结构体数组类型后，栈顶访问到的就是结构体类型变量了，需要按照结构体变量的方式去使用。

例题与练习

P101 括号匹配

P752 中缀表达式值