六、栈和队列

6.1数据结构的应用

1. 用栈实现队列

   力扣232

   

   很简单，添加的时候正常加在弹入栈，删除的时候把元素放到弹出栈，直接调用java集合实现的Stack

   class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackout;public MyQueue() {stackIn = new Stack<>();stackout = new Stack<>();}public void push(int x) {stackIn.push(x);}public int pop() {dumpstackIn();return stackout.pop();}public int peek() {dumpstackIn();return stackout.peek();}public boolean empty() {return stackIn.isEmpty()&&stackout.isEmpty();}private void dumpstackIn() {if (!stackout.isEmpty()) return;while (!stackIn.isEmpty()) {stackout.push(stackIn.pop());}}
   }
   

2. 用队列实现栈

   力扣225

   

   很经典的题目，可以实现两个队列因为栈是先进后出，所以我们可以删除或者增加元素的时候把所有元素放到另一个队列中，然后再把数据追加上去，这样另一个增加或者删除就正常了。

   class MyStack {Queue<Integer> queueIn = new ArrayDeque<>();Queue<Integer> queueOut = new ArrayDeque<>();public MyStack() { }public void push(int x) {queueIn.offer(x);}public int pop() {while (queueIn.size() > 1) {queueOut.offer(queueIn.poll());}int res = queueIn.poll();Queue<Integer> temp = queueIn;queueIn = queueOut;queueOut = temp;return res;}public int top() {while (queueIn.size() > 1) {queueOut.offer(queueIn.poll());}int res = queueIn.poll();Queue<Integer> temp = queueIn;queueIn = queueOut;queueOut = temp;queueIn.offer(res);return res;}public boolean empty() {return queueIn.isEmpty();}
   }
   

   • 单个队列，就是正常增加元素，删除的时候把要删除的元素，全部拿出来放到要删除元素的后面

   class MyStack {Queue<Integer> queue = new ArrayDeque<>();public MyStack() { }public void push(int x) {queue.offer(x);int size = queue.size();while (size - 1 > 0) {queue.offer(queue.poll());size--;}}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
   }
   

6.2栈的应用

