题解 | #用两个栈实现队列#

一.题目描述
题目链接:
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=188&&tqId=38552&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
二.算法(c++实现)

c++STL中的stack可以直接拿过来用，下面介绍一下STL中stack的用法:

• push(x)将x入栈，时间复杂度为O(1)
• top()获得栈顶元素，时间复杂度为O(1)
• pop()用以弹出栈顶元素，时间复杂度为O(1)
• empty()可以检测stack内是否为空，放回true为空，返回false为非空，时间复杂度为O(1)
• size()返回stack内元素的个数，时间复杂度为O(1)

下面给出完整代码:

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        //当stack2全为空时，stack1全部到stack2 然后stack2再出栈(模拟出队列)
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int ret = stack2.top();//返回栈顶元素 相当于队列的队头
        stack2.pop();
        return ret;
    }

private:
    stack<int> stack1;//入队列
    stack<int> stack2;//出队列
};

时间复杂度:o(1) 利用sTL，效率很高
空间复杂度:o(n) 需要利用栈来存储
优缺点:容易实现，但是空间利用大

三.算法(java实现)

和算法二思路一致，是使用java来实现的,下面是完整代码：

import java.util.Stack;//初学者可能忘记导入Stack 造成无法编译
public class Solution {
    //申请两个栈satck1 stack2
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public Solution() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    //入队的时候只把数据存储在stackPush中即可
    public void push(int node) {
        stack1.push(node);
    }

    //出队的时候如果stackPop为空
    //就把stackPush中的数据全部倒入stackPop中
    public int peek() {
        if (stack2.isEmpty())
            while (!stack1.isEmpty())
                stack2.push(stack1.pop());
        return stack2.isEmpty() ? -1 : stack2.peek();
    }

    public int pop() {
        int res = peek();
        stack2.pop();
        return res;
    }

    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}

时间复杂度:O(n)
空间复杂度:O(n),需要使用两个栈存储已有的元素。
优缺点:实现起来很简单，但是速度明显慢于c++