[剣指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の先端にあり、直接イジェクトすることができる.
コード#コード#
/*--------------------------------------- *   :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;
}