前言
如果你和程序员接触的比较多，你可能会经常听到他们说一个词——“栈溢出（Stack Overflow）”。那么栈到底是什么？为什么会溢出这？下面我们就一一解答这些问题。一点点题外话，Stack Overflow 也是一个很好的社区。
栈（stack），又名堆栈，是一种运算受限制的线性表类型的数据结构。其限制是只允许在栈的一端进行插入和删除运算。这一端被成为栈顶，相对地，把另一端称为栈底。
可以想象往子弹夹中装子弹的情形，正常情况下只能往子弹夹入口那段端入子弹，这一步就好比向栈中压入元素，称为 push，射击的时候，弹夹会从顶端弹出子弹，这一步就好比从栈顶弹出元素，称为 pop，可以发现，从栈顶弹出的子弹是最后一个压进去的子弹，这也是栈的一个重要性质，先进后出（FILO——first in last out）。另外，用一个 top指针来标示当前栈顶的位置。
实现
关于栈的实现，一种方法是利用数组手动实现，需要固定缓存大小，也是就是数组大小。
int stack[maxsize]; // 储存栈的空间
int top = 0; // 当前栈顶的指针位置
void push(int x) { // 入栈，压入一个数x到栈顶
stack[top++] = x;
}
void pop() { // 出栈，从栈顶弹出一个元素
--top;
}
int topval() { //获取栈顶元素
return stack[top - 1];
}
int empty() { // 检验栈是否为空
return top > 0;
}
STL 中的栈
在 C++ 中有已经写好的栈对象，可以直接用。C 语言中没有对象的概念，但是使用 C 语言的同学有必要学习一下，C++ 是兼容 C 语言的，学会使用 STL 的好处第一是避免自己写的有错误，第二是节省时间。
#include <stack>
#include <iostream>
using namespace std;
stack<int> S;
int main() {
S.push(1);
S.push(10);
S.push(7);
while (!S.empty()) {
cout << S.top() << endl;
S.pop();
}
return 0;
}
上面代码是 C++ 里面的 stack 的用法。
总结
| 方法 | 功能 |
|---|---|
| pop | 出栈 |
| push | 压栈 |
| top | 返回栈顶元素 |
| empty | 判断栈是否为空 |
京公网安备 11010502036488号