栈与队列

发表于 更新于 分类于 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 17 分钟

1. 栈的实现

1.1 设计一个支持增量操作的栈

请你设计一个支持对其元素进行增量操作的栈。

实现自定义栈类 CustomStack ：

  • CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量。
  • void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
  • int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
  • void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。

思路

使用数组进行模拟即可。

代码

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
class CustomStack {
    List<Integer> stack;
    int size;
    public CustomStack(int maxSize) {
        stack=new ArrayList<>(maxSize);
        size=maxSize; 
    }
    
    public void push(int x) {
        if(stack.size()<size){
            stack.add(x);
        }
    }
    
    public int pop() {
        return stack.isEmpty()?-1:stack.remove(stack.size()-1);
    }
    
    public void increment(int k, int val) {
        // k与栈中元素个数取较小值
        int s=stack.size()<k?stack.size():k;
        for(int i=0;i<s;i++){
            stack.set(i,stack.get(i)+val);
        }
    }
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack obj = new CustomStack(maxSize);
 * obj.push(x);
 * int param_2 = obj.pop();
 * obj.increment(k,val);
 */

1.2 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

思路

维护两个栈，一个是当前栈，一个是最小栈。

代码

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
class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStack;
    public MinStack() {
        stack=new LinkedList<>();
        minStack=new LinkedList<>();
        // 最小栈中预先存入int最大值，这样不必判断栈是否为空
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) { 
        // 入栈操作
        stack.push(val);
        // 最小栈更新当前最小值
        minStack.push(minStack.peek()<=val?minStack.peek():val);
    }
    
    public void pop() {
        // 出栈
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        // 返回当前栈顶元素
        return stack.peek();
    }
    
    public int getMin() {
        // 返回最小元素
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

2. 栈的应用

2.1 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

思路

使用栈进行模拟，每次比较栈顶元素与当前元素是否配对。

代码

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
class Solution {
    public boolean isValid(String s) {
        Deque<Character> hep=new LinkedList<>();
        int n=s.length();
        for(int i=0;i<n;i++){
            char k=s.charAt(i);
            // 若为左括号，直接入栈
            if(k=='('||k=='['||k=='{'){
                hep.push(k);
            }else{// 若为右括号，需判断
                // 栈空，说明不配对，返回false
                if(hep.isEmpty()){
                    return false;
                }else{
                    char r=hep.poll();
                    // 判断元素是否配对
                    if((k==')'&&r=='(')||(k==']'&&r=='[')||(k=='}'&&r=='{')){
                        continue;
                    }else{
                        return false;
                    }
                }
            }
        }
        // 栈空说明表达式有效，否则还有元素残留在栈中则无效
        return hep.isEmpty();
    }
}

2.2 移除无效的括号

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：

  • 空字符串或只包含小写字母的字符串
  • 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
  • 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

思路

栈思想模拟，仅一种括号类型，无需使用栈，仅需一个变量存储当前状态即可。

首先删除多余的)，然后根据left的数量删除多余的左括号。

注意：删除左括号时，要从字符串末尾开始删除，因为从左往右遍历，若左括号多余，则是右端先多出左括号。

代码

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
class Solution {
    public String minRemoveToMakeValid(String s) {
        int n=s.length();
        int left=0;
        StringBuilder cnt=new StringBuilder();
        for(int i=0;i<n;i++){
            char k=s.charAt(i);
            // 左括号加入字符串中，后期再处理是否多余
            if(k=='('){
                cnt.append(k);
                left++;
            }else if(k==')'){
                // 判断右括号是否能加入字符串中
                if(left==0){// 左括号数量为0，无法加入
                    continue;
                }else{
                    // 若加入，那么左括号数量减一
                    left--;
                    cnt.append(k);
                }
            }else{
                cnt.append(k);
            }
        }
        int over=left;
        int size=cnt.length();
        StringBuilder target=new StringBuilder();
        for(int i=size-1;i>=0;i--){
            // 多余左括号处理
            if(over>0&&cnt.charAt(i)=='('){
                over--;
                continue;
            }
            target.append(cnt.charAt(i));
        }
        // 由于从右往左遍历，字符串需要反转
        return target.reverse().toString();
    }
}

2.3 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

思路

模拟入栈与出栈操作。

代码

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
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n=pushed.length;
        Deque<Integer> stack=new LinkedList<>();
        // popped指针
        int index=0;
        // pushed指针
        int id=0;
        while(id<n||index<n){
            // 栈空或栈顶元素不等于出栈元素
            if(stack.isEmpty()||stack.peek()!=popped[index]){
                // 若元素已经全部入栈，返回false
                if(id>=n) return false;
                // 否则将元素入栈
                else stack.push(pushed[id++]);
            }else{
                // 栈顶元素等于出栈元素，出栈
                stack.pop();
                // popped指针后移
                index++;
            }
        }
        return true;
    }
}

2.4 用栈操作构建数组

给你一个数组 target 和一个整数 n。每次迭代，需要从 list = { 1 , 2 , 3 ..., n } 中依次读取一个数字。

