leetcode刷题：栈与队列01（用栈实现队列）

力扣题目链接

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路：就是两个栈嘛，一个用来接数据，一个用来出数据， 先进 后出 后进 先出。
入栈就直接入数据的栈 接数据 push了。
出栈和查看栈差不多，先看看出数据的栈是否是空的，如果是空的，把入数据的栈全推到出数据的栈， 先进 +（ 后出 + 后进 ）+ 先出 = 先进 先出
判空就更好做了，看看两个栈如果都是空才算空。

package com.programmercarl.stacks_queues;

import java.util.Stack;

/** * @ClassName MyQueue * @Descriotion TODO * @Author nitaotao * @Date 2022/6/29 10:57 * @Version 1.0 * 232. 用栈实现队列 * https://leetcode.cn/problems/implement-queue-using-stacks/ * 思路： * 栈，先进后出 * 队列，先进先出 * 栈模拟队列，一个元素从第一个栈入，出来后再推入第二个栈，则 先进 后出 后进 先出 == 先进 先出 **/
public class MyQueue {
    
    private Stack stackIn;
    private Stack stackOut;

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

    /** * 推入一个元素 * * @param x */
    public void push(int x) {
    
        stackIn.push(x);
    }

    /** * 返回栈顶元素 * * @return */
    public int pop() {
    
        int lenIn = stackIn.size();
        int lenOut = stackOut.size();
        //老区先出完，新区再进
        if (lenOut > 0) {
    
            return (int) stackOut.pop();
        } else {
    
            //老区无元素，新区进老区
            while (lenIn > 0) {
    
                stackOut.push(stackIn.pop());
                lenIn--;
            }
            return (int) stackOut.pop();
        }
    }

    /** * 查看栈顶元素 * * @return */
    public int peek() {
    
        int lenIn = stackIn.size();
        int lenOut = stackOut.size();
        //老区先出完，新区再进
        if (lenOut > 0) {
    
            return (int) stackOut.peek();
        } else {
    
            //老区无元素，新区进老区
            while (lenIn > 0) {
    
                stackOut.push(stackIn.pop());
                lenIn--;
            }
            return (int) stackOut.peek();
        }
    }

    /** * 判空 * * @return */
    public boolean empty() {
    
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}


/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */