<>--キュー内で最大値をとる操作の問題

プログラミングの美しさは良い本だと言わざるを得ません.acmを作る過程で多くの問題に遭遇したことがありますが、考えるべきところはたくさんあります.
これは今日プログラミングの美しさで見た問題で、スタックがキューに変換されることについて考えています.
通常はc++内の関数ライブラリのスタックとキューに依存しすぎますが、彼らの拡張には手書きスタックとキューを自分で行い、より簡単なアルゴリズムを実現する必要があります.
 
テーマ:
3つのアクションを持つキューがあるとします.
1.EnQueue(v):vをキューに入れる
2.DeQueue:キュー内のキューヘッダ要素を削除し、この要素を返します.
3.MaxElement:キュー内の最大要素を返す
MaxElement操作の時間的複雑さをできるだけ低くするデータ構造とアルゴリズムを設計する
 
まず、このような問題を考えてみましょう.
前に知られているシーケンスに対して、要素xを追加すると、現在のシーケンスの最大値が特に容易になります.
maxVal[i] = max(maxVal[i-1] , x);
では、i番目の要素を削除すると、得られるシーケンスの最大値も特に容易にmaxVal[i-1]になります.
角度を変えて考えると、このときのi番目の要素はスタックトップ要素と理解できます.
つまりこの問題を3つのスタック操作を持つキューに変更すると、単位時間でMaxElementを得ることができます.
これらの数を保存することはすべての数をスキャンすることであり、O(N)は解決する.
 
しかし、ここではキューです.キューは常に先頭、つまり下に0と表示されている要素を削除します.これにより、maxVal[i]を使用して現在のキュー要素の最大値を表すことはできません.
 
スタックがこんなに便利である以上、キューをスタックで表す方法を考えることができます.
まず2つのスタックが必要で、データを1つのスタックs 2に入れます.では、これらのデータは実際に逆さまに保存されています.では、キューの最初の要素、つまりスタックの底の要素を削除します.
では、別のスタックs 1を使用して、前のスタックs 2の要素をもう一度別のスタックs 1に戻すことができます.このとき、s 1のスタックトップ、すなわちキューのスタックトップ
すなわち、s 1に要素がある限り、s 1のスタックトップは常にキューヘッダ要素である
s 1の要素が存在しない場合にのみ、s 2の要素を一度にs 1にすべて注ぎ込みます.
int DeQueue(){if(s 1.empty()&&s 2.empty())return-INF;//キューにif(s 1.empty(){while(!s 2.empty(){s 1.push(s 2.pop());            }        }        return s1.pop();    }
キュー内のすべての要素が常にs 1およびs 2に分散すると、最大要素はs 1またはs 2にある可能性があるので、return max(s 1.Max()、s 2を返す.Max());
このようにこのプログラムの全体的な複雑さはO(N)の線形複雑度に達することができる.
次は自分で手書きでテストした問題のないプログラムです

  1 #include <cstdio>

  2 #include <cstring>

  3 #include <exception>

  4 using namespace std;

  5 #define max(a,b) a>b?a:b

  6 const int MAXN = 10005;

  7 const int INF = 0x3fffffff;

  8 struct Stack{

  9     int top , a[MAXN] , maxVal[MAXN];

 10     //a[]       ，maxVal[i]  i        ，top     ，   -1

 11     Stack(){

 12         top = -1;

 13         memset(maxVal , -1 , sizeof(maxVal));

 14     }

 15     void push(int x)

 16     {

 17         if(top>=MAXN) throw exception();

 18         a[++top] = x;

 19         if(top == 0) maxVal[top]=x;

 20         else maxVal[top] = max(maxVal[top-1] , x);

 21     }

 22     bool empty(){return top == -1;}

 23     int Max()

 24     {

 25         if(empty()) return -INF;

 26         return maxVal[top];

 27     }

 28     int pop()

 29     {

 30         if(top<0) return -1;

 31         int ret = a[top--];

 32         return ret;

 33     }

 34 };

 35 

 36 struct Queue{

 37     Stack s1 , s2;

 38     Queue()

 39     {

 40         s1 = Stack();

 41         s2 = Stack();

 42     }

 43     void EnQueue(int x)

 44     {

 45         s2.push(x);

 46     }

 47     int DeQueue()

 48     {

 49         if(s1.empty() && s2.empty()) return -INF; //       

 50         if(s1.empty()){

 51             while(!s2.empty()){

 52                 s1.push(s2.pop());

 53             }

 54         }

 55         return s1.pop();

 56     }

 57     int MaxElement()

 58     {

 59         return max(s1.Max() , s2.Max());

 60     }

 61     bool empty()

 62     {

 63         return s1.empty()&&s2.empty();

 64     }

 65 };

 66 

 67 int main()

 68 {

 69   //  freopen("a.in" , "r" , stdin);

 70     Queue q;

 71 

 72     q = Queue();

 73  //   int num[10] = {5 , 7 , 6 , 3 , 2 , 4 , 9 , 15 , 13 , 11};

 74     q.EnQueue(5);

 75     int op , x;

 76     while(!q.empty())

 77     {

 78         printf("      ：");

 79         scanf("%d" , &op);

 80         if(op == 1){

 81             printf("        ：");

 82             scanf("%d" , &x);

 83             q.EnQueue(x);

 84         }

 85         else if(op == 2){

 86             printf("      %d       
" , q.DeQueue());

 87         }

 88         else{

 89             printf("          %d
" , q.MaxElement());

 90         }

 91         

 92         //                     

 93         /*

 94         printf("   1    
");

 95         for(int i=q.s1.top ; i>=0 ; i--){

 96             printf("%d " , q.s1.a[i]);

 97         }

 98         puts("");

 99 

100         printf("   2    
");

101         for(int i=q.s2.top ; i>=0 ; i--){

102             printf("%d " , q.s2.a[i]);

103         }

104         puts("");

105         */

106     }

107     return 0;

108 }