【数据结构】栈与队列

发表于2021-09-20更新于2022-02-18字数统计3.8k阅读时长28分阅读次数

栈和队列的转换

使用两个栈实现队列结构

思路：A 栈用来添加数据，B 栈用来弹出数据

  • append 时直接加入到 A 栈中
  • delete 时，先判断 B 栈是否为空：
    • 如果为空，A 栈都弹出到 B 里，然后弹出 B 顶
    • 如果不为空，则直接弹出 B 顶

代码：

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
class CQueue {
    // 两个栈，
    // 1. append 时直接加入到 A 栈
    // 2. delete 时，先判断 B 栈是否为空，
    //    2.1 如果为空，A 栈都弹出到 B 里，然后弹出 B 顶。
    //    2.2 如果不为空，则直接弹出 B 顶 
    // 相当于 A 栈专门 appen。 B 栈专门 delete
    
    private Stack<Integer> queueA;
    private Stack<Integer> queueB;

    public CQueue() {
        queueA = new Stack<>();
        queueB = new Stack<>();
    }
    
    public void appendTail(int value) {
        // 向 A 栈中添加元素
        queueA.push(value);
    }
    
    public int deleteHead() {
        // 先判断 B 栈是否为空
        // 1. 如果为空，则将 A 栈的都弹出到 B 中
        if (queueB.isEmpty()) {
            while (!queueA.isEmpty()) {
                queueB.push(queueA.pop());
            }
            // 然后判断 B 是否仍为空，如果还为空，说明压根没元素
            if (queueB.isEmpty()) {
                return -1;
            } else {
                return queueB.pop();
            }
        } else {
            // 1. 如果不为空，则直接弹出 B 的栈顶
            return queueB.pop();
        }
    }
}

使用两个队列实现栈结构

思路：准备两个队列 queue 和 help。

  • 添加时，加入到 queue 中
  • 删除时，将 queue 中的数据都存到 help 中，只剩下一个弹出。弹出后再交换 queue 和 help 的引用，使得 queue 始终指向存放数据的队列。help 始终存放空队列

代码：

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
public static class TwoQueuesStack {
    private Queue<Integer> queue;
    private Queue<Integer> help;

    public TwoQueuesStack() {
        queue = new LinkedList<Integer>();
        help = new LinkedList<Integer>();
    }

    public void push(int pushInt) {
        queue.add(pushInt);
    }

    public int peek() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Stack is empty!");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }
        int res = queue.poll();
        help.add(res);
        swap();
        return res;
    }

    public int pop() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Stack is empty!");
        }
        while (queue.size() > 1) {
            help.add(queue.poll());
        }
        int res = queue.poll();
        swap();
        return res;
    }

    private void swap() {
        Queue<Integer> tmp = help;
        help = queue;
        queue = tmp;
    }
}

栈的常见题目

栈内元素的排序

请编写一个程序，对一个栈里的整型数据，按升序进行排序（即排序前，栈里的数据是无序的，排序后最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

思路：创建一个辅助栈，按照底大顶小的顺序保存原栈中的数据。

  • 从原栈中弹出元素：
    • 如果辅助栈为空或辅助栈栈顶元素大于当前元素，则该元素进辅助栈
    • 否则该元素暂时不进，而是不断弹出辅助栈的栈顶元素到原栈中，直到辅助栈为空或辅助栈栈顶元素大于当前元素，将该元素进辅助栈
  • 重复该过程，直到原栈弹空，此时辅助栈中保存了所有元素，并且是按照降序排序的
  • 依次弹出辅助栈中的元素到原栈中，即完成了升序排序

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class StackSort {
    public static void stackSort(Stack<Integer> stack) {
        int tmp = 0;
        Stack<Integer> stackHelper = new Stack<>();
        // 遍历原始栈，将每个元素压入到辅助栈中
        while (!stack.isEmpty()) {
            tmp = stack.pop();
            // 如果tmp大于辅助栈的栈顶, 则辅助栈一直弹栈直到tmp能进去
            while (!stackHelper.isEmpty() && tmp > stackHelper.peek()) {
                stack.push(stackHelper.pop());
            }
            // 辅助栈弹够了以后, 就可以把tmp放进去了, 此时能保证辅助栈里的顺序是上面小下面大
            stackHelper.push(tmp);
        }

        // 最后再将辅助栈里的元素一一弹出压入原栈中
        while (!stackHelper.isEmpty()) {
            stack.push(stackHelper.pop());
        }
    }
}

包含 min 函数的栈

