232. 用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

两个栈

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

  1. class MyQueue {
  2.         Stack<Integer> stackIn = new Stack<>();
  3.         Stack<Integer> stackOut = new Stack<>();
  5.         public MyQueue() {
  7.         }
  9.         public void push(int x) {
  10.             stackIn.push(x);
  11.         }
  14.         public int pop() {
  15.             dumpstackIn();
  16.             return stackOut.pop();
  17.         }
  20.         public int peek() {
  21.             dumpstackIn();
  22.             return stackOut.peek();
  23.         }
  25.         public boolean empty() {
  26.             return stackIn.isEmpty() && stackOut.isEmpty();
  27.         }
  29.         private void dumpstackIn() {
  30.             if (!stackOut.isEmpty()) return;
  31.             while (!stackIn.isEmpty()) {
  32.                 stackOut.push(stackIn.pop());
  33.             }
  34.         }
  35. }

225. 用队列实现栈

https://leetcode-cn.com/problems/implement-stack-using-queues/

两个队列

队列模拟栈，其实一个队列就够了，那么我们先说一说两个队列来实现栈的思路。
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！
如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

  1.  class MyStack {
  2.         Queue<Integer> queue1;
  3.         Queue<Integer> queue2; // 备份队列
  5.         public MyStack() {
  6.             queue1 = new LinkedList<>();
  7.             queue2 = new LinkedList<>();
  8.         }
  10.         public void push(int x) {
  11.             queue1.offer(x);
  12.         }
  14.         public int pop() {
  15.             int size = queue1.size();
  16.             for (int i = 0; i < size - 1; i++) {
  17.                 queue2.offer(queue1.poll());
  18.             }
  19.             int res = queue1.poll();
  20.             while (!queue2.isEmpty()) {
  21.                 queue1.offer(queue2.poll());
  22.             }
  23.             return res;
  24.         }
  26.         public int top() {
  27.             int pop = pop();
  28.             queue1.offer(pop);
  29.             return pop;
  30.         }
  32.         public boolean empty() {
  33.             return queue1.isEmpty();
  34.         }
  35.     }

优化：一个队列

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

  1. // 一个队列
  2.     class MyStack2 {
  3.         Queue<Integer> queue;
  5.         public MyStack2() {
  6.             queue = new LinkedList<>();
  7.         }
  9.         public void push(int x) {
  10.             queue.offer(x);
  11.         }
  13.         public int pop() {
  14.             int size = queue.size();
  15.             for (int i = 0; i < size - 1; i++) {
  16.                 queue.offer(queue.poll());
  17.             }
  18.             return queue.poll();
  19.         }
  21.         public int top() {
  22.             int pop = pop();
  23.             queue.offer(pop);
  24.             return pop;
  25.         }
  27.         public boolean empty() {
  28.             return queue.isEmpty();
  29.         }
  30.     }

20. 有效的括号

https://leetcode-cn.com/problems/valid-parentheses/

  1.  public boolean isValid(String s) {
  2.          char[] str = s.toCharArray();
  3.          Stack<Character> stack = new Stack<>();
  4.          for (char c : str) {
  5.              if (c == '(' || c == '[' || c == '{') {
  6.                  // 遇到左括号就把对应的右括号入栈
  7.                  stack.push(c == '(' ? ')' : c == '[' ? ']' : '}');
  8.              } else {
  9.                  if (stack.isEmpty()) {
  10.                      return false;
  11.                  }
  12.                  if (c != stack.pop()) {
  13.                      return false;
  14.                  }
  15.              }
  16.          }
  17.          return stack.isEmpty();
  18.  }

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

拿字符串作为栈

https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/submissions/

  1. public String removeDuplicates(String s) {
  2.         // 拿字符串直接作为栈，省去了栈还要转为字符串的操作。
  3.         StringBuilder sb = new StringBuilder();
  4.         int top = -1;
  5.         for (int i = 0; i < s.length(); i++) {
  6.             char c = s.charAt(i);
  7.             if (top >= 0 && sb.charAt(top) == c) {
  8.                 sb.deleteCharAt(top--);
  9.             } else {
  10.                 sb.append(c);
  11.                 top++;
  12.             }
  13.         }
  14.         return sb.toString();
  15.     }

