【代码随想录】-栈和队列专栏（Java）

理论基础

栈：先进后出

队列：先进先出

Java中涉及到栈的使用时推荐使用Deque

用栈实现队列 leetcode-232

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; //out不为空直接返回
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}
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

队列实现栈 leetcode-225

/**
 * 225. 用队列实现栈
 */
class MyStack {
    Queue<Integer> queueStack;
    Queue<Integer> queueTemp; //临时存放

    public MyStack() {
        queueStack = new LinkedList<>();
        queueTemp = new LinkedList<>();
    }

    public void push(int x) {
        //栈的特性，先进后出，此时来的新元素根据队列的特性会先出
        //把新来的元素先入临时队列，再将队列Stack中的元素复制到临时队列，则新来的元素就变为最后一个
        queueTemp.offer(x);
        while (!queueStack.isEmpty()){
            queueTemp.offer(queueStack.poll());
        }
        //最后将两者交换
        Queue<Integer> temp;
        temp = queueStack;
        queueStack = queueTemp;
        queueTemp = temp;
    }

    public int pop() {
        return  queueStack.poll();
    }

    public int top() {
        return queueStack.peek();
    }

    public boolean empty() {
        return queueStack.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

有效的括号 leetcode-20

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if(chars[i]=='(') stack.push(')'); //比较巧妙的避开左右括号对应
        else if(chars[i]=='{') stack.push('}');
        else if(chars[i]=='[') stack.push(']');
        //栈为空，字符串还没遍历完证明右括号多余
        //栈里没有匹配的字符
        else if(stack.isEmpty() || stack.peek() != chars[i]) return false;
        else stack.pop(); //栈顶与当前字符相同，出栈
    }
    return stack.isEmpty(); //若栈不为空，证明左括号有多余的
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

方法1，双指针法：

public String removeDuplicates(String s) {
    char[] chars = s.toCharArray();
    for (int i = 1; i < chars.length; i++) {
        int j = i-1;
        while (i<chars.length && chars[i] == chars[j]){
            chars[i++] = 32;
            chars[j] = 32;
            while (j>0 && chars[j]==32) j--; //j退回到第一个空格相邻的索引
        }
    }
    return new String(chars).replace(" ","");
}
1
2
3
4
5
6
7
8
9
10
11
12

方法2，api栈，速度较慢：

/**
     * api栈 这样写速度慢
     * @param s
     * @return
     */
public String removeDuplicates3(String s) {
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if(!stack.isEmpty() && stack.peek() == chars[i]){
            stack.pop(); //出队
        }else {
            stack.push(chars[i]); //入队
        }
    }
    StringBuilder sb = new StringBuilder("");
    while (!stack.isEmpty()){
        sb.append(stack.pop());
    }
    return sb.reverse().toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法3，模拟栈，速度和第一种相仿：

/**
     * 模拟栈
     * @param s
     * @return
     */
public String removeDuplicates(String s) {
    StringBuilder sb = new StringBuilder("");
    int top = -1; //栈顶指针
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if(top >=0 && sb.charAt(top)==chars[i]){
            sb.deleteCharAt(top);
            top--;
        }else {
            sb.append(chars[i]);
            top++;
        }
    }
    return sb.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法4，相当于对上面算法的优化,StringBuilder,StringBuffer比较慢

public String removeDuplicates4(String s) {
    int top = -1; //栈顶指针
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if(top == -1 || chars[top] != chars[i]){
            chars[++top] = chars[i];
        }else {
            top--;
        }
    }
    return String.valueOf(chars,0,top+1); //返回 char 数组的字符串表示形式。左闭右开
}
1
2
3
4
5
6
7
8
9
10
11
12

逆波兰表达式求值 leetcode-150

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new LinkedList(); //java 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 temp1 = stack.pop();
            int temp2 = stack.pop();
            stack.push(temp2 / temp1);
        } else {
            stack.push(Integer.valueOf(s));
        }
    }
    return stack.pop();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

滑动窗口最大值 leetcode-239

暴力法超时……

public int[] maxSlidingWindow(int[] nums, int k) {
    //使用双端队列 队列中存放的是下标
    Deque<Integer> deque = new LinkedList<>();
    int len = nums.length;
    int[] res = new int[len - k + 1]; //结果数组
    //left和right分别是滑动窗口的左右下标
    for (int right = 0; right < len; right++) {
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[right]) {
            // 队尾元素小于考察元素  出队
            deque.removeLast();
        }
        deque.addLast(right); //队列空或者考察元素大于队尾元素 入队
        int left = right - k + 1; //窗口左侧边界
        //窗口已形成

        // 队首元素下标小于left 证明队首不在窗口内 删除队首
        if (deque.peekFirst() < left) {
            deque.removeFirst();
        }
        //窗口形成
        if (right + 1 >= k) { //下标从0开始
            res[left] = nums[deque.peekFirst()]; //队首即最大
        }
    }
    return res;
}
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

前 K 个高频元素 leetcode-347

/**
     * 347. 前 K 个高频元素
     *
     * @param nums
     * @param k
     * @return
     */
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>(); //统计频率
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    //定义优先级队列 其实是披着外衣队列的堆
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            //compare 正的交换（true） 负的不交换
            //a表示位于前面的对象 b表示位于后面的对象
            return map.get(a) - map.get(b);  //队头到队尾升序就是小根堆
        }
    });

    for (Integer key : map.keySet()) {
        if (priorityQueue.size() < k) {
            priorityQueue.add(key);
        } else if (map.get(key) > map.get(priorityQueue.peek())) {
            priorityQueue.poll();
            priorityQueue.add(key);
        }
    }
    int[] res = new int[k];
    int index = 0;
    while (!priorityQueue.isEmpty()) {
        res[index++] = priorityQueue.poll();
    }
    return res;
}
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