代码随想录——栈与队列

232.用栈实现队列

力扣题目链接

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

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 操作）。

思路

两个栈实现一个队列，一个栈顺序存放元素，一个栈逆序存放元素，两个栈同时只能一个栈存放元素，要么是顺序存放，要么是逆序存放。

代码实现

class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        //顺序存放元素
        stack1 = new Stack<>();

        //逆序存放元素
        stack2 = new Stack<>();
        //两个栈同时只能一个栈存放元素，要么顺序存放，要么逆序存放
    }

    public void push(int x) {
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        stack1.push(x);
    }

    public int pop() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }

    public int peek() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.size() == 0 && stack2.size() == 0;
    }
}
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

225. 用队列实现栈

力扣题目链接

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

实现 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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

思路

栈和队列只是一种抽象概念，底层可以用任意数据结构实现。只需保证维护栈和队列基本特征，栈：先进后出；队列：先进先出。任何实现都是OK的。

下面就是使用一个队列来实现栈。【双端队列直接调API】

代码实现

class MyStack {
    //使用一个队列来实现栈
    LinkedList<Integer> queue;

    public MyStack() {
       queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.addFirst(x);
    }
    
    public int pop() {
        return queue.removeFirst();
    }
    
    public int top() {
        return queue.getFirst();
    }
    
    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

---

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

只需要统一操作规则，实现起来就不算难，例如：我的pop()和top()操作，有着统一的规则：让queue1每次都存放的是栈顶元素

代码实现

public class MyStack2 {
    /**
     * 使用两个队列来实现栈
     */
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack2() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        //queue1只维护一个栈顶元素
        int size = queue1.size();

        //size >= 1
        while (size > 1){
            queue2.offer(queue1.poll());
            size--;
        }

        if (size == 1){
            return queue1.poll();
        }

        //size = 0
        while (!queue2.isEmpty()){
            queue1.offer(queue2.poll());
            size++;
        }

        while (size > 1){
            queue2.offer(queue1.poll());
            size--;
        }
        return queue1.poll();
    }

