<style> .reveal p{text-align:left;}</style> # 栈 --- #### 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存放了结构体数组类型后，栈顶访问到的就是结构体类型变量了，需要按照结构体变量的方式去使用。 --- ## 例题与练习 [后缀表达式的值](http://39.99.183.126:8888/p/YBTJ1331) [**P101** 括号匹配](http://39.99.183.126:8888/p/101) [**P752** 中缀表达式值](http://39.99.183.126:8888/p/752) [NOIPJ2013B 表达式求值](http://39.99.183.126:8888/p/NOIPJ2013B)