【代码随想录算法训练营-第十天】【栈与队列】232.用栈实现队列，225. 用队列实现栈

写在最前面，目前Java已经推荐使用Deque来实现栈和队列了，原因：
https://www.cnblogs.com/jiading/articles/12452830.html

232.用栈实现队列

第一遍

• 思路
  • pop：出栈；
  • push：入栈；
  • peek：获取栈顶元素；
  • empty：判断栈是否为空；
    https://blog.csdn.net/weixin_45428910/article/details/129701275

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void push(int x) {
        stackIn.push(x);
    }

    public int pop() {
        judge();
        return stackOut.pop();
    }

    public int peek() {
        // 返回队头元素
        judge();
        return stackOut.peek();
    }

    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    public void judge() {
        if (!stackOut.isEmpty()) return;
        while (!stackIn.isEmpty()) {
            Integer x = stackIn.pop();
            stackOut.push(x);
        }
    }
}

225. 用队列实现栈

第一遍

• 思路
  • 我实现的这个方法过于复杂了，其实不用写两个trans的函数；
  • 参考答案，可以将In中的转换到Out中，然后命名交换即可；
  • 同时，Deque提供了获取头尾元素和插入头尾位置的方法，可以使用Deque实现一个队列就完成这个操作；
    https://blog.csdn.net/swadian2008/article/details/126783574

class MyStack {
    Deque<Integer> queueIn;
    Deque<Integer> queueOut;

    public MyStack() {
        queueIn = new ArrayDeque<>();
        queueOut = new ArrayDeque<>();
    }

    public void push(int x) {
        queueIn.addLast(x);
    }

    public int pop() {
        transToOut();
        Integer x = queueIn.pollFirst();
        transToIn();
        return x;
    }

    public int top() {
        transToOut();
        Integer x = queueIn.pollFirst();
        queueOut.addLast(x);
        transToIn();
        return x;
    }

    public boolean empty() {
        return queueIn.isEmpty() && queueOut.isEmpty();
    }

    private void transToOut() {
        while (queueIn.size() > 1) {
            Integer x = queueIn.pollFirst();
            queueOut.addLast(x);
        }
    }

    private void transToIn() {
        while (queueOut.size() > 0) {
            Integer x = queueOut.pollFirst();
            queueIn.addLast(x);
        }
    }
}