笔记·栈

userId_undefined
AAA_Cheer_EndBet
时间刺客空间掌握者时空双修者出道萌新快乐小狗秩序白银

2026-06-29 18:41:09

发布于：云南

0阅读
0回复
0点赞

栈

一、什么是栈

栈是一种先进后出（Last In First Out，LIFO）的线性数据结构。就像一摞盘子，后放上去的盘子先被拿走，先放上去的盘子后被拿走。

核心操作：

  • 入栈（push）：在栈顶添加元素
  • 出栈（pop）：移除栈顶元素
  • 取栈顶（top）：查看栈顶元素但不移除
  • 判空（empty）：判断栈是否为空
  • 获取大小（size）：获取栈中元素个数

二、栈的两种实现方式

1. 数组实现栈（静态栈）

原理：用数组存储元素，用一个变量top指向栈顶位置。top初始为0表示空栈，入栈时先top++再赋值，出栈时top--。

优点：简单高效，访问速度快
缺点：大小固定，不能动态扩展

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],top;
int main() {
    top=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            if(top<MAXN-5) {
                stk[++top]=x;
                printf("入栈成功：%d\n",x);
            } else {
                printf("栈已满\n");
            }
        } else if(op==2) {
            if(top>0) {
                printf("出栈元素：%d\n",stk[top--]);
            } else {
                printf("栈为空\n");
            }
        } else if(op==3) {
            if(top>0) {
                printf("栈顶元素：%d\n",stk[top]);
            } else {
                printf("栈为空\n");
            }
        } else if(op==4) {
            printf("栈中元素个数：%d\n",top);
        } else if(op==5) {
            printf("栈是否为空：%s\n",top==0?"是":"否");
        }
    }
    return 0;
}

2. STL栈（标准模板库）

C++的STL提供了现成的栈容器，方便使用。

#include <bits/stdc++.h>
using namespace std;
stack<int> st;
int main() {
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            st.push(x);
            printf("入栈成功：%d\n",x);
        } else if(op==2) {
            if(!st.empty()) {
                printf("出栈元素：%d\n",st.top());
                st.pop();
            } else {
                printf("栈为空\n");
            }
        } else if(op==3) {
            if(!st.empty()) {
                printf("栈顶元素：%d\n",st.top());
            } else {
                printf("栈为空\n");
            }
        } else if(op==4) {
            printf("栈中元素个数：%d\n",st.size());
        } else if(op==5) {
            printf("栈是否为空：%s\n",st.empty()?"是":"否");
        }
    }
    return 0;
}

三、栈的经典应用

1. 括号匹配

原理：遍历字符串，遇到左括号入栈，遇到右括号则检查栈顶是否是对应的左括号。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char stk[MAXN],s[MAXN];
int top;
int main() {
    scanf("%s",s+1);
    int len=strlen(s+1);
    top=0;
    int flag=1;
    for(int i=1;i<=len;i++) {
        if(s[i]=='('||s[i]=='['||s[i]=='{') {
            stk[++top]=s[i];
        } else if(s[i]==')') {
            if(top>0&&stk[top]=='(') {
                top--;
            } else {
                flag=0;
                break;
            }
        } else if(s[i]==']') {
            if(top>0&&stk[top]=='[') {
                top--;
            } else {
                flag=0;
                break;
            }
        } else if(s[i]=='}') {
            if(top>0&&stk[top]=='{') {
                top--;
            } else {
                flag=0;
                break;
            }
        }
    }
    if(flag&&top==0) {
        printf("括号匹配正确\n");
    } else {
        printf("括号匹配错误\n");
    }
    return 0;
}

2. 表达式求值（中缀转后缀）

