栈

                     

贡献者： 有机物

　　 栈是一种 “先进后出” 的数据结构。也是计算机实现递归和基本结构，栈只有一端可以进出元素，这一段被称为 “栈顶”，另一端被称为 “栈底”。往栈中插入元素被称为” 进栈 “，往栈中删除元素被称为 “出栈”。 C++ 的 STL 已经帮助我们实现好了栈，一般情况我们可以直接使用 STL 库里的栈。

　　 栈的常用操作：

1. 向栈顶插入一个数 $x$；
2. 从栈顶弹出一个数；
3. 判断栈是否为空；
4. 查询栈顶元素。

　　 C++ STL

#include <stack> // 注意要引入栈的头文件

stack<int> stk;
stk.push(x);     // 在栈顶插入一个数 x
stk.pop();       // 弹出栈顶元素, 但不返回其值
if (stk.empty()) // 果栈为空则返回 true, 否则返回 false;
cout << stk.top() << endl;   // 输出栈顶元素, 但不删除该元素

// 还有如下几个操作
stk.size();        // 返回栈中元素的个数

　　 但我们在这里详细的讲一下如何使用数组模拟栈。

　　 定义一个数组 $\mathtt{stk}$ 用于模拟栈，再定义一个变量表示栈顶，初始化为 $0$。

string op;
cin >> op;

int tt = 0;
if (op == "push")
{
    int x;
    cin >> x;
    stk[ ++ tt] = x;   // 向栈顶添加一个数
} 
if (op == "query") cout << stk[tt] << endl;
if (op == "pop") tt -- ;  // 删除栈顶元素，即 tt -- 
if (op == "empty") cout << (tt ? "NO" : "YES") << endl;  // 栈为空则输出 YES，否则输出 NO

　　 以上就是栈的基本操作了。