剑指offer面试题：用两个栈实现队列

题目描述

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

C++版本的初始代码为：

class Solution
{
public:
    void push(int node) {
        
    }

    int pop() {
        
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

思路分析

用两个栈实现一个队列的功能?要求给出算法和思路!

<分析>：

入队：将元素进栈A
出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B直接出栈。

换个说法：
栈A用来作入队列；栈B用来出队列，当栈B为空时，栈A全部出栈到栈B,栈B再出栈（即出队列）。

本地测试的完整C++程序：【添加了一个打印函数】

#include <iostream>
#include <stack>
using namespace std;

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.size() <= 0) {
            while (stack1.size() > 0) {
                int data = stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }
        if(stack2.size() == 0)
            cout << "error" << endl;
            //throw new exception("queue is empty");
        
        int head = stack2.top();
        stack2.pop();
        
        return head;
    }
    int show_value(){
        int count = 0;
        int data;
        while (stack2.size() > 0) {
            data = stack2.top();
            cout << data << " ";
            stack2.pop();
            stack1.push(data);
            ++count;
        }
        while (stack1.size() > 0) {
            data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
        // stack2中只返回原先就在stack1中的值。
        while (stack2.size() > count) {
            data = stack2.top();
            cout << data << " ";
            stack2.pop();
            stack1.push(data);
        }
        if  (stack2.size() != count )
            cout << "error:" << stack2.size() << " != " << count;
        cout << endl;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

int main() {
    Solution *s = new Solution();
    s->push(5);
    s->push(4);
    s->push(3);
    s->push(2);
    s->pop();
    s->push(1);
    s->push(0);
    s->push(-1);
    s->pop();
    s->push(-2);
    // 打印出队列的值。
    s->show_value();
	
	return 0;
}

此外，还可以思考一下：

用两个队列实现一个栈的功能?要求给出算法和思路!

<分析>：

入栈：将元素进队列A
出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素 以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把队列B中的元素出队列依次放入队列A中。