原理：利用栈的优先级比较，将中缀表达式转换为后缀表达式再求值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char stk[MAXN],s[MAXN];
int top;
int getPri(char c) {
    if(c=='*'||c=='/') return 2;
    if(c=='+'||c=='-') return 1;
    return 0;
}
int main() {
    scanf("%s",s+1);
    int len=strlen(s+1);
    top=0;
    for(int i=1;i<=len;i++) {
        if(s[i]>='0'&&s[i]<='9') {
            printf("%c",s[i]);
        } else if(s[i]=='(') {
            stk[++top]=s[i];
        } else if(s[i]==')') {
            while(top>0&&stk[top]!='(') {
                printf("%c",stk[top--]);
            }
            if(top>0) top--;
        } else {
            while(top>0&&getPri(stk[top])>=getPri(s[i])) {
                printf("%c",stk[top--]);
            }
            stk[++top]=s[i];
        }
    }
    while(top>0) {
        printf("%c",stk[top--]);
    }
    printf("\n");
    return 0;
}

3. 单调栈（求下一个更大元素）

原理：维护一个单调递减的栈，当前元素比栈顶大时，栈顶的下一个更大元素就是当前元素。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],ans[MAXN],stk[MAXN];
int top;
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    top=0;
    for(int i=n;i>=1;i--) {
        while(top>0&&a[stk[top]]<=a[i]) {
            top--;
        }
        if(top>0) {
            ans[i]=a[stk[top]];
        } else {
            ans[i]=-1;
        }
        stk[++top]=i;
    }
    for(int i=1;i<=n;i++) {
        printf("%d ",ans[i]);
    }
    printf("\n");
    return 0;
}

4. 模拟递归（DFS）

栈可以用来模拟递归调用，避免递归深度过大的问题。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
struct Node {
    int x,y,step;
};
Node stk[MAXN];
int top;
int main() {
    int n,start;
    scanf("%d %d",&n,&start);
    top=0;
    stk[++top]={start,0,1};
    while(top>0) {
        Node cur=stk[top--];
        printf("%d ",cur.x);
        if(cur.x*2<=n) {
            stk[++top]={cur.x*2,cur.y+1,cur.step+1};
        }
        if(cur.x+1<=n) {
            stk[++top]={cur.x+1,cur.y+1,cur.step+1};
        }
    }
    printf("\n");
    return 0;
}

四、栈的常见题型

1. 最小栈

设计一个栈，支持push、pop、top和getMin操作，getMin能在O(1)时间返回最小值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],minStk[MAXN];
int top,minTop;
int main() {
    top=0;
    minTop=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            stk[++top]=x;
            if(minTop==0||x<=minStk[minTop]) {
                minStk[++minTop]=x;
            }
        } else if(op==2) {
            if(top>0) {
                if(stk[top]==minStk[minTop]) {
                    minTop--;
                }
                printf("出栈：%d\n",stk[top--]);
            }
        } else if(op==3) {
            if(top>0) {
                printf("栈顶：%d\n",stk[top]);
            }
        } else if(op==4) {
            if(minTop>0) {
                printf("最小值：%d\n",minStk[minTop]);
            }
        }
    }
    return 0;
}

2. 栈排序

使用辅助栈对栈进行排序。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],tmpStk[MAXN];
int top,tmpTop;
int main() {
    top=0;
    tmpTop=0;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        while(top>0&&stk[top]>x) {
            tmpStk[++tmpTop]=stk[top--];
        }
        stk[++top]=x;
        while(tmpTop>0) {
            stk[++top]=tmpStk[tmpTop--];
        }
    }
    while(top>0) {
        printf("%d ",stk[top--]);
    }
    printf("\n");
    return 0;
}

五、栈的总结

特性 数组实现 STL实现
时间复杂度 O(1) O(1)
空间限制 固定大小 动态扩展
操作直观 需要手动管理 封装完善
适用场景 已知最大大小 大小不确定

栈的核心思想：

  1. 先进后出是根本特性
  2. 递归本质上就是栈的应用
  3. 适用于需要回溯的场景
  4. 常用于深度优先搜索（DFS）
  5. 表达式求值、括号匹配等是经典应用

注意事项：

  1. 使用数组实现时注意栈溢出（top超过MAXN）
  2. 出栈前检查栈是否为空
  3. 递归深度过大时考虑用栈模拟
  4. 栈擅长处理具有嵌套结构的数据
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论