【剣指Offer面接プログラミング問題】タイトル1512:2つのスタックでキューを実現--9度OJ
1352 ワード
タイトルの説明:
2つのスタックで1つのキューを実現し、キューのPushとPop操作を完了します.キュー内の要素はintタイプです.
入力:
各入力ファイルには、テストサンプルが含まれています.各テストサンプルについて、最初の行には、キュー操作の個数を表すn(1<=n<=10000000)が入力される.次のn行、各行にキュー操作を入力:1.PUSH Xはキュー内のpushの整数x(x>=0)2.POPがキューからpopする数.
出力:
各テストケースに対応して、すべてのpop操作のキューpopからの数値を印刷します.pop操作を実行するときにキューが空の場合は、-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:
タイトルリンク: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を印刷します.
サンプル入力:
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