数据结构--栈

线性表的定义

前面文章有讲过，线性表就是一次保存单个同类型元素，多个元素之间逻辑上连续
例子：数组，栈，队列，字符串

栈

1.1 栈和队列的特点

栈和队列都是操作受限的线性表。
前面学过的数组，链表，是可以菜任意位置插入和删除的
而栈和队列只能在一端插入元素和删除元素

1.2 栈的定义

只能在一端插入元素（栈顶），也只能从这一端取出元素（栈顶）

先看下入栈的动画：

再看下出栈的动画：

利用数组模拟栈，每次入栈从数组后面追加，数组开头是栈底，数组末尾为栈顶。

模拟实现栈思路

1、定义

定义stk[N]栈 top 为栈顶 因为栈是一种先进后出的结构。

2、实现初始化

top=-1对栈进行初始化，表示空

3、实现压栈和出栈

压栈 需要++top 然后读入即可 stk[++top]=x
出栈 只需 --top

4、判断栈是否为空

只要top>0栈就不为空
栈顶stk[top]

#include <iostream>using namespace std;const int N = 100010;// stk[N] 为栈， tt 为栈顶下标
int stk[N], tt;// 插入一个数, 栈顶++
stk[ ++ tt] = x;// 弹出
tt --;// 判断栈是否为空
if(tt > 0) not empty
else empty// 栈顶
stk[tt];

Acwing 828

#include <iostream>using namespace std;const int N = 100010;int m;
int stk[N], top;int main()
{cin >> m;while(m --){string op;int x;cin >> op;if(op == "push"){cin >> x;stk[ ++ top] = x;}else if(op == "pop"){-- top;}else if(op == "empty"){//如果top>0 则输出no 否则输出yescout << (top ? "NO" : "YES") << endl;}else{cout << stk[top] << endl;}}return 0;
}

Acwing 830 单调栈

#include <iostream>using namespace std;const int N = 100010;int n;
int stk[N], tt;int main()
{cin >> n;for(int i = 0; i < n; i ++){int x;cin >> x;while(tt && stk[tt] >= x) tt --;if(tt) cout << stk[tt] << ' ';else cout << -1 << ' ';stk[++ tt] = x;}return 0;
}

时间复杂度

每个数只会进栈一次，出栈一次，整个时间复杂度是O(n)。

总结

学数据结构 最主要的还是要画图，先画一遍，代码自然就能够写了