1. 有效的括号

   力扣20

   

   就是为栈量身定做的，没碰到一个符号的前半部分就把后半部分放到栈中，到后半部分开始的时候，正常弹栈匹配即可

   class Solution {public boolean isValid(String s) {Stack<Character> newStack = new Stack<>();for (char i : s.toCharArray()) {switch (i) {case '(':newStack.push(')');break;case '{':newStack.push('}');break;case '[':newStack.push(']');break;default:if (newStack.isEmpty() || newStack.pop() != i) {return false;}}}return newStack.isEmpty();}
   }
   

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

   力扣1047

   

   其实这题我觉得用不用无所谓，题本身比较简单，只要碰到重复元素即可，开辟一个空间，添加的元素判断是否与前一项相等，如果相等就全部删除，但是第一眼最方便的还是栈，数组需要通过下标需要考虑边界，没有栈的方法来的方便

   class Solution {public String removeDuplicates(String s) {Stack<Character> newStack = new Stack<>();for(char i : s.toCharArray()) {if (!newStack.isEmpty() && newStack.peek() == i) {newStack.pop();continue;}else {newStack.push(i);}}// 将栈中的字符转换为字符串StringBuilder result = new StringBuilder();for (char c : newStack) {result.append(c);}return result.toString();}
   }
   

3. 逆波兰表达式求值

   力扣150

   

   其实理解了题目很好做，计算机更喜欢这种类似于数逆序遍历的排序，不需要考虑括号什么的 a b + c *就知道是(a+b)*c，不需要去考虑优先级。这种只涉及一个方向的删除增加很适合用栈，所以只要遍历tokens，碰到数字就放入栈，然后碰到运算符就计算，记得把结果放入栈。也要记得减法和除法的特殊，先pop的是除数和减数

   class Solution {public int evalRPN(String[] tokens) {Stack<Integer> newStack = new Stack();for (String s : tokens) {switch (s) {case "+":newStack.push(newStack.pop() + newStack.pop());break;case "-":int b = newStack.pop();int a = newStack.pop();newStack.push(a - b);break;case "/":b = newStack.pop();a = newStack.pop();newStack.push(a / b);break;case "*":newStack.push(newStack.pop() * newStack.pop());break;default:newStack.push(Integer.parseInt(s));}}return newStack.pop();}
   }
   

6.3堆的应用

1. 滑动窗口最大值

   力扣239

   

   1. 使用大顶堆，我们知道大顶堆会自动排序，时间复杂度度为O(logn)，但是要注意大顶堆是会打乱顺序的，但是最大的元素始终是在最前面的，我们只要循环判断，前面的元素在不在滑动区间范围内即可，这样就不会出现问题，也就是说这个滑动区间，可能并不是一直是长度为3，但是会保证不该在滑动区间范围内的元素不会影响该滑动区间。再次强调弹出滑动区间的判断第一个最大元素是不是在滑动区间内即可。比如12323 k为3 此时滑动区间为312（大顶堆是完全二叉树，所以这里12不会变化顺序，但是这里也不重要，因为最大的元素一定在最前面，那么后面的元素就不会有影响，只要最大的不在滑动区间内就一定会被删除，这几个方法就保证了不会出问题），最大为3再往下3221（至于为什么是321，这是堆的性质，不清楚的话，我可以下期出一篇文章讲），最大还是3。

      import java.util.*;public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 结果数组的初始化int n = nums.length;int[] result = new int[n - k + 1];// 定义大顶堆，存储值和索引，按值降序排序PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0] // 按值降序);// 初始化堆，加入前 k 个元素for (int i = 0; i < k; i++) {maxHeap.offer(new int[]{nums[i], i});}// 第一个窗口的最大值result[0] = maxHeap.peek()[0];// 滑动窗口，从 k 到 nums.lengthfor (int i = k; i < n; i++) {// 加入新元素maxHeap.offer(new int[]{nums[i], i});// 移动窗口左边界，确保堆顶的索引在窗口内while (maxHeap.peek()[1] <= i - k) {maxHeap.poll();}// 记录当前窗口的最大值result[i - k + 1] = maxHeap.peek()[0];}return result;}
      }
      

   2. 单调队列（其实就是保持顺序的双端队列），用双端队列的原因就是因为可以前删后加

      单调队列是按照大小顺序排列的，其实在本题很多情况都是区间只有一个元素，因为只要出现新元素比尾元素大，那么就不断poll尾元素，while循环直到不行位置，可以发现，始终是保持数组顺序的。所以删除操作只要用if判断队首是不是不在区间内即可。具体细节参考如下

      import java.util.*;public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> queue = new LinkedList<>();int n = nums.length;int[] result = new int[n - k + 1];// 如果新元素比队尾元素大，则删除队尾元素，不停的while循环，这样保证了滑动窗口不会被打乱// 这里初始化，不会有问题for (int i = 0; i < k; ++i) {while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {queue.pollLast();}queue.offerLast(i);}result[0] = nums[queue.peekFirst()];// 因为是按照顺序排列的单调双端队列，首先要删除左边界外的元素，每次循环一次判断一次就好，因为是按照顺序排布的// 不用每次while循环，是真正的按照顺序排列，堆是有多条分支的，所以它会出现顺序打乱，所以堆是使用while循环的// 首先删除不在范围内的元素，但要保证滑动窗口不能为空，推荐把删除判断写在加入结果列表的前面for (int i = k; i < n; ++i) {while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {queue.pollLast();}queue.offerLast(i);if (queue.peekFirst() <= i - k) {queue.pollFirst();}result[i - k + 1] = nums[queue.peekFirst()];}return result;}
      }
      

2. 前k个高频元素

   力扣347

   

   像这种统计次数的，一眼哈希表，后续就按照大小排列，取前k个就好，这里是使用工具类自己排序+stream优雅书写，思路明了,主要要把结果转换为int数组

   class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> count = new HashMap<>();// 统计每个数字的频率for (int num : nums) {count.put(num, count.getOrDefault(num, 0) + 1);}int[] result = count.entrySet().stream().sorted((a, b) -> b.getValue().compareTo(a.getValue())) .limit(k).mapToInt(Map.Entry::getKey)  // 转换为int类型，一个流只能终结一次.toArray();return result;}
   }