用栈实现队列&&用队列实现栈（LeetCode 232&&225）

题目

232. 用栈实现队列 

思路

使用两个栈，输入一个栈，输出一个栈，输出栈中存放的是输入栈中pop的每个元素。输出栈用于实现队列的pop和peek方法，输入栈用于队列的push方法。如两者中元素都为空时，则表示队列为空。 

代码

class MyQueue {
    public Stack<Integer> stack_1;
    public Stack<Integer> stack_2;

    public MyQueue() {
         stack_1 = new Stack<>();
         stack_2 = new Stack<>();
    }

    public void push(int x) {
        this.stack_1.push(x);
    }

    public int pop() {
        // 输出栈为空
        // 则将输入栈的数据复制一份到输出栈中
        while (stack_2.empty()){
            while (!stack_1.empty()){
                stack_2.push(stack_1.pop());
            }
        }
        return stack_2.pop();
    }

    public int peek() {
        while (stack_2.empty()){
            while (!stack_1.empty()){
                stack_2.push(stack_1.pop());
            }
        }
        return stack_2.peek();
    }

    public boolean empty() {
        while (stack_2.empty() && stack_1.empty()){
            return true;
        }
        return false;

    }
}

题目

225. 用队列实现栈 

思路

每次保证新加入的数据在队列的第一个位置即可保持与栈一致的顺序（这里有点点巧妙 可用看代码随想录 中的动画表示）。 

代码

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q2.add(x);
        //循环后 q1的队列为空都加入到q2中了
        while (!q1.isEmpty()){
            q2.add(q1.poll());
        }
        // 交换q1、q2 保证q2在下次加入队列时为空 q1中保持与栈一致
        // 这样向q2加入数据时
        // 该数据就是q2的第一个 保持与栈一致
        Queue<Integer> temp ;
        temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();

    }
}