[剣指Offer]9.2つのスタックでキューを実装
3538 ワード
タイトル
2つのスタックで1つのキューを実現し、キューのPushとPop操作を完了します.キュー内の要素はintタイプです.
構想
スタックでキューをシミュレートします.まず、1つの要素aをstack 1に挿入し、2つの要素bcを押し込みます.このとき、スタックには要素abcがあり、cはスタックの上部にあり、stack 2はまだ空です.要素を削除してみます.キューが先に出る原則に従って、要素aを削除する必要があります.要素aはstack 1に格納され、スタックの上部には存在しないため、直接削除することはできない.stack 2がまだ使用されていないことに気づき、stack 1の要素を1つずつポップアップしてstack 2に押し込み、stack 2の要素はcba、スタックトップの要素はaであり、要素aを直接削除することができます.
stack 2が空でない場合、stack 2のスタックトップ要素は最初にキューに入った要素であり、ポップアップできます.stack 2が空の場合、stack 1の要素を1つずつポップアップしてstack 2に押し込みます.先にキューに入った要素がstakc 1のローエンドに押されるため、イジェクトと圧入を経てstack 2の先端にあり、直接イジェクトすることができる.
コード#コード#
2つのスタックで1つのキューを実現し、キューのPushとPop操作を完了します.キュー内の要素はintタイプです.
構想
スタックでキューをシミュレートします.まず、1つの要素aをstack 1に挿入し、2つの要素bcを押し込みます.このとき、スタックには要素abcがあり、cはスタックの上部にあり、stack 2はまだ空です.要素を削除してみます.キューが先に出る原則に従って、要素aを削除する必要があります.要素aはstack 1に格納され、スタックの上部には存在しないため、直接削除することはできない.stack 2がまだ使用されていないことに気づき、stack 1の要素を1つずつポップアップしてstack 2に押し込み、stack 2の要素はcba、スタックトップの要素はaであり、要素aを直接削除することができます.
stack 2が空でない場合、stack 2のスタックトップ要素は最初にキューに入った要素であり、ポップアップできます.stack 2が空の場合、stack 1の要素を1つずつポップアップしてstack 2に押し込みます.先にキューに入った要素がstakc 1のローエンドに押されるため、イジェクトと圧入を経てstack 2の先端にあり、直接イジェクトすることができる.
コード#コード#
/*--------------------------------------- * :2015-07-20 * :SJF0115 * : 9. * :AC * :http://www.nowcoder.com/books/coding-interviews/54275ddae22f475981afa2244dd448c6?rp=1 * : Offer * : -----------------------------------------*/
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Solution{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()){
if(stack1.empty()){
return -1;
}//if
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}//while
}//while
int num = stack2.top();
stack2.pop();
return num;
}
private:
stack<int> stack1;
stack<int> stack2;
};
int main(){
Solution s;
s.push(1);
s.push(2);
s.push(3);
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
s.push(4);
s.push(5);
cout<<s.pop()<<endl;
s.push(6);
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
return 0;
}