【代码随想录算法训练营-第十天】【栈与队列】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 stackIn;
        Stack 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 queueIn;
            Deque 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);
                }
            }
        }