栈

· · 个人记录

在此感谢以下人对本篇文章的修改建议：

fast_photon ：提出打字错误以及学术错误

xhee ：提出学术错误

ningago ：帮助解决学术错误

Node_Edge ：理解上的优化

1. 栈的基础知识

定义：栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

首先栈一端封死（称为 栈底 , bottom ）。想向容器中加入元素，只能从另一端（称为 栈顶 ， top ）逐个加入。栈限定为只能在一端进行插入和删除操作。比如说：我们吃桶装薯片最底下的是最先放进的，而最先被吃掉的是最后放进的。此时的放薯片是 进 ,而吃薯片是 出 ，这样的一个生活实例就可以把栈实现出来。

那么我们该如何用代码实现栈呢，其实我们可以用数组来模拟，首先我们可以把一个数组竖着放如下图：

数组可以很好的模拟栈。数组的开头 0 （根据第一个数据输入的位置固定）可以看作不可移动的栈底，只需要维护一个栈顶，表示栈顶的下一个位置的下标，就可以轻松的实现插入与删除。

然后我们可以用一个结构体即: struct 来封装我们的这个栈代码如下：

struct Stack {
    int a[100000];
    int top //栈顶
} tot;

关于结构体的使用不会的同学或者说是好奇的同学可以自行上网搜索我就不多说了。

以上就是栈的基本知识，让我们进入下一个章节 φ(≧ω≦*)♪

2. 栈的操作

  1. 向栈中加入一个数

  2. 将栈顶弹出。如果此时栈为空则不进行弹出操作并且会报错

  3. 输出栈顶元素

  4. 输出此时栈内元素个数

  5. 如果该栈为空输出 true ,反之不为空输出 false

需要注意一下 弹出不意味输出 ，同时 输出不意味弹出 。

输出此时栈内元素个数其实就是你的栈顶( top )和栈底( bottom )的差, 但是 一般来说栈底的值一般为 0 ,所以一般输出此时栈内元素个数就是你栈顶的标号。

向栈中加入一个数注意是从栈顶加入

3. STL的使用

1. `stack <int> q` 声明一个 int 类型的栈 q 2. `q.push()`：向栈中加入一个数 3. `q.pop()`：将栈顶弹出。如果此时栈为空则不进行弹出操作 4. `q.empty()`：如果该栈为空输出 $true$ ,反之不为空输出 $false

  1. q.size()：输出此时栈内元素个数

  2. q.top()：输出栈顶元素

4. 实战

让我们来点题目吧！

B3614 【模板】栈

P1739 表达式括号匹配

P1449 后缀表达式