    public int top() {
        //queue1只维护一个栈顶元素
        int size = queue1.size();

        while (size > 1){
            queue2.offer(queue1.poll());
            size--;
        }

        if (size == 1){
            return queue1.peek();
        }

        while (!queue2.isEmpty()){
            queue1.offer(queue2.poll());
            size++;
        }

        while (size > 1){
            queue2.offer(queue1.poll());
            size--;
        }
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.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
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

Queue的一些API解释

20. 有效的括号

力扣题目链接

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例 1:

• 输入: “()”
• 输出: true

示例 2:

• 输入: “()[]{}”
• 输出: true

示例 3:

• 输入: “(]”
• 输出: false

示例 4:

• 输入: “([)]”
• 输出: false

示例 5:

• 输入: “{[]}”
• 输出: true

思路

括号匹配是使用栈解决的经典问题。

看代码就能看懂，直接上代码

代码实现

 public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        // java8新特性–双括号初始化map
        Map<Character, Character> map = new HashMap<Character, Character>(3) {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
     	//借助栈
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (map.containsValue(c)) {
                stack.push(c);
            } else {
                //先出现反括号直接返回false
                if (stack.isEmpty()) {
                    return false;
                }

                //peek返回栈顶元素不删除，pop弹出并返回栈顶元素
                if (!stack.peek().equals(map.get(c))) {
                    //只要栈顶元素跟该元素不匹配直接返回false
                    return false;
                } else {
                    //弹出栈顶元素
                    stack.pop();
                }
            }
        }

        return stack.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

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

力扣题目链接

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

• 输入：“abbaca”
• 输出：“ca”
• 解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

提示：

• 1 <= S.length <= 20000
• S 仅由小写英文字母组成。

思路

操作过程如下：

依旧是栈的经典应用，直接使用栈，最后栈不能直接转成字符串，还需要使用额外空间反转栈元素，费时费空间。

使用StringBuilder来充当栈，不需借助额外空间，到最后能直接返回结果。

代码实现

 public String removeDuplicates(String s) {
//        //直接使用栈
//        Stack stack = new Stack<>();
//        for (char c : s.toCharArray()) {
//            if (!stack.isEmpty() && stack.peek().equals(c)) {
//                stack.pop();
//            } else {
//                stack.push(c);
//            }
//        }
//
//        String ans = "";
//        //字符串反转
//        while (!stack.isEmpty()){
//            ans = stack.pop() + ans;
//        }
//        return ans;

        //StringBuilder 充当栈
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) {
                sb.deleteCharAt(sb.length() - 1);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
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

150. 逆波兰表达式求值

力扣题目链接

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

• 输入: [“2”, “1”, “+”, “3”, " * "]
• 输出: 9
• 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

• 输入: [“4”, “13”, “5”, “/”, “+”]
• 输出: 6
• 解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

• 输入: [“10”, “6”, “9”, “3”, “+”, “-11”, " * ", “/”, " * ", “17”, “+”, “5”, “+”]

• 输出: 22

• 解释:该算式转化为常见的中缀算术表达式为：

  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
  = ((10 * (6 / (12 * -11))) + 17) + 5       
  = ((10 * (6 / -132)) + 17) + 5     
  = ((10 * 0) + 17) + 5     
  = (0 + 17) + 5    
  = 17 + 5    
  = 22    
  1
  2
  3
  4
  5
  6
  7

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

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

思路

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

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

注意两数字操作前后顺序即可

操作过程如下：

代码实现

    public int evalRPN(String[] tokens) {
       Stack<Integer> stack = new Stack<>(); 
       //加法、乘法两个元素先后顺序无所谓，减法、除法两个元素顺序不能被改变
       for(String s : tokens){
           if("+".equals(s)){   
            stack.push(stack.pop() + stack.pop()); 
           }else if("-".equals(s)){
            stack.push(-stack.pop() + stack.pop()); 
           }else if("*".equals(s)){
            stack.push(stack.pop() * stack.pop()); 
           }else if("/".equals(s)){
            int first = stack.pop();
            stack.push(stack.pop() / first); 
           }else{
            stack.push(Integer.parseInt(s));
           }
       }      

        //到最后栈中只有一个元素，该元素就是最后的结果
        return stack.pop();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

347.前 K 个高频元素

力扣题目链接

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

• 输入: nums = [1,1,1,2,2,3], k = 2
• 输出: [1,2]

示例 2:

• 输入: nums = [1], k = 1
• 输出: [1]

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 $O(n\log n)$ , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

思路

这道题目主要涉及到如下三块内容：

1. 要统计元素出现频率
2. 对频率排序
3. 找出前K个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。（key存元素，value存元素出现次数即可）

然后是对频率进行排序，这里我们可以使用一种 集合就是优先级队列。

什么是优先级队列？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。当然我们也可以自己指定排序规则。

得益于它的这个构造器public PriorityQueue(Comparator comparator)，因此我们可以通过实现Comparator接口自定义排序规则

什么是堆？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

对于该题我们可以使用大顶堆也可以使用小顶堆。

大顶堆：

优先级队列中不限制元素数量，将上述统计得到的map中的所有元素放入优先级队列，最后取出优先级队列前k个元素即可。这种做法的时间复杂度是O(n log n)，不是最优解，而且我们只需要k个元素，没必要对所有元素进行排序，最后取出前k个。

小顶堆：

使用小顶堆的话，我们可以只在优先级队列中存k个元素，当第k + 1个元素过来时与堆顶元素出现次数比较（堆顶元素出现次数最小），如果该元素出现次数大于堆顶元素，只需移除堆顶元素放入该元素即可，最后队列中元素就是我们需要的k个元素。该种做法的时间复杂度是O(n log k)。当元素个数n很大，需要找到元素个数k很小时，这种做法效率明显比大顶堆高很多。

代码实现

   /*Comparator接口说明:
    * 默认从小到大升序【队头到队尾】小顶堆
    * 
	* 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
	* 对于队列：排在前面意味着往队头靠
	* 
 	* 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
 	*                               从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
 	* (pair1, pair2) -> pair1.getValue() - pair2.getValue() 根据元素出现频率升序，对于堆而言就是小顶堆	
	* */ 
	public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        //使用map统计元素出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        //优先级队列，出现次数按从队头到队尾的顺序是从小到大排，出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((pair1, pair2) -> pair1.getValue() - pair2.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.add(entry);
            } else {
                //队列中只维护k个元素，当当前元素出现个数大于堆顶元素出现个数（小顶堆）时，移除队头元素放入当前元素
                if (entry.getValue() > priorityQueue.peek().getValue()) {
                    priorityQueue.poll();
                    priorityQueue.add(entry);
                }
            }
        }

        int index = k - 1;
        while (!priorityQueue.isEmpty()) {
            ans[index--] = priorityQueue.poll().getKey();
        }
        

        //基于大顶堆实现，从头到尾出现频率依次递减
//        PriorityQueue> priorityQueue = new PriorityQueue<>((pair1, pair2) -> pair2.getValue() - pair1.getValue());
//        for (Map.Entry entry : map.entrySet()) {
//            priorityQueue.add(entry);
//        }
//
//        //直接取前k个元素即可
//        for (int i = 0; i < k; i++) {
//            ans[i] = priorityQueue.poll().getKey();
//        }
        return ans;
    }
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

239. 滑动窗口最大值

力扣题目链接

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

思路

这题完全可以用优先级队列来解题，优先级队列中只维护k个元素，可以使用大顶堆，窗口每次移动，堆顶也就是队列头就是我们要的元素，放到结果中，这种解法理论上可行。（但是会超时~）

代码如下：

