欢迎光临
我们一直在努力

栈的奥秘:从基础到实战

文章目录
一、前言
二、栈是什么?
三、使用步骤
四、总结
前言
曾有一位程序员面试大厂,面试官出了道现场手写的题:“设计一个支持随时获取最小元素的栈。”他很快写出了push、pop,却在实现getMin时卡住了——每次想拿最小值,都得把整个栈翻个遍,太慢了。

面试官笑了笑:“如果每个栈状态都顺便记一下当前的最小值呢?”

栈就是这么个挺有意思的东西。表面看它死板得很——“后来居上,先得后出”,跟排队完全反过来。但只要稍微动点脑筋,它就能秒速告诉你最小值,还能轻松搞定括号匹不匹配、浏览器的前进后退、程序的函数调用……这些日常开发中经常碰到的问题。

读完这篇文章,希望你能手写一个自己的栈,更希望下次遇到“后进先出”的场景时,能自然而然地想到:哦,这个用栈就好了。
栈是什么
你可以把栈想象成一个只有一端开口的盒子,或者一摞盘子。放东西进去(push)只能从开口放,拿东西出来(pop)也只能从同一个开口拿,所以最后放进去的那个,永远是最先被拿出来的。这就是栈最核心的规则:后进先出(LIFO)。

现实里这样的例子很多:浏览器的“后退”按钮,最后点开的网页最先关掉;程序的“撤销”功能,最后做的操作最先被撤销;还有代码里的括号匹配,遇到左括号就压进栈,遇到右括号就弹出栈顶来配对——完美用上了“后来居上”的逻辑。在代码中,栈就是一组严格遵循这个规则的数据结构,虽然简单,却很实用。

使用步骤

下面展示一个题目:

题目描述

请你实现一个栈(stack),支持如下操作:

  • push(x):向栈中加入一个数 xxx。
  • pop():将栈顶弹出。如果此时栈为空则不进行弹出操作,输出 Empty。
  • query():输出栈顶元素,如果此时栈为空则输出 Anguei!。
  • size():输出此时栈内元素个数。

输入格式

本题单测试点内有多组数据。
输入第一行是一个整数 TTT,表示数据组数。对于每组数据,格式如下:
每组数据第一行是一个整数,表示操作的次数 nnn。
接下来 nnn 行,每行首先由一个字符串,为 push,pop,query 和 size 之一。若为 push,则其后有一个整数 xxx,表示要被加入的数,xxx 和字符串之间用空格隔开;若不是 push,则本行没有其它内容。

输出格式

对于每组数据,按照「题目描述」中的要求依次输出。每次输出占一行。

输入输出样例 #1

输入 #1

2
5
push 2
query
size
pop
query
3
pop
query
size

输出 #1

2
1
Anguei!
Empty
Anguei!
0

说明/提示

样例 1 解释

对于第二组数据,始终为空,所以 pop 和 query 均需要输出对应字符串。栈的 size 为 0。

数据规模与约定

对于全部的测试点,保证 1≤T,n≤1061 \\leq T, n\\leq 10^61≤T,n≤106,且单个测试点内的 nnn 之和不超过 10610^6106,即 ∑n≤106\\sum n \\leq 10^6∑n≤106。保证 0≤x<2640 \\leq x \\lt 2^{64}0≤x<264。

提示

  • 请注意大量数据读入对程序效率造成的影响。
  • 请注意输出的 Empty 不含叹号,Anguei! 含有叹号。

代码实现

C++ 实现

#include<iostream>
#include<string>
using namespace std;

int main(){
ios::sync_with_stdio(false); // 关闭C和C++的IO同步,加速输入输出
cin.tie(0); // 解绑cin和cout,进一步提速
int n;
cin >> n;
unsigned long long A[1000005]; // 数组模拟栈,最大容量1e6+5
int cnt = 0; // 栈中元素个数,也是下一次push的下标
for(int i = 0;i < n;i++){ // 遍历每个测试用例
cnt = 0; // 每个新测试用例重置栈
int a1;
cin >> a1;
for(int j = 0;j < a1;j++){
string s1;
cin >> s1;
if(s1 == "push"){
unsigned long long t;
cin >> t;
A[cnt++] = t; // 入栈:赋值后cnt自增
}
else if(s1 == "pop"){
if(cnt == 0){
cout << "Empty" << '\\n';
}
else{
cnt—; // 逻辑删除栈顶,无需擦除数据
}
}
else if(s1 == "query"){
if(cnt == 0){
cout << "Anguei!" << '\\n';
}
else{
cout << A[cnt – 1] << '\\n'; // 输出栈顶元素
}
}
else if(s1 == "size"){
cout << cnt << '\\n'; // 输出当前栈的大小
}
}
}
return 0;
}

