【剣指Offer面接プログラミング問題】タイトル1512:2つのスタックでキューを実現--9度OJ


タイトルの説明:
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

【解題の考え方】新規スタックst 1シミュレーションキューの入力は、push操作に遭遇すると、要素をst 1に押し込む.また、新しいスタックst 2はキューの出力をシミュレートし、pop操作時にst 1が空であるかどうかを判断し、st 2が空である場合、st 1のすべての要素を1つずつポップアップしてst 2に押し込んで出力に備える.このときのst 2の要素の配列は、現在のすべての要素の入力の逆順序であり、キューの出力順序に合致する.-->
pop操作が発生した場合、st 2が空でなければ、このときのスタックトップ要素は現在の状態のキューのヘッダ要素であることが好ましく、スタックトップ要素はキューの出力として直接ポップアップされる.
AC code:
#include 
#include 
using namespace std;
 
int main()
{
  int n;
  scanf("%d",&n);
  stack st1,st2;
  for(int i=0;i

タイトルリンク:http://ac.jobdu.com/problem.php?pid=1512