栈的特点是"先进后出"。
栈在生活中的原型有:坐电梯,先进电梯的被挤在最里面,只能最后出来；一管泡腾片,最先放进管子的药片位于最底层，最后被拿出来。
栈只有唯一的出入口,从这个口进入,也从这个口弹出,这是它与队列最大的区别。
队列有一个入口和一个出口,所以手写栈比手写队列更简单。
编程中常用的递归就是用栈来实现的。栈需要用空间存储,如果栈的深度太大,或者存进栈的数组太大,那么总数会超过系统为栈分配的空间,就会爆栈导致栈溢出。这是递归的主要问题,递归深度要注意。
编码时通常直接用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;
}
