剑指Offer-用两个栈实现队列-蒲公英云

剑指Offer-用两个栈实现队列

题目描述

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

初步解题思路：使用stack1专门用来输入，stack2专门用来输出。当作为队列输出时，将stack1中的内容全部压入stack2中，然后stack2.pop()。当作为队列输入时，将stack2中的内容全部压入stack1中，然后stack1.push(value)。
最优解：初步解题思路将数据来回压入堆栈，效率较低。此时可以分段压入和输出。当stack2中没有数据时，将stack1的内容压入进行输出。当stack2中有数据时，stack1中的内容不需要移动，依旧保存在stack1中，stack1继续在原有数据上存放输入数据。

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) {
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        stack1.push(node);
    }
    public int pop() {
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

最优解

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(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}