栈

贡献者：有机物

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

　　栈的常用操作：

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

　　 C++ STL

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

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

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

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

　　定义一个数组 $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

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

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。