当前位置：首页 > news >正文

【算法竞赛】栈

news 2024/11/14 13:47:43

栈的特点是"先进后出"。

栈在生活中的原型有:坐电梯,先进电梯的被挤在最里面,只能最后出来；一管泡腾片,最先放进管子的药片位于最底层，最后被拿出来。
栈只有唯一的出入口,从这个口进入,也从这个口弹出,这是它与队列最大的区别。
队列有一个入口和一个出口,所以手写栈比手写队列更简单。

编程中常用的递归就是用栈来实现的。栈需要用空间存储,如果栈的深度太大,或者存进栈的数组太大,那么总数会超过系统为栈分配的空间,就会爆栈导致栈溢出。这是递归的主要问题,递归深度要注意。

编码时通常直接用STL stack,或者自己手写找。为避免爆栈,需要控制栈的大小。

STL stack（栈）

STL stack的有关操作如表1.2所示.
在这里插入图片描述
下面用一道例题说明栈的应用：

代码如下,其中用到了栈的多个操作

#include<bits/stdc++.h>
using namespace std;int main() 
{int n;scanf("%d", &n);getchar();while (n--) {stack<char> s;while (true) {char ch = getchar();if (ch == ' ' || ch == '\n' || ch == EOF) {while (!s.empty()) {printf("%c", s.top());s.pop();}printf("");if (ch == '\n' || ch == EOF) break;} else{s.push(ch);}printf("\n");}}return 0;
}

手写栈

手写栈代码简单且节省空间.
下面针对例题,自己写一个简单的栈.代码中包括栈的基本操作:push()、pop()、top()、empty().用t指向栈顶.

#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];}void pop() {t--; }int empty() { return t==0?1:0;}
}st;int main()
{int n;scanf("%d", &n);getchar();while(n--){while(true) {char ch = getchar();if(ch=='.' || ch=='\n' || ch==EOF) {while(!st.empty()){printf("%c", st.top());st.pop();}if(ch=='\n' || ch==EOF) break;printf("");}else st.push(ch);printf("\n");}}return 0;
}

单调栈

单调栈不是一种新的栈结构,它在结构上仍然是一个普通的栈,它是栈的一种使用方式。

单调栈内的元素是单调递增或递减的,有单调递增栈、单调递减栈。单调栈可以用来处
理比较问题。

单调栈实际上就是普通的栈,只是使用时始终保持栈内的元素是单调的。例如,单调递
减栈从栈顶到栈底是从小到大的顺序。当一个数入栈时,与栈顶比较,若比栈顶小,则入栈;若比栈顶大,则弹出栈顶,直到这个数能入栈为止。注意,每个数都一定入栈。

单调栈比单调队列简单,因为栈只有一个出入口。
用下面的例题说明单调栈的简单应用。

例1.6
在这里插入图片描述
题解：
从后向前遍历奶牛,并用一个栈保存从低到高的奶牛,栈顶的奶牛最矮,栈底的最高。

具体操作:遍历到奶牛i时,将栈顶的奶牛与其进行比较,如果不比奶牛i高,就弹出栈顶,直到栈顶的奶牛比奶牛i高,这就是奶牛i的仰望对象;然后把i放进栈顶,找中的奶牛仍然保持从低到高。
每头奶牛只进出栈一次,所以复杂度为O(n)。

STL stack代码如下：

#include <iostream>
#include <stack>
using namespace std;int main() 
{int n;scanf("%d", &n);int h[1005];for (int i = 1; i <= n; i++) scanf("%d", &h[i]);stack<int> st;int ans[1005];for (int i = n; i >= 1; i--) {while (!st.empty() && h[st.top()] <= h[i]) {if (!st.empty()) st.pop();}ans[i] = st.empty()? 0 : st.top();st.push(i);}for (int i = 1; i <= n; i++) printf("%d ", ans[i]);return 0;
}