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
1
2
3
4
5
6

说明:

• 你只能使用标准的栈操作 – 也就是只有 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();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96