剣指OFFERの2つのスタックでキューを実現する(九度OJ 1512)

タイトルの説明:

2つのスタックで1つのキューを実現し、キューのPushとPop操作を完了します.キュー内の要素はintタイプです.
 

入力:

各入力ファイルには、テストサンプルが含まれています.各テストサンプルについて、最初の行には、キュー操作の個数を表すn(1<=n<=10000000)が入力される.次のn行、各行にキュー操作を入力:1.PUSH Xはキュー内のpushの整数x(x>=0)2.POPがキューからpopする数.
 

出力:

各テストケースに対応して、すべてのpop操作のキューpopからの数値を印刷します.pop操作時にキューが空の場合、-1を印刷します.

サンプル入力:

3
PUSH 10
POP
POP

サンプル出力:

10
-1

 

問題解決の考え方：

まず,問題要求は,2つのスタックがキューを表す.では、2つのスタックを使ったほうがいいですね.OJがどのように検出したのか分かりませんが、1つのキューではだめです.
では、ハンノタワーを思い出します.スタック自体は後進後出で、列は先進先出です.どうやってデザインしますか?
2つのスタックを使用して、最初のスタックはPUSHに使用され、2番目のスタックはPOPに使用されます.
注意すべき問題は、2つのスタックの間のあちこちの要素の順序が乱れてはいけないことです.スタック2に要素が存在する限り、スタック1はスタック2に要素を圧縮することはできない.たとえば
スタック1の新しい要素3
スタック2の要素は2 1であり、
2つのスタックのリストは次のとおりです.

3
2 1

この場合、スタックを出る順序は

1 2 3

このときスタック1をスタック2に押し込むと、スタックを出る順番が

3 1 2

したがって、スタック2内の要素が空であることを保証し、スタック2内にスタック1の要素を押し込むことは禁物である.

コード:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#define MAX 100001
int stack1[MAX],stack2[MAX],top1,top2;
int main(void){
    int n,i,m;
    char input1[10];
    while(scanf("%d",&n)!=EOF && n<=100000 && n>= 1){
        top1 = top2 = 0;
        memset(&stack1,0,sizeof(int)*MAX);
        memset(&stack2,0,sizeof(int)*MAX);
        for(i=0;i<n;i++){
            scanf("%s",input1);
            if(strcmp(input1,"PUSH") == 0){
                scanf("%d",&m);
                stack1[top1++] = m;
            }else{
                if(top2 == 0){// 2 
                    while(top1){
                        stack2[top2++] = stack1[--top1];
                    }
                }
                if(top2)// 2 ， ， ， 
                    printf("%d
",stack2[--top2]);
                else{
                    printf("-1
");
                }
            }
        }
    }
    return 0;
}