关键步骤说明

  • 数据结构选择:
    C++ 使用 std::stack 容器
    额外维护 stackSize 变量,避免频繁调用 size() 方法(C++ 的 std::stack::size() 是 O(1))

  • 输入输出优化:

    • C++ 使用 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 提高 IO 效率
  • 边界条件处理:

    • 在 pop() 和 query() 方法中检查栈是否为空
    • 严格按照题目要求输出 “Empty”(无叹号)和 “Anguei!”(有叹号)
  • 时间复杂度:

    • 所有操作的时间复杂度均为 O(1)
    • 空间复杂度为 O(n),其中 n 为栈中元素数量
  • 数据范围处理:

    • 使用 unsigned long long(C++)支持 0≤x<2640 \\leq x \\lt 2^{64}0≤x<264 的范围
  • 栈的说明
    1. 定义与特点
    栈是一种操作受限的线性数据结构,只允许在同一端(称为栈顶)进行插入和删除操作。
    其核心特性是 后进先出(LIFO,Last In First Out)——最后放入栈中的元素最先被取出。

    2. 基本操作(概念描述)
    入栈:将一个元素放到栈的顶部。

    出栈:移除栈顶的元素(通常不返回该元素的值)。

    查看栈顶:获取当前栈顶元素的值,但不移除它。

    判空:检查栈中是否没有任何元素。

    获取大小:返回栈中当前存储的元素个数。

    以上所有操作的时间复杂度均为 O(1)(常数时间)。

    3. 使用前的注意事项
    栈空时不能执行出栈或查看栈顶操作,否则会导致错误(如程序崩溃、未定义行为或异常)。执行这些操作前必须先判空。

    栈的容量可能是有限的(尤其是在静态数组模拟时),需要防止因连续入栈导致溢出。

    多个独立测试用例场景下,记得在每个用例开始时清空栈(重置栈顶指针)。

    4. 典型应用场景
    程序函数调用:系统用调用栈管理函数返回值、局部变量及返回地址。

    括号匹配:检查表达式中的括号是否成对且嵌套正确。

    表达式求值:中缀表达式转后缀表达式,以及后缀表达式的计算。

    撤销/恢复(Undo/Redo):每次操作被压入栈,撤销时弹出。

    深度优先搜索(DFS):显式使用栈替代递归,避免递归过深。

    浏览器后退按钮:访问的页面依次入栈,后退时弹出当前页。

    5. 栈的两种常见实现方式对比
    基于数组(顺序栈)

    优点:访问快,内存连续,额外开销小。

    缺点:需预先指定最大容量,可能造成空间浪费或溢出。

    基于链表(链式栈)

    优点:理论上大小无上限(受限于内存),不会溢出。

    缺点:每个元素需要额外存储指针,内存占用稍大,访问速度略慢。

    两种实现的基本操作均能保持 O(1) 的时间复杂度。

    6. 性能优化建议
    若频繁获取栈的大小,最好手动维护一个计数器(入栈时加一,出栈时减一),避免每次调用可能存在的低效实现。

    在需要高性能的场合(如算法竞赛),优先选用数组模拟栈,并关闭输入输出的同步以提高整体速度。

    对于栈顶元素的访问,确保在判空之后进行,以免产生不可预料的后果。

    7. 常见错误与避免方法
    当使用栈时常见错误有:
    1) 访问到无效数据或崩溃,原因是栈空时执行出栈或查看栈顶,解决方法为操作前总是调用判空函数;
    2) 栈不再接受新元素(溢出),原因是数组模拟时超过预设容量,解决方法为预估最大需要,或改用链式栈;
    3) 多用例间数据错乱,原因是未重置栈顶指针,解决方法为每个用例开始前清空栈;
    4) 获取的大小不准确,原因是未手动维护计数器而每次调用遍历计数,解决方法为自行维护独立大小变量。

    总结

    栈是一种后进先出(LIFO)的线性数据结构,所有操作(入栈、出栈、查看栈顶、判空、取大小)均可实现 O(1) 时间复杂度。实际使用中,可选择 C++ 的 std::stack 或 Python 的列表,但在性能敏感场景(如算法竞赛)下,推荐使用数组加下标手动模拟栈,并关闭输入输出同步以进一步提升速度。

    核心注意事项:

    1) 执行出栈或查看栈顶前必须判空,否则会导致未定义行为或程序崩溃。

    2) 数组模拟栈需预先估算最大容量并检查溢出,必要时改用链式栈。

    3) 多测试用例环境里,每个用例开始前须重置栈顶指针(如 top = 0)。

    4) 频繁获取栈大小时,应手动维护一个计数变量(入栈加一,出栈减一),避免调用可能低效的 size() 方法。

    常见错误及处理方式:

    空栈操作 → 操作前总是判空。

    栈溢出 → 预估最大容量或改用链式栈。

    多用例数据错乱 → 每个用例开头清空栈。

    获取的大小不准确 → 自行维护独立大小变量。

    典型应用: 函数调用栈、括号匹配、表达式求值、撤销操作、深度优先搜索等。

    一句话原则: 牢记 LIFO,先判空再操作,手动维护大小,用后及时重置。

    赞(0)
    未经允许不得转载:171主机测评 » 栈的奥秘:从基础到实战
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址