请使用下述操作来构建目标数组 target ：

  • "Push"：从 list 中读取一个新元素， 并将其推入数组中。
  • "Pop"：删除数组中的最后一个元素。
  • 如果目标数组构建完成，就停止读取更多元素。

题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。

思路

按照题意进行栈模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<String> buildArray(int[] target, int n) {
        // 结果数组
        List<String> cnt=new ArrayList<>();
        // push和pop
        String push="Push",pop="Pop";
        int len=target.length,id=0;
        for(int i=1;i<=n;i++){
            // 若target数组已遍历完，则返回结果
            if(id==len) return cnt;
            // 将当前元素入栈
            cnt.add(push);
            // 若当前元素在目标数组中，则指针后移
            if(i==target[id]){
                id++;
            }else{// 否则将当前元素出栈
                cnt.add(pop);
            }
        }
        return cnt;
    }
}

3. 表达式求值

3.1 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

思路

栈模拟，遇到操作数则将其入栈，遇到运算符则运算，并将结果入栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> op=new LinkedList<>();
        int x=0,y=0;
        for(String token:tokens){
            // 判断是否为运算符
            if(token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/")){
                // 运算
                switch(token.charAt(0)){
                    case '+':op.push(op.poll()+op.poll());break;
                    case '-':x=op.poll();y=op.poll();op.push(y-x);break;
                    case '*':op.push(op.poll()*op.poll());break;
                    case '/':x=op.poll();y=op.poll();op.push(y/x);break;
                }
            }else{// 操作数直接入栈
                op.push(Integer.parseInt(token));
            }
        }
        return op.poll();
    }
}

3.2 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

思路

栈模拟，由于表达式中运算符仅有加减乘除，操作数均为非负数，对于加减操作，可以直接将对应操作数推入栈中；对于乘除操作，则推出栈顶元素进行运算后再将结果推入栈中。

代码

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
class Solution {
    public int calculate(String s) {
        int n=s.length();
        Deque<Integer> cnt=new LinkedList<>();
        // 初始状态为非负数，即+
        char pre='+';
        int num=0;
        for(int i=0;i<n;i++){
            if(Character.isDigit(s.charAt(i))){
                num=num*10+s.charAt(i)-'0';
            }
            // 若为’ ‘，不执行
            // 若i==n-1，说明已到末尾，进行最终运算
            if(!Character.isDigit(s.charAt(i))&&s.charAt(i)!=' '||i==n-1){
                // 每次对数字前的运算符进行运算，而非对当前运算符运算
                switch(pre){
                    case '+':cnt.push(num);break;
                    case '-':cnt.push(-num);break;
                    case '*':cnt.push(cnt.pop()*num);break;
                    case '/':cnt.push(cnt.pop()/num);break;
                }
                pre=s.charAt(i);
                num=0;
            }
        }
        int ans=0;
        // 由于加减操作是直接将操作数推入栈中，需要将栈中数字累加得到结果
        while(!cnt.isEmpty()){
            ans+=cnt.poll();
        }
        return ans;
    }
}

3.3 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

思路

思路与上一题解类似，表达式中的运算符只有加减，对于左括号，存储它前面的运算符号，对于右括号，直接出栈即可。

代码

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
class Solution {
    public int calculate(String s) {
        int n=s.length();
        int i=0;
        Deque<Integer> cnt=new LinkedList<>();
        int flag=1;
        // 初始化为正
        cnt.push(flag);
        int answer=0;
        while(i<n){
            if(s.charAt(i)==' '){// 空格跳过
                i++;
            }else if(s.charAt(i)=='+'){// 取当前栈顶元素符号
                flag=cnt.peek();
                i++;
            }else if(s.charAt(i)=='-'){// 取当前栈顶元素符号的相反数
                flag=-cnt.peek();
                i++;
            }else if(s.charAt(i)=='('){// 将括号前的元素符号入栈
                cnt.push(flag);
                i++;
            }else if(s.charAt(i)==')'){// 括号内运算结束，出栈
                cnt.pop();
                i++;
            }else{
                // 运算
                int ans=0;
                while(i<n&&Character.isDigit(s.charAt(i))){
                    ans=ans*10+s.charAt(i)-'0';
                    i++;
                }
                answer+=flag*ans;
            }
        }
        return answer;
    }
}

4. 队列的实现

4.1 设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

思路

通过数组或链表模拟队列。

数组模拟：front指针指向队首，tail指针指向最后一个未被占用的空间，即队尾之后。

注意：数组模拟时注意队列为空与队列已满的判断条件。

代码

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
class MyCircularQueue {
    private int front;
    private int tail;
    private int size;
    private int[] queue;
    public MyCircularQueue(int k) {
        // 初始化容量为k+1，因为tail指向最后一个不被占用的空间
        // 即数组需要多一个元素位置，这样在队列满时，tail才能指向最后剩余的空间
        size=k+1;
        queue=new int[size];
        front=0;
        tail=0;
    }
    