150. 逆波兰表达式求值

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

  1. public int evalRPN(String[] tokens) {
  2.         Stack<Integer> stack = new Stack<>();
  3.         for (String s : tokens) {
  4.             if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
  5.                 // 注意这里先弹出的是num2， 后弹出的是num1， 因为后面涉及到除法
  6.                 int num2 = stack.pop();
  7.                 int num1 = stack.pop();
  8.                 int ans = 0;
  9.                 switch (s){
  10.                     case "+":
  11.                         ans = num1 + num2;
  12.                         break;
  13.                     case "-":
  14.                         ans = num1 - num2;
  15.                         break;
  16.                     case "*":
  17.                         ans = num1 * num2;
  18.                         break;
  19.                     case "/":
  20.                         ans = num1 / num2;
  21.                         break;
  22.                 }
  23.                 stack.push(ans);
  24.             } else {
  25.                 stack.push(Integer.valueOf(s));
  26.             }
  27.         }
  28.         return stack.peek();
  29.     }

239. 滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

  • 笔记 https://www.yuque.com/docs/share/3d2b3396-b0af-4caf-945b-08b9ebe9a9d9?# 《滑动窗口及其更新结构》

    1. public int[] maxSlidingWindow(int[] nums, int k) {
    2.       // 双端队列，大->小, 存下标,
    3.       LinkedList<Integer> qMax = new LinkedList<>();
    4.       int[] ans = new int[nums.length - k + 1];
    5.       // L一方面是窗口的L， 又可以作答案数组的索引
    6.       int L = 0;
    7.       for (int R = 0; R < nums.length; R++) {
    8.           while (!qMax.isEmpty() && nums[qMax.peekLast()] <= nums[R]) {
    9.               qMax.pollLast();
    10.           }
    12.           qMax.addLast(R);
    13.           /* 两层含义： R - k是过期下标
    14.                1. 如果窗口没有形成k的长度， 是不弹出数字的
    15.                2. L要缩之前，看下L是不是双端队列中的头，若是，则此刻的L是即将要过期的，弹出
    16.                */
    17.           if (qMax.peekFirst() == R - k) {
    18.               qMax.pollFirst();
    19.           }
    21.           //开始记录
    22.           if (R >= k - 1) {
    23.               ans[L++] = nums[qMax.peekFirst()];
    24.           }
    25.       }
    26.       return ans;
    27. }

    347. 前K个高频元素

    https://leetcode-cn.com/problems/top-k-frequent-elements/

  • 笔记https://www.yuque.com/docs/share/2ca380dd-f64b-49ec-8f95-3d7834dfc9f4?# 《347. 前K个高频元素》

    1. public class Node {
    2.       int num;
    3.       int count;
    4.       public Node(int num) {
    5.           this.num = num;
    6.           this.count = 1;
    7.       }
    8.   }
    10.   public int[] topKFrequent(int[] nums, int k) {
    11.       int[] result = new int[k];
    12.       // map统计词频
    13.       HashMap<Integer, Node> map = new HashMap<>();
    14.       for (int num : nums) {
    15.           if (!map.containsKey(num)) {
    16.               map.put(num, new Node(num));
    17.           } else {
    18.               map.get(num).count++;
    19.           }
    20.       }
    21.       // 小顶堆
    22.       PriorityQueue<Node> minHeap = new PriorityQueue<>((o1, o2) -> o1.count - o2.count );
    23.       for (Node node : map.values()) {
    24.           minHeap.add(node);
    25.           if (minHeap.size() > k) {
    26.               minHeap.poll();
    27.           }
    28.       }
    30.       for (int i = 0; i < k; i++) {
    31.           result[i] = minHeap.poll().num;
    32.       }
    33.       return result;
    34.   }