  public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        int[] ans = new int[len];
        //一、大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((num1, num2) -> num2 -num1);
        for(int i = 0; i < len; i++){
            //每次进来清空队列，让队列中只维护k个元素
            queue.clear();
            int temp = i;
            while(temp < i + k){
                queue.add(nums[temp++]);
                ans[i] = queue.peek();
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

实际上我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

这个队列应该长这个样子：

class MyQueue {
        void pop(int val) {}

        void push(Integer val) {}

        public int getMax() {}

    }
1
2
3
4
5
6
7
8

每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.getMax()就返回我们要的最大值。

实际上Java中没有这样的数据结构，我们需要自己实现这么个队列。

---

然后再分析一下，队列里的元素一定是要排序的，而且要最大值放在出队口，要不然怎么知道最大值呢。

但如果把窗口里的元素都放进队列里，窗口移动的时候，队列需要弹出元素。

那么问题来了，已经排序之后的队列 怎么能把窗口要移除的元素（这个元素可不一定是最大值）弹出呢。

主要思想是队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

---

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。

而且不要以为实现的单调队列就是 对窗口里面的数进行排序，如果仅仅排序的话，那和优先级队列又有什么区别了呢。

设计单调队列的时候，pop，和push操作要保持如下规则：

1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列出口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.getMax()【直接返回队头元素】就可以返回当前窗口的最大值。
动画过程：

首先要明确的是，题解中单调队列里的pop和push接口，仅适用于本题。

单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。

不要以为本题中的单调队列实现就是固定的写法。

代码实现

（自定义单调队列以及直接使用双端队列来实现单调队列）

public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        int[] ans = new int[len];
        //二、自定义单调栈：单调队列只维护可能是最大值的数
//        MyQueue queue = new MyQueue();
//        int index = 0;
//        //先push前k个元素
//        for (int i = 0; i < k; i++) {
//            queue.push(nums[i]);
//        }
//        ans[index++] = queue.getMax();
//
//        for (int i = k; i < nums.length; i++) {
//            //弹出最开始的元素
//            queue.pop(nums[i - k]);
//            queue.push(nums[i]);
//            ans[index++] = queue.getMax();
//        }

        //直接使用双端队列实现单调栈
        Deque<Integer> deque = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            //先pop 弹出开始元素
            if (!deque.isEmpty() && i - k >= 0 && nums[i - k] == deque.peekFirst()) {
                deque.removeFirst();
            }

            //再push
            while (!deque.isEmpty() && deque.getLast() < nums[i]) {
                deque.removeLast();
            }
            deque.add(nums[i]);
            //最后取出最大元素[队头元素]，从前k个元素开始
            if (i >= k - 1) {
                ans[index++] = deque.peekFirst();
            }
        }
        return ans;
    }


    /**
     * 自定义单调队列
     * 队列中元素从头到尾依次递减，
     * pop元素时，开始元素与队头元素相等时，pop出队头元素
     * push元素时，队尾元素比当前元素小将该元素弹出（因此需要双端队列）直到队尾元素大于等于当前元素，再把当前元素添加到队尾
     * 每次pop、push结束之后，获取队列中最大值（即队头元素）getMax
     */
    static class MyQueue {
        Deque<Integer> deque = new LinkedList<>();

        void pop(int val) {
            //只有开始值与队头元素相等，才将队头元素弹出
            if (!deque.isEmpty() && deque.getFirst() == val) {
                deque.removeFirst();
            }
        }

        void push(Integer val) {
            //只要队尾值比当前元素小，直接从队尾弹出
            while (!deque.isEmpty() && deque.getLast() < val) {
                deque.removeLast();
            }

            deque.addLast(val);
        }

        //返回队头最大值
        public int getMax() {
            return deque.peek();
        }

    }
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

详情见代码随想录