9.用两个栈实现队列.md

9.两个栈实现一个队列

题目描述

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

思路 & 解答

• 栈的特性是先进后出
• 队列的特性是先进先出

有两个栈 stack1,stack2； 如果有新的数据进入，那么我们可以直接 push 到 stack1； 如果需要取出数据，那么我们优先取出 stack2 的数据，如果 stack2 里面数据是空的，那么我们需要把所有的 stack1 的数据倒入 stack2。再从 stack2 取数据。

例如： (1). push 1 --> push 2

(2). pop 1

(3). push 3 --> push 4

(4). pop 2

Java 代码实现如下：

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

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

    public int pop() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

C++ 代码实现如下：

#include <iostream>
#include <stack>

using namespace std;

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

    int pop() {
        if(!stack2.empty()){
            int result = stack2.top();
            stack2.pop();
            return result;
        }else{
            while(!stack1.empty()){
                int result = stack1.top();
                stack1.pop();
                stack2.push(result);
            }
        }
        int result = stack2.top();
        stack2.pop();
        return result;
    }

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