dequeue維護最大值

程式設計之美 -  隊列中取最大值操作問題

假設有這樣一個擁有3個操作的隊列：

    1. EnQueue(v)：将v加入隊列中

    2. DeQueue：使隊列中的對首元素删除并傳回此元素

    3. MaxElement：傳回隊列中的最大(小)元素

    請設計一個資料結構和算法，讓MaxElement操作的時間複雜度盡可能的低。

因為在棧s1外隻要多開一個s2，就可以很友善的維護最大值：

當t壓入s1時，判斷是否大于s2.top，是則壓入s2，

當pop掉s1的值時，判斷s1.top==s2.top，是則s2也pop一個值.

如果能用stack實作queue的基本功能，那問題就解決了。

stack是隻有尾的資料結構，那再開一個stack s，把s1的資料壓入s中，s的top就變成原資料的頭了.

維護下這2個stack的最大值就是原隊列的最大值了.（最小值理同）

```

#include <cstdio>
#include <cstring>
#include <stack>
#include <iostream>
using namespace std;
stack<int> s1, s2, sx1, sx2;
void Push(int v)
{
    s1.push(v);
    if (v>sx1.top()) sx1.push(v);
}
void Pop()
{
    if (s2.empty()){
        while (!s1.empty()){
            int v=s1.top();
            s2.push(v);
            if (v>sx2.top()) sx2.push(v);
            if (v==sx1.top()) sx1.pop();
            s1.pop();
        }
    }
    if (sx2.top()==s2.top()) sx2.pop();
    s2.pop();
}
int Getmx()
{
    return sx1.top()>sx2.top()?sx1.top():sx2.top();
}
int main()
{
    sx1.push(-123123);
    sx2.push(-123123);
    Push(1);
    Push(3);
    cout << Getmx() << endl;
    Pop();
    cout << Getmx() << endl;
    Push(123);
    Push(324);
    Pop();
    cout << Getmx() << endl;
    Pop();
    cout << Getmx() << endl;
    Pop();
    cout << Getmx() << endl;
    return 0;
}
           

```