线性数据结构题解——栈，队列，单调栈，单调队列，优先队列（我也认为是线性了）

栈

例题1

链接：https://ac.nowcoder.com/acm/contest/22669/A

来源：牛客网

给你一个1->n的排列和一个栈，入栈顺序给定，你要在不打乱入栈顺序的情况下，对数组进行从大到小排序 当无法完全排序时，请输出字典序最大的出栈序列。

ac代码：

	#include <iostream>
	#include <stack>
	using namespace std;
	int a[1000010];
	int maxn[1000010];
	stack<int> st;

    int main(int argc, const char * argv[]) {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }

        maxn[n] = a[n];
        for(int i = n - 1; i >= 1 ; i--){
            maxn[i] = max(maxn[i + 1], a[i] );
        }

        for(int i = 1; i <= n; i++){
            st.push(a[i]);
            while(!st.empty() && st.top() > maxn[i + 1]){
                cout << st.top() << " ";
                st.pop();
            }
        }
        while(!st.empty() ){
            cout << st.top() << " ";
            st.pop();
        }
        return 0;
    }

这道题有个特性，每次输出的元素有两种可能性，1： 栈顶的元素 2：还没有入栈的元素。

题目要求字典序最大，也就是每次出栈的元素最大。于是便要判断如何使出栈的元素尽可能大。 可能性1每次只要O(1) 的时间就能访问。而可能性2需要维护一个后缀最大数组， 这样2也能在O（1）内访问了。

自己做的逻辑有很大的问题，于是WA或者TLE了好几次。

例题2 牛牛与后缀表达式

链接：https://ac.nowcoder.com/acm/contest/22669/B 来源：牛客网

给定牛牛一个后缀表达式s，计算它的结果，例如，1+1对应的后缀表达式为1#1#+，‘#’作为操作数的结束符号。 其中，表达式中只含有‘+’、’-‘、’*‘三种运算，不包含除法。 本题保证表达式一定合法，且计算过程和计算结果的绝对值一定不会超过.