栈

[yifanzheng]

栈

栈结构特点：后进者先出，先进者后出，只允许在一端插入和删除数据。

练习

• 用数组实现栈
• 用链表实现栈
• 有效的括号
• 最小栈
• 用栈实现队列
• 比较含退格的字符串
• 棒球比赛
• 下一个更大元素 I

[yifanzheng]

用数组实现栈

/**
 * 数组实现的顺序栈
 */
public class ArrayStack {

    /** 数组，存放元素 */
    private String[] datas;

    /** 栈中的元素个数 */
    private int size;

    /** 栈的容量 */
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.datas = new String[capacity];
        this.size = 0;
    }

    public boolean push(String value) {
        // 如果栈已经满了，则入栈失败，返回 false
        if (this.size == this.capacity) {
            return false;
        }
        this.datas[size++] = value;
        return true;
    }

    public String pop() {
        // 栈为空，就直接返回 null
        if (this.size == 0) {
            return null;
        }
        // 出栈时，从数组的末尾开始取出元素返回
        String value = this.datas[size - 1];
        // 释放内存
        this.datas[--size] = null;
        return value;
    }

    public int size() {
        return this.size;
    }
}

[yifanzheng]

用链表实现栈

/**
 * 链表实现栈
 */
public class LinkedListStack {

    private Node top;

    public void push(String value) {
        Node node = new Node(value, null);
        // 判断 top 是否为 null
        if (top != null) {
            node.next = top;
        }
        top = node;
    }

    public String pop() {
        if (top == null) {
            return null;
        }
        String value = top.getValue();
        top = top.next;
        return value;
    }

    private static class Node {
        private String value;
        private Node next;

        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }

        public String getValue() {
            return this.value;
        }
    }
}

[yifanzheng]

有效的括号

LeetCode 地址：20. 有效的括号

题解

public static boolean isValidBrackets(String s) {
       if (s == null || "".equals(s) || s.length() % 2 == 1) {
           return false;
       }
       Map<Character, Character> pairs = new HashMap<Character, Character>() {{
           put(')', '(');
           put(']', '[');
           put('}', '{');
       }};

       Stack<Character> stack = new Stack<>();
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           if (pairs.containsKey(c)) {
               // 防止出现类似 ")(&}" 这样的情况
               if (stack.isEmpty() || stack.peek() != pairs.get(c)) {
                   return false;
               }
               stack.pop();
           } else {
               stack.push(c);
           }
       }
       return stack.isEmpty();
}

[yifanzheng]

最小栈

LeetCode 地址：155. 最小栈

题解

public class MinStack {
    private Stack<Integer> valueStack;
    private Stack<Integer> minStack;

    public MinStack() {
        valueStack = new Stack<>();
        minStack = new Stack<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        valueStack.push(val);
        minStack.peek();
        minStack.push(Math.min(val, minStack.peek()));
    }

    public void pop() {
        valueStack.pop();
        minStack.pop();
    }

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

    public int getMin() {
       return minStack.peek();
    }

}

[yifanzheng]

用栈实现队列

LeetCode 地址：232. 用栈实现队列

题解

public class StackQueue {

    private Stack<Integer> stack;
    private Stack<Integer> queue;

    public StackQueue() {
        stack = new Stack<>();
        queue = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
    }

    public int pop() {
        if (queue.isEmpty()) {
            while (!stack.isEmpty()) {
                queue.push(stack.pop());
            }
        }
        return queue.pop();
    }

    public int peek() {
        if (queue.isEmpty()) {
            while (!stack.isEmpty()) {
                queue.push(stack.pop());
            }
        }
        return queue.peek();
    }

    public boolean empty() {
       return queue.isEmpty() && stack.isEmpty();
    }
}

[yifanzheng]

比较含退格的字符

LeetCode 地址：844. 比较含退格的字符串

题解

思路：将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两个字符串。使用栈进行字符存储，当遇到退格符，就弹出栈顶元素；当是遇到普通字符，就存入栈中。

public boolean backspaceCompare(String s, String t) {
    return parseStr(s).equals(parseStr(t));
}

private String parseStr(String str) {
    if (str == null) {
        return "";
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (c != '#') {
            sb.append(c);
            continue;
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    return sb.toString();
}

[yifanzheng]

棒球比赛

LeetCode 地址：682. 棒球比赛

题解

public int calPoints(String[] ops) {
    Deque<Integer> points = new LinkedList<>();
    for (String s : ops) {
        if (s.equals("C")) {
            points.pop();
            continue;
        }
        if (s.equals("D")) {
            Integer point = points.peek();
            points.push(2 * point);
            continue;
        }
        if (s.equals("+")) {
            Integer top = points.pop();
            Integer point = points.peek();
            points.push(top);
            points.push(top + point);
            continue;
        }

        points.push(Integer.parseInt(s));
    }
    int sum = 0;
    for (Integer point : points) {
        sum += point;
    }

    return sum;
}

[yifanzheng]

下一个更大元素 I

LeetCode 地址：496. 下一个更大元素 I

题解

思路：倒序遍历 nums2，次我们移动到数组中一个新的位置 ii，就将当前单调栈中所有小于 nums2[i] 的元素弹出单调栈，当前位置右边的第一个更大的元素即为栈顶元素，如果栈为空则说明当前位置右边没有更大的元素，然后我们将位置 ii 的元素入栈。

public int[] nextGreaterElements(int[] nums1, int[] nums2) {
    Deque<Integer> stack = new ArrayDeque<>();
    Map<Integer, Integer> greaterMap = new HashMap<>();
    for (int i = nums2.length - 1; i >= 0; i--) {
        int num = nums2[i];
        while (!stack.isEmpty() && num > stack.peek()) {
            stack.pop();
        }
        greaterMap.put(num, stack.isEmpty() ? -1 : stack.peek());
        stack.push(num);
    }

    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        res[i] = greaterMap.get(nums1[i]);
    }

    return res;
}