【力扣刷题】Day11——栈和队列专题

---

栈和队列

栈：先进后出（尾插尾出）

队列：先进先出（尾插头出）

Java库中的栈和队列：

栈:

• 判空: empty()
• 添加元素: push
• 弹出栈顶元素: pop()
• 获取栈顶元素: peek()

队列:

• 判空: isEmpty()
• 添加元素: offer()
• 弹出栈顶元素 poll()
• 获取栈顶元素 peek()

1. 用栈实现队列

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

队列是先进先出，而栈是先进后出，我们可以通过两个栈来模拟队列。

• 将所有元素压入栈1
• 将栈1中的所有元素弹出，压入栈2，此时栈2的出栈顺序即达到了模拟队列的效果（先进先出）

注意：

• 这里的模拟是一个完整的序列要全部入栈1，然后再弹出入栈2，不能中途打断或者插入，这样的话出队的顺序就放生了改变
• 每次弹出或者获取对头元素时，要是为空的话，那就报异常，我们要注意处理（统一dumpStackIn()处理）

Code

import java.util.Stack;

class MyQueue {
    Stack<Integer> stackIn = new Stack<>();
    Stack<Integer> stackOut = new Stack<>();
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * 弹出队头元素
     * @return
     */
    // 当stackOut为空，则将stackIn里的元素弹出然后入栈
    // 当出栈stackOut不为空，那么就一直出栈（出队列）
    // 不为空时才能弹出对头元素
    public int pop() {
        dumpStackIn();
        int result = stackOut.pop();
        return result;
    }

    /**
     * 返回队列开头的元素
     * 注意：不为空才能获取
     * @return
     */
    public int peek() {
        dumpStackIn();
        int result = stackOut.peek();
        return result;
    }
    
    public boolean empty() {
        return stackIn.empty() && stackOut.empty();
    }

    // 当stackOut为空时 那么将stackIn中的元素全部放到stackOut中
    public void dumpStackIn(){
        if(!stackOut.empty()) return ;
        while(!stackIn.empty()){
            int x = stackIn.pop();
            stackOut.push(x);
        }
    }
}

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

2. 用队列实现栈

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

方法一：两个队列实现栈

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1

Code

import java.util.ArrayList;
import java.util.Queue;

class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> tmp = new LinkedList<>();
        tmp = queue1;// 此时的q1已经是空的了
        queue1 = queue2;
        queue2 = tmp;
    }
    
    public int pop() {
        int x = queue1.poll();
        return x;
    }
    
    public int top() {
        int x = queue1.peek();
        return x;
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}


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

方法二：一个队列实现

思路：

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

Code

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class MyStack {

    Queue<Integer> queue = new LinkedList<>();

    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        int n = queue.size();// 入队前先获取队列的大小
        queue.offer(x);
        for(int i = 0; i < n; i ++){
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}


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

3. 有效括号

题目链接：20. 有效的括号 - 力扣（LeetCode）

思路：栈模拟

遇到左括号入栈，遇到右括号则和栈顶元素比较，为了方便比较，我们在遇到左括号入栈的时候，实际是将它的右括号入栈，当对比的时候，就可以直接判断了（消消乐）

括号匹配有三种失败的情况：

1. 左括号多余

   ({[]}()

2. 括号未多余，但不匹配

   [()[

3. 右括号多余

   ({[]})))

第一种情况：当遍历完字符串，栈中还有多余的括号（左括号）

第二种情况：遍历匹配过程中直接不配对

第三种情况：遍历字符串的过程中，在匹对的时候，发现栈中没有与之配对的元素了（栈为空）

优化: 当字符串的长度是奇数时,一定时不能匹配成功的!

Code

import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 != 0) return false;

        Stack<Character> stk = new Stack<>();
        for(int i = 0; i < n; i ++){
            if(s.charAt(i) == '(') stk.push(')');
            else if(s.charAt(i) == '[') stk.push(']');
            else if(s.charAt(i) == '{') stk.push('}');
            
            // 第二、第三种情况
            else if(stk.empty() || s.charAt(i) != stk.peek()) return false;
            else stk.pop();// 当前元素匹配了
        }
        return stk.empty();// 第一种情况（看最后栈是否为空）
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 删除字符串中的所有相邻重复项

题目链接:1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

思路: 栈模拟

和上一题很相像, 我们遍历时对栈进行操作即可

• 当栈为空或者此时的元素和栈顶元素不匹配, 则将当前元素入栈
• 匹配, 则弹出栈顶元素

最后栈内剩余的元素即为答案!

Code

import java.util.Stack;

class Solution {
    public String removeDuplicates(String s) {
        char[] cs = s.toCharArray();
        Stack<Character> stk = new Stack<>();

        //遍历模拟过程 
        for(int i = 0; i < cs.length; i ++){
            if(stk.empty() || cs[i] != stk.peek()){
                stk.push(cs[i]);
            }else {
                stk.pop();
            }
        }
        String res = "";
        while (!stk.empty()){
            res = stk.pop() + res;
        }
        return res;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24