    public boolean enQueue(int value) {
        // 判断队列是否已满
        if(isFull()){
            return false;
        }
        // 插入队列中
        queue[tail]=value;
        // 队尾指针后移
        // （tail+1）%size保证tail指针不越界
        tail=(tail+1)%size;
        return true;
    }
    
    public boolean deQueue() {
        // 判断队列是否为空
        if(isEmpty()){
            return false;
        }
        // 移除队首元素即队首指针后移一位
        // 处理了队首指针越界问题
        front=(front+1)%size;
        return true;
    }
    
    public int Front() {
        // 判断队列是否为空
        if(isEmpty()){
            return -1;
        }
        // 返回队首元素
        return queue[front];
    }
    
    public int Rear() {
        // 判断队列是否为空
        if(isEmpty()){
            return -1;
        }
        // tail指向的是未使用的空间，即它的前一个位置才是队尾元素
        // （tail-1+size）%size防止tail指针越界（tail可能小于0）
        return queue[(tail-1+size)%size];
    }
    
    public boolean isEmpty() {
        // 判断队列是否为空
        // 即队首==队尾
        return front==tail;
    }
    
    public boolean isFull() {
        // 判断队列是否已满
        // 即队尾指针的后一位置是否是队首
        return (tail+1)%size==front;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

4.2 设计循环双端队列

设计实现双端队列。

实现 MyCircularDeque 类:

  • MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
  • boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
  • boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
  • boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
  • boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
  • int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
  • int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
  • boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
  • boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

思路

双端队列模拟，思路同题解一。

代码

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
class MyCircularDeque {
    private int front;
    private int tail;
    private int size;
    private int[] deque;
    public MyCircularDeque(int k) {
        size=k+1;
        deque=new int[size];
        front=tail=0;
    }
    
    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }
        front=(front-1+size)%size;
        deque[front]=value;
        return true;
    }
    
    public boolean insertLast(int value) {
        if(isFull()){
            return false;
        }
        deque[tail]=value;
        tail=(tail+1)%size;
        return true;
    }
    
    public boolean deleteFront() {
        if(isEmpty()){
            return false;
        }
        front=(front+1)%size;
        return true;
    }
    
    public boolean deleteLast() {
        if(isEmpty()){
            return false;
        }
        tail=(tail-1+size)%size;
        return true;
    }
    
    public int getFront() {
        if(isEmpty()){
            return -1;
        }
        return deque[front];
    }
    
    public int getRear() {
        if(isEmpty()){
            return -1;
        }
        return deque[(tail-1+size)%size];
    }
    
    public boolean isEmpty() {
        return front==tail;
    }
    
    public boolean isFull() {
        return (tail+1)%size==front;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

5. 栈和队列相互实现

5.1 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

思路

维护两个队列，outStack存储栈内元素，inStack作为辅助队列，辅助入栈。

每次进行入栈操作时，先将其插入inStack中，然后再将outStack中元素依次插入inStack中，再将二者交换，即实现了栈。

代码

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
class MyStack {
    Deque<Integer> inStack;
    Deque<Integer> outStack;
    public MyStack() {
        inStack=new LinkedList<>();
        outStack=new LinkedList<>();
    }
    
    public void push(int x) {
        // 加入辅助队列
        inStack.offer(x);
        // 将原来栈中元素加入辅助队列中
        while(!outStack.isEmpty()){
            inStack.offer(outStack.poll());
        }
        // 交换两者指针，实现栈
        Deque<Integer> tmp=outStack;
        outStack=inStack;
        inStack=tmp;
    }
    
    public int pop() {
        return outStack.poll();
    }
    
    public int top() {
        return outStack.peek();
    }
    
    public boolean empty() {
        return outStack.isEmpty();
    }
}

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

5.2 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

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

思路

维护两个栈，一个栈用于输入，一个用于输出。

代码

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
class MyQueue {
    Deque<Integer> inQueue;
    Deque<Integer> outQueue;
    public MyQueue() {
        inQueue=new LinkedList<>();
        outQueue=new LinkedList<>();
    }
    
    public void push(int x) {
        // 入栈
        inQueue.push(x);
    }
    
    public int pop() {
        // 将输入栈中的元素依次加入输出栈中
        // 这样使得栈顶元素变为了栈底元素，即实现了队列
        if(outQueue.isEmpty()){
            while(!inQueue.isEmpty()){
                outQueue.push(inQueue.pop());
            }
        }
        return outQueue.pop();
    }
    
    public int peek() {
        // 将输入栈中的元素依次加入输出栈中
        // 这样使得栈顶元素变为了栈底元素，即实现了队列
        if(outQueue.isEmpty()){
            while(!inQueue.isEmpty()){
                outQueue.push(inQueue.pop());
            }
        }
        return outQueue.peek();
    }
    
    public boolean empty() {
        // 判断输入栈和输出栈是否同时为空
        return inQueue.isEmpty()&&outQueue.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();
 */