定义

栈：仅在表尾进行插入和删除操作的线性表

与之对应的：当一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

特性：前进后出

可以想象一下沙漠之鹰的手枪，进栈为子弹弹入弹夹，出栈为子弹弹出弹夹

栈的应用

像浏览器的后退功能也是用栈来实现的，

单击后可以按访问顺序的逆序加载浏览过的网页

还有许多的文本编辑软件的 ctrl+z”的撤销功能，也是通过栈来实现的

栈中的专业名词

栈顶：允许插入和删除的一端栈底：栈顶的另一端空栈：不含任何元素的还可以说是栈是限定仅在表尾（栈顶）进行插入和删除操作的线性表插入就叫进栈删除称为出栈

例题

某城市有一个火车站，铁轨铺设如图。有 n 节车厢从 A 方向驶入车站，按进站的顺序编号为 1～n。你的任务是判断是否能让他们按照某种特定的顺序进入 B 方向的铁轨并驶出车站。例如，出栈顺序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。 为了重组车厢，你可以借助中转站 C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入 C 的车厢必须按照相反的顺序驶出 C。对于每节车厢，一旦从 A 移入 C，就不能返回 A 了;一旦从 C 移入 B，就不能返回 C 了。也就是说，在任意时刻，只有两种选择：A 到 C 和 C 到 B。

//首先中转站C中，车厢符合先进后出的原则，是一个栈#include<cstdio>#include<stack>using namespace std;const int maxn = 1000 + 10;int n, target[maxn];
int main(){  while (scanf_s("%d", &n) == 1)  {    stack<int> s;    int a = 1, b = 1;    for (int i = 1; i <= n; i++)    {      scanf_s("%d", &target[i]);    }    int ok = 1;    while (b <= n)    {      if (a == target[b])      {        a++;        b++;      }      else if (!s.empty() && s.top() == target[b])      //运用empty和top函数，包含头文件《stack》      {        s.pop();        b++;
      }      else if (a <= n)        s.push(a++);      else      {        ok = 0;        break;      }  }    printf("%s\n", ok ? "yes" : "no");
  }  return 0;}

习题巩固

题目：设计一个有 getMin 功能的栈

实现一个特殊的栈，在实现栈的基本功能上，再实现返回栈中最小元素的操作

要求：1.pop，push，getMin 操作的时间复杂度为 O（1）设计时候可以使用现成的栈结构