栈
1.介绍
栈的特点是“先进先出”，与队列不同，栈只有唯一的一个出入口。
编程中常用的递归就是用栈实现的。栈需要用空间存储，如果栈的深度太大，或者存进 栈的数组太大，那么总数会超过系统为栈分配的空间，就会爆栈导致栈溢出。
编码时通常使用STL stack或者自己手搓。
2. STL stack
| 操作 |
说明 |
stack<Type> s |
定义栈，Type 为数据类型 |
s.push(item) |
把item放到栈顶 |
s.top() |
返回栈顶的元素，不会删除 |
s.pop() |
删除栈顶的元素，但不会返回 |
s.size() |
返回栈中元素的个数 |
s.empty |
检查栈是否为空，如果为空则返回true，反之返回false |
3.手写栈
自己写一个简单的栈。包括一些基本操作：push(),pop(),top(),empty()
1
2
3
4
5
6
7
8
9
10
11
| #include<bits/stdc++.h>
const int N = 100100;
struct mystack{
char a[N];
int t = 0;
void push(char x){a[t++]=x;}
char top(){return a[t-1];}
void pop(){t--;}
int empty() {return t==0 ? 1 : 0;}
}
|
4.单调栈
单调栈本质上也是栈，但是满足特点是：栈内的元素是单调递增或单调递减的，可以用于处理比较问题
如何使栈保持单调？例如，一个单调递减栈，从栈顶到栈底是从小到大的顺序。当一个数入栈时，与栈顶比较，若比栈顶小，则入栈；若比栈顶大，则栈顶出栈，直到比栈顶元素小或栈为空为止
例题： 向右看齐
题解：从后往前遍历奶牛，并用一个栈保存从低到高的奶牛，栈顶奶牛最矮，栈底最高；
具体操作如下：遍历到奶牛i时，与栈顶奶牛比较，如果栈顶不比奶牛i高，就出栈，直到栈顶奶牛比奶牛i高或者栈为空为止，此时栈顶奶牛就是奶牛i的仰望对象，栈为空仰望对象就是0；然后把奶牛i放入栈中，此时栈仍然保持单调。
每头奶牛只进出栈一次，遍历一遍，时间复杂度O(n)
下面用STL stack和手写栈进行编码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc+.h>
using namespace std;
int h[100001],ans[100001];
int main()
{
int n;
scanf("%d",&n);
for(int i= 1;i<= n;i++) scanf("%d",&h[i]);
stack<int> st;
for(int i=n ; i >= 1; i--){
while(!st.empty() && h[st.top()]<= h[i]){
st.pop();
}
if(st.empty()) ans[i] = 0;
else ans[i] = st.top();
st.push(i);
}
for(int i = 1; i<=n; i++)printf("%d\n",ans[i]);
return 0;
}
|
手写栈代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<bits/stdc+.h>
using namespace std;
const int N = 100100;
struct mystack{
int a[N];
int t =0;
void push(int x){a[t++] = x;}
int top(){return a[t-1];}
void pop(){t--;}
int empty(){return t==0 ? 1 : 0;}
}st;
int h[N],ans[N];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i<=n ;i++){scanf("%d",&h[i]);}
for(int i=n; i>=1; i--){
while(!st.empty() && h[st.top()] <= h[i])
st.pop();
if(st.empty()) ans[i] = 0;
else ans[i] = st.top();
st.push(i);
}
for(int i = 1; i <= n; i++)printf("%d\n",ans[i]);
return 0;
}
|
wechat
alipay