栈（Stack）数据结构详解

蛟龙_wangyanxi

2026-08-29 13:09:34

发布于：广东

3阅读

0回复

0点赞

注：本文为CSDN本人的博客搬运并进行了排版优化

简介

栈（Stack）是一种先进后出（FILO, First In Last Out）的线性数据结构，类似于生活中一摞盘子的摆放方式——你总是先拿到最上面的盘子，而最下面的盘子最后才能被拿到。

从结构上看，栈是一种操作受限的线性表，它只允许在表的一端（称为栈顶）进行数据的插入或删除操作，另一端（称为栈底）则是封闭的。这意味着任何不在栈顶的元素都无法被直接访问，必须等到它上面的所有元素都被取出后，才能触及到它。这种“后进先出”的机制，使得栈天然适合处理具有嵌套结构或需要回溯的场景。

栈的实现方式灵活多样，既可以使用数组（静态栈）来实现，也可以使用链表（动态栈）来构建。数组实现简单高效，但需要预先分配固定大小的空间；链表实现则可以动态扩展，更加灵活。

栈的应用遍布计算机科学的各个领域：程序运行时的函数调用栈支持函数的嵌套调用和递归实现；编译原理中用于表达式求值和括号匹配检查；日常应用中的撤销操作、浏览器的前进后退功能；算法设计中的深度优先搜索（DFS）等，都离不开栈的支持，虽然我不用。

栈的优点是实现简单、操作高效（所有基本操作均为 $O(1)$ 时间复杂度），缺点是访问受限，无法直接访问栈中任意位置的元素。这种以受限访问换取清晰逻辑和高效性能的设计，使栈成为计算机科学中不可或缺的基础数据结构。

这是一个栈：

它的压入顺序显然是1-2-3-4
此时如果我们弹出顶部元素(4)
它就会变成这样：

假设我们知道一个入栈顺序1-2-3-4和出栈顺序3-4-2-1如何判断出栈顺序是否合法呢？
我们知道，要让3先出栈必然要先把1和2先压入，把3压入，

再让3 出栈

此时栈中还剩余的元素是1和2

接着同理，再把4压进去，弹出来，我们就得到了3-4的出栈顺序
栈中剩余元素为1和2

按顺序出栈即可得到3-4-2-1的顺序，所以这个顺序是合法的。
以上即为判断出栈顺序是否合法的方法。
毒瘤CSP经常考

代码框架

需要用到头文件<stack>

#include <stack>

也可以手写（有亿点麻烦）

const int MAXN = 1e6 + 5; // 最大值 

struct Stack { // 手写栈
	int s[MAXN], top;
	Stack() { // 构造函数
		memset(s, 0, sizeof(s));
		top = 0;
	}
	void push(int x) { // 压入
		s[++top] = x;
	}
	void pop() { // 弹出
		top--;
	}
	int top() { // 栈顶
		return s[top];
	}
	int size() { // 长度
		return top;
	}
	bool empty() { // 是否为空
		return !top;
	}
};
// 没有非法判断

例题

洛谷 P1427 小鱼的数字游戏

这道题虽然有很多种做法，
还比较简单，
但还是先用栈做

题目大意

输入 $n$ 个数，将它们倒序输出

思路

将 $n$ 个数压入栈中，
随后挨个输出并弹出。
因为栈的FILO（先进后出）性质，所以会倒序输出。

Code

1.带注释详解版

#include <iostream>
#include <algorithm>
#include <stack>
#define Please return
#define AC 0
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
stack<int> st; // st 是栈
int a; // a 是读入的数

int main() {
	while (cin >> a && a != 0) { // 输入
		st.push(a);
	}
	while (!st.empty()) { // 输出
		cout << st.top() << " ";
		st.pop(); // 注意弹出
	}
	cout << endl;
	Please AC;
}

2.无注释纯享版

#include <iostream>
#include <algorithm>
#include <stack>
#define Please return
#define AC 0
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
stack<int> st;
int a;

int main() {
	while (cin >> a && a != 0) {
		st.push(a);
	}
	while (!st.empty()) {
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
	Please AC;
}