理论

栈与队列 - 图1

第一章 刷题

栈和队列题目不分类

232. 用栈实现队列

准备两个栈push和pop：用户给我的数永远进push栈、用户要的数据永远从pop拿；
如果有数据进来，则压入push栈
如果拿数据，看pop栈有没有，如果有，直接pop；如果没有，看push栈有没有；没有报错；有则让push栈数据全部进入pop栈，再返回栈顶。
倒这个行为有两个限制：1.如果push的数据要向pop栈倒，则必须一次性倒完；如果pop栈有东西，push栈一定不能倒。

  1. class MyQueue {
  2.     Stack<Integer> push;
  3.     Stack<Integer> pop;
  4.     /** Initialize your data structure here. */
  5.     public MyQueue() {
  6.         push = new Stack<Integer>();
  7.         pop = new Stack<Integer>();
  8.     }
  10.     /** Push element x to the back of queue. */
  11.     public void push(int x) {
  12.         push.push(x);
  13.     }
  15.     /** Removes the element from in front of queue and returns that element. */
  16.     public int pop() {
  17.         this.dao();
  18.         if (pop.isEmpty()) {
  19.             throw new RuntimeException("no data");
  20.         }
  21.         return pop.pop();
  22.     }
  24.     /** Get the front element. */
  25.     public int peek() {
  26.         this.dao();
  27.         if (pop.isEmpty()) {
  28.             throw new RuntimeException("no data");
  29.         }
  30.         return pop.peek();
  31.     }
  33.     /** Returns whether the queue is empty. */
  34.     public boolean empty() {
  35.         this.dao();
  36.         return pop.isEmpty();
  37.     }
  39.     private void dao() {
  40.         if (!pop.isEmpty()) {
  41.             return;
  42.         }
  43.         while (!push.isEmpty()) {
  44.             pop.push(push.pop());
  45.         }
  46.     }
  47. }
  49. /**
  50.  * Your MyQueue object will be instantiated and called as such:
  51.  * MyQueue obj = new MyQueue();
  52.  * obj.push(x);
  53.  * int param_2 = obj.pop();
  54.  * int param_3 = obj.peek();
  55.  * boolean param_4 = obj.empty();
  56.  */

225. 用队列实现栈

其实实现起来很傻：无非就是如何放数据和如何取数据！
准备两个队列a和b
有数据放入，则放入队列a；取数据时，将队列a中数据放入b，要留一个弹出；再取还是如此

数永远保存在data队列，只有出或者peek操作时，才到help队列，然后又立刻索引变换过来。
就是这么简单：

  1. class MyStack {
  2.     private Queue<Integer> data;
  3.     private Queue<Integer> help;
  5.     /** Initialize your data structure here. */
  6.     public MyStack() {
  7.         data = new LinkedList<Integer>();
  8.         help = new LinkedList<Integer>();
  9.     }
  11.     /** Push element x onto stack. */
  12.     public void push(int x) {
  13.         data.offer(x);
  14.     }
  16.     /** Removes the element on top of the stack and returns that element. */
  17.     public int pop() {
  18.         if (data.isEmpty()) {
  19.             throw new RuntimeException("no data");
  20.         }
  21.         while (data.size() != 1) {
  22.             help.offer(data.poll());
  23.         }
  24.         swap();
  25.         return help.poll();
  26.     }
  28.     /** Get the top element. */
  29.     public int top() {
  30.         if (data.isEmpty()) {
  31.             throw new RuntimeException("no data");
  32.         }
  33.         while (data.size() != 1) {
  34.             help.offer(data.poll());
  35.         }
  36.         swap();
  37.         int num = help.poll();
  38.         data.offer(num);
  39.         return num;
  40.     }
  42.     /** Returns whether the stack is empty. */
  43.     public boolean empty() {
  44.         return data.isEmpty();
  45.     }
  47.     private void swap() {
  48.         Queue<Integer> temp = data;
  49.         data = help;
  50.         help = temp;
  51.     }
  52. }
  54. /**
  55.  * Your MyStack object will be instantiated and called as such:
  56.  * MyStack obj = new MyStack();
  57.  * obj.push(x);
  58.  * int param_2 = obj.pop();
  59.  * int param_3 = obj.top();
  60.  * boolean param_4 = obj.empty();
  61.  */

20. 有效的括号

系统中处处都是栈的应用！
由于栈结构的特殊性，非常适合做对称匹配类的题目。

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         Stack<Character> stack = new Stack<Character>();
  4.         for (int i = 0; i < s.length(); i++) {
  5.             char ch = s.charAt(i);
  6.             if (stack.isEmpty() || ch == '(' || ch == '{' || ch == '[') {
  7.                 stack.push(ch);
  8.             } else {
  9.                 char left = stack.peek();
  10.                 if ((left == '(' && ch == ')') || (left == '[' && ch == ']') || (left == '{' && ch == '}')) {
  11.                     stack.pop();
  12.                 } else {
  13.                     return false;
  14.                 }
  15.             }
  16.         }
  17.         return stack.isEmpty();
  18.     }
  19. }

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

匹配问题都是栈的强项！
如果想不到栈，就很难办了！
实话说，官网代码比我写的好的多，我的就不贴了！

  1. class Solution {
  2.     public String removeDuplicates(String S) {
  3.         StringBuffer stack = new StringBuffer();
  4.         int top = -1;
  5.         for (int i = 0; i < S.length(); ++i) {
  6.             char ch = S.charAt(i);
  7.             if (top >= 0 && stack.charAt(top) == ch) {
  8.                 stack.deleteCharAt(top);
  9.                 --top;
  10.             } else {
  11.                 stack.append(ch);
  12.                 ++top;
  13.             }
  14.         }
  15.         return stack.toString();
  16.     }
  17. }

150. 逆波兰表达式求值

有没有想过计算机是如何处理表达式的？
image.png
其实看到题目九知道怎么解了。
这里大家思考一下，怎么将一个我们可以看懂的式子转化成逆波兰表达法才是难点！

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<String>();
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")) {
                stack.push(calculate(Integer.valueOf(stack.pop()), Integer.valueOf(stack.pop()), tokens[i]) + "");
            } else {
                stack.push(tokens[i]);
            }
        }
        return Integer.valueOf(stack.pop());
    }
    private int calculate(int num2, int num1, String flag) {
        if (flag.equals("+")) {
            return num1 + num2;
        } else if (flag.equals("-")) {
            return num1 - num2;
        } else if (flag.equals("*")) {
            return num1 * num2;
        } else {
            return num1 / num2;
        }
    }
}

239. 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return null;
        }
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            while (!qmax.isEmpty() && nums[qmax.peekLast()] <= nums[i]) {
                qmax.pollLast();
            }
            qmax.addLast(i);
            if (qmax.peekFirst() == i - k) {
                qmax.pollFirst();
            }
            if (i >= k - 1) {
                res[index++] = nums[qmax.peekFirst()];
            }
        }
        return res;
    }
}

347. 前 K 个高频元素

image.png

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

image.png
image.png