剑指 Offer 30. 包含min函数的栈：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

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
class MinStack {
    private Stack<Integer> stack;
    // 维护一个单调栈结构，动态且单调地保存目前栈内的最小值序列
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (!minStack.isEmpty()) {
            // 如果当前元素小于等于单调栈的栈顶元素，保存到单调栈中
            if (minStack.peek() >= x) {
                minStack.push(x);
            }
        } else {
            // 如果为空直接添加
            minStack.push(x);
        }
    }
    
    public void pop() {
        // 如果即将弹出一个最小值，则同样将单调栈的栈顶给弹出
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

单调栈

遍历整个数组，使用一个栈记录数组中的元素索引。

所有元素不重复的情况

  • 当寻找某个元素左右距离他最近的比他小的元素时，栈底元素的值小于栈顶元素的值。例如栈中：[2 -> 3 -> 4(栈顶)。新来一个元素1，其值小于4，则找到了当前栈顶4左右侧距离他最近的比他小的元素3和1。将4弹出，记录其左右侧的3和1，然后继续。
  • 当寻找某个元素左右距离他最近的比他大的元素时，栈底元素大于栈顶元素。例如栈中：[4 -> 3 -> 2(栈顶)。新来一个元素5，其值大于2，则找到了当前栈顶2左右侧距离他最近的比他大的元素3和5。

规律：

  • 整体是满足单调性的。当发现新来的元素破坏了栈中的单调性时，将栈顶元素弹出（其余元素不弹出，新来的元素也不在此时入栈，而是进行下一轮判断是否可以入栈），记录此时新的栈顶元素作为其左侧最近元素，记录新来的元素为其右侧最近元素。
  • 栈中保存的元素始终是按照升序或降序排列的，肯定满足单调性。这是因为中途破坏单调性的元素都被弹出并记录了，还在栈中的都是单调排序的。
  • 找某个元素左右比他小的，栈中是升序排列；找某个元素左右比他大的，栈中是降序排列。

有元素重复的情况

当有元素重复时，栈中不能单单只存储一个 Integer 类型变量，而应该存储一个 ArrayList，将相同值的元素存储到同一个 List 中。

算法整体顺序一致，区别在于弹栈时弹出的是一个 List，需要将这个 List 中的所有元素都遍历一次，加入到 res[][] 中；另外，在获取左侧的元素索引值时，需要获取到栈顶第二个 List 里的最后一个元素（这个元素是最靠近当前弹出栈的元素的，因为整体是单调的，越靠后的，越在 List 的后面）。

代码：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
public class MonotonousStack {

   public static int[][] getNearLessNoRepeat(int[] nums) {
      if (nums == null || nums.length < 1) {
         return null;
      }

      Stack<Integer> stack = new Stack<>();
      int[][] res = new int[nums.length][2];

      for (int i = 0; i < nums.length; i++) {
         // 如果遇到栈顶元素大于当前元素，说明栈顶元素找到了其左侧小于它的第一个元素（栈顶下的第二个的元素）
         // 如果新来的元素仍是按照升序或降序排列，则都不会弹栈，因为仍然是符合单调性的，只有在破坏单调性时才弹栈记录
         while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            int popIndex = stack.pop();
            // 弹出的栈顶元素左侧的最小值就是新的栈顶元素（或不存在，对应栈空）
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            // 存储这个栈顶元素的左侧小于它的第一个元素索引 leftLessIndex 和其右边小于它的第一个元素索引 i
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = i;
         }
         // 跳出while循环时，i位置的元素已经能插入到栈中并满足栈中的单调性了，此时将i压入栈中
         stack.push(i);
      }

      // 遍历完数组后，栈中可能还存在一些元素，这些元素的最近元素还没保存到res里
      // 将栈中元素依次弹出，其左侧最近值就是下一个栈中元素，右侧最近值不存在，保存-1
      while (!stack.isEmpty()) {
         int popIndex = stack.pop();
         int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
         res[popIndex][0] = leftLessIndex;
         res[popIndex][1] = -1;
      }
      return res;
   }


   public static int[][] getNearLess(int[] nums) {
      if (nums == null || nums.length < 1) {
         return null;
      }

      Stack<List<Integer>> stack = new Stack<>();
      int[][] res = new int[nums.length][2];
      for (int i = 0; i < nums.length; i++) {
         while (!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]) {
            // 获取到list集合，里面可能存着多个相同值的元素
            List<Integer> popList = stack.pop();
            // 左边最小的元素为新的栈顶集合里的最后一个元素，因为最后一个元素是最靠近当前元素的（因为栈结构的单调性）
            int leftLessIndex = stack.isEmpty() ? -1 :stack.peek().get(stack.peek().size() - 1);
            // 遍历当前list里的元素（值相同），为其赋上左边最小元素索引（是相同的）以及右侧元素（i）
            for (Integer popIndex : popList) {
               res[popIndex][0] = leftLessIndex;
               res[popIndex][1] = i;
            }
         }
         // 将i加入到栈中，注意分两种情况：
         //   1. i的值和当前栈顶元素的值不相同，则新建一个list，将该list入栈
         //   2. i的值和当前栈顶元素的值相同，则将i加入到栈顶元素的list里的最后一个位置
         // 注意要带上 !stack.isEmpty() && ，必须要有元素才行
         if (!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]) {
            // 相同时，直接加入到栈顶的list中
            stack.peek().add(i);
         } else {
            // 不同时，新建一个list，入栈
            List<Integer> list = new ArrayList<>();
            list.add(i);
            stack.push(list);
         }
      }

      // 全部遍历完毕后，依次弹栈，记录栈中元素的左侧最小信息到res中
      while (!stack.isEmpty()) {
         List<Integer> popList = stack.pop();
         for (Integer popIndex : popList) {
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
         }
      }

      return res;
   }

   // for test
   public static int[] getRandomArrayNoRepeat(int size) {
      int[] arr = new int[(int) (Math.random() * size) + 1];
      for (int i = 0; i < arr.length; i++) {
         arr[i] = i;
      }
      for (int i = 0; i < arr.length; i++) {
         int swapIndex = (int) (Math.random() * arr.length);
         int tmp = arr[swapIndex];
         arr[swapIndex] = arr[i];
         arr[i] = tmp;
      }
      return arr;
   }

   // for test
   public static int[] getRandomArray(int size, int max) {
      int[] arr = new int[(int) (Math.random() * size) + 1];
      for (int i = 0; i < arr.length; i++) {
         arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
      }
      return arr;
   }

   // for test
   public static int[][] rightWay(int[] arr) {
      int[][] res = new int[arr.length][2];
      for (int i = 0; i < arr.length; i++) {
         int leftLessIndex = -1;
         int rightLessIndex = -1;
         int cur = i - 1;
         while (cur >= 0) {
            if (arr[cur] < arr[i]) {
               leftLessIndex = cur;
               break;
            }
            cur--;
         }
         cur = i + 1;
         while (cur < arr.length) {
            if (arr[cur] < arr[i]) {
               rightLessIndex = cur;
               break;
            }
            cur++;
         }
         res[i][0] = leftLessIndex;
         res[i][1] = rightLessIndex;
      }
      return res;
   }

   // for test
   public static boolean isEqual(int[][] res1, int[][] res2) {
      if (res1.length != res2.length) {
         return false;
      }
      for (int i = 0; i < res1.length; i++) {
         if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
            return false;
         }
      }

      return true;
   }

   // for test
   public static void printArray(int[] arr) {
      for (int i = 0; i < arr.length; i++) {
         System.out.print(arr[i] + " ");
      }
      System.out.println();
   }

   public static void main(String[] args) {
      int size = 10;
      int max = 20;
      int testTimes = 2000000;
      for (int i = 0; i < testTimes; i++) {
         int[] arr1 = getRandomArrayNoRepeat(size);
         int[] arr2 = getRandomArray(size, max);
         if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
            System.out.println("Oops!");
            printArray(arr1);
            break;
         }
         if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
            System.out.println("Oops!");
            printArray(arr2);
            break;
         }
      }
   }
}

