文章目录
• 前言
• 一、关于栈
• 二、栈的操作
• 1.数组模拟栈必备属性
• 2.把x插入到栈顶
• 3.把栈顶元素弹出
• 4.判断栈是否为空
• 5.查询栈顶元素
• 三、例题，代码
• AcWing 828. 模拟栈
• AC代码
• 四、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：用数组模拟栈，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上
一、关于栈
在C++中，STL已经帮助我们实现了栈，详见：STL—stack，本篇博客中，讲解如何用数组去模拟栈，实现栈的一些功能.
二、栈的操作
1.数组模拟栈必备属性
int st[N]; //st数组中存储的就是栈的元素 int tt; //tt初始值为0，代表栈中没有任何一个元素
2.把x插入到栈顶
st[ ++ tt ] = x; //先把tt往后移动一个位置，然后把x赋值到st数组中
3.把栈顶元素弹出
tt代表的就是栈顶的元素坐标，所以我们只需要
tt --;
4.判断栈是否为空
if (tt == 0) printf("栈为空"); else printf("栈不为空");
5.查询栈顶元素
printf("%d", st[tt]); //tt代表的就是栈顶元素
三、例题，代码
AcWing 828. 模拟栈
本题链接：AcWing 828. 模拟栈
本博客给出本题截图：
AC代码
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N = 100010; int st[N], tt; int main() { int n; scanf("%d", &n); while (n -- ) { string a; cin >> a; if (a == "push") { int x; scanf("%d", &x); st[ ++ tt ] = x; } else if (a == "pop") tt --; else if (a == "empty") { if (tt == 0) printf("YES\n"); else printf("NO\n"); } else printf("%d\n", st[tt]); } return 0; }
四、时间复杂度
关于数组模拟栈的各操作时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
