[剑指Offer]9.用两个栈实现队列

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路

用栈来模拟队列。我们首先插入一个元素a到stack1中，再压入两个元素bc，此时栈中有元素abc,其中c位于栈顶，而stack2仍然为空。我们试着删除一个元素。按照队列先进先出的原则，我们应该先删除元素a。元素a存放在stack1中且不在栈顶，因此不能直接删除。注意到stack2还未使用，我们把stack1中的元素逐个弹出并压入stack2中，stack2中的元素是cba,栈顶元素是a，我们现在可以直接删除元素a了。

当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个弹出并压入stack2中。由于先进入队列的元素被压到stakc1的低端，经过弹出和压入之后就处于stack2的顶端了，可以直接弹出。

代码

/*---------------------------------------
*   日期：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;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>