【9度oj】1512キューを2つのスタックで実現

原題リンク:http://ac.jobdu.com/problem.php?pid=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を印刷します.
 
アルゴリズムの説明:
多くの人の考えは、s 1を常に記憶空間として維持し、s 2を一時バッファとすることである.
(1)エンキュー時にs 1に要素を押し込む.
(2)デキュー時には、s 1の要素を1つずつ(ポップアップして押し込む)s 2、s 2のトップ要素をポップアップしてデキュー要素とし、その後、s 2の残りの要素を1つずつs 1に戻す.
上記の考え方は,実行可能性は疑いの余地がない.しかし、最適化できる詳細があります.すなわち、デキュー時にs 1の要素を1つずつs 2に「注ぐ」場合、元のs 1スタックの底にある要素は、s 2を「注ぐ」ことなく(すなわち、s 1.Count()-1個のみ)、直接デキュー要素としてポップアップして返すことができる.これにより、一次スタックの動作を低減することができる.  上記の考え方では、いくつかの変種があります.例えば、チームに入るとき、まずs 1が空であるかどうかを判断し、空でない場合は、すべての要素がs 1にあることを説明します.このとき、チームに入る要素を直接s 1に押し込みます.空の場合、s 2の要素を1つずつs 1に戻し、キュー要素に押し込みます.チームを出るときは、まずs 2が空であるかどうかを判断し、空でない場合は、s 2のトップ要素を直接ポップアップしてチームを出ます.空の場合は、s 1の要素を1つずつs 2に「注ぐ」と、最後の要素をポップアップしてキューから出ます.大衆の方法と変種を同時に考えることができる人もいるが、頭がいいと言うべきだ.  本当に性能が高いのは、実は別の変種です.すなわち、エンキュー時にs 1に要素を押し込む.デキュー時にs 2が空かどうかを判断し、空でなければトップ要素を直接ポップアップする.空の場合、s 1の要素を1つずつs 2に「注ぐ」と、最後の要素をポップアップしてキューから出ます.この考え方は,スタックの「逆」を繰り返すことを避け,必要に応じて一度だけ「逆」にする.これに基づいて実装されるコードは以下の通りである.

#include <stdio.h>
#include <stack>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int main()
{
	int n,pushn;
	string op;
	stack<int> s1;
	stack<int> s2;
	scanf("%d",&n);
	while(n>0)
	{
		cin >> op;
		if(op == "PUSH")
		{
			scanf("%d",&pushn);
			s1.push(pushn);
		}
        else if(op == "POP")
		{
			if(s2.empty())
			{	
				if(s1.empty()) printf("-1
");
				else{
					
					int k = s1.size();
					int popn;
					while(k > 0)
					{
						s2.push(s1.top());
						s1.pop();
						k--;
					}
					printf("%d
",s2.top());
					s2.pop();
				}
			}
            else
            {
				printf("%d
",s2.top());
				s2.pop();
			}
		}
		n--;
	}
	return 0;
}