单调栈的相关题目

数组中累积和与最小值的乘积

定义指标A：正数数组中累积和与该数组中最小值的乘积。给定一个数组，请返回子数组中，指标A最大的值。

该问题可以使用单调栈结构进行求解。思路：

  • 遍历每一个元素，以该元素作为当前子区间内的最小值元素（其子区间内的元素都比当前元素大）；
  • 尽可能的扩大该子区间的范围，使得当前元素为最小值的子区间范围尽可能的大，这样其数组中的累加和就会尽可能的大；
  • 找到当前元素左右侧区间边界的方法为：使用单调栈找出当前元素左侧和右侧距离他最近的比他小的元素
  • 对数组中每个元素都进行该操作，直到找出最大的指标A
  • 可以在单调栈的建立过程中更新最大的指标A，无需创建索引后再单独计算

代码：

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
public class MonotonousStack {
    public static int solution(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }

        // 数组的前缀累加和
        int[] sums = new int[nums.length];
        // 初始化第一个元素
        sums[0] = nums[0];
        // 遍历每一个元素,计算前缀累加和
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }

        Stack<Integer> stack = new Stack<>();
        // 记录答案
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            // 注意单调栈里保存的是索引值
            // 如果当前栈顶元素大于新来的元素，则找到了当前栈顶元素左右离他最近的元素，将其弹出
            // 注意是 while 循环，不断判断当前元素 nums[i] 与新的栈顶的大小，可能会一直弹出
            // 注意是 >=，和前面单调栈不同，是可能为等于的，不需要考虑太多，不会漏掉答案，因为更大的值总会被后者考虑进去的
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                // 弹出栈顶元素，更新指标A的最大值
                // 注意这两个边界值的元素值都比当前元素小
                // 弹出的这个索引位置j就是当前的局部最小值（此时的stack.peek()比他小，i也比他小，所以自己是局部最小）
                int j = stack.pop();
                // 1. 如果栈空，则不存在比他小的左边界，可以一直取到nums[0]，则当前子区间的累加和等于sums[i-1]（不能包含i值，因为其小于nums[j]）
                // 2. 如果栈不为空，则存在比他小的左边界且该边界值取不到，则当前子区间的累加和等于sums[i - 1] - sums[stack.peek()]
                max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * nums[j]);
            } 
            // 新来的元素入栈
            stack.push(i);
        }
        // 最后将栈里剩余元素进行设置
        while (!stack.isEmpty()) {
            int j = stack.pop();
            // 当前栈中元素都不存在比他小的右边界，所以右边界从sums[size - 1]开始取
            max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
        }
        return max;
    }
}

柱状图中最大的矩形

柱状图中最大的矩形：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

image-20211215154559108

该问题即为上一题的具体形式，同样可以使用单调栈进行求解。