The leecode algorithm "155. Minimum Stack" is annotated and simple.

Content of the original topic

Design a stack that supports push, pop, top operations and can retrieve the smallest elements in a constant time.

push(x) - Push element x into the stack.
pop() - Delete the element at the top of the stack.
top() - Gets the top element of the stack.
getMin() - Retrieves the smallest element in the stack.
Examples:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
MinStack. getMin (); --> Return - 3.
minStack.pop();
MinStack. top (); --> Return 0.
MinStack. getMin (); --> Return - 2.

Source: LeetCode
Links: https://leetcode-cn.com/problems/min-stack
Copyright belongs to the seizure network. For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

Examination of topics:

The meaning of this question is to create a class to satisfy.
push(x) - Push element x into the stack.
pop() - Delete the element at the top of the stack.
top() - Gets the top element of the stack.
getMin() - Retrieves the smallest element in the stack.
These requirements

Idea analysis:

There are two ways to implement code:

1. Auxiliary stack and data stack synchronization

Features: Simple coding, without considering some boundary conditions, there is a little bad: auxiliary stack may store some "unnecessary" elements.

2. Asynchronization of Auxiliary Stack and Data Stack

Features: From the idea of "assistant stack and data stack synchronization", we know that when the number of data stacks is increasing, we need to place the same elements on the top of the assistant stack as the current assistant stack, which is a bit of "waste". Based on this, we do some "optimization", but we need to pay attention to some boundary conditions in coding.

(1) When the auxiliary stack is empty, the number of new entries must be put in.

(2) When the number of new arrivals is less than or equal to the top element of the auxiliary stack, they are put in. Particular attention should be paid to the fact that "equal" here should be taken into account, because when leaving the stack, elements of continuity, equality and minimum value should be synchronized out of the stack.

(3) When leaving the stack, the top element of the auxiliary stack is equal to the top element of the data stack before leaving the stack.

Summarize: When leaving the stack, the minimum out of the stack is synchronized; when entering the stack, the minimum in the stack is synchronized.

Contrast: I think the way of "synchronization stack" is better, because the idea is clear, because all operations are synchronized, so debugging code and positioning problems are simple. "Asynchronous stack", although reducing some space, but in the "out of the stack" and "in the stack" to make judgments, there are also performance consumption.

Method 1: Assist stack and data stack synchronization

Code:

class MinStack {
   // Data stack
    private Stack<Integer> data;
    // Auxiliary Stack
    private Stack<Integer> helper;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        data = new Stack<>();
        helper = new Stack<>();
    }

    public void push(int x) {
        // Data stack and auxiliary stack must add elements
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x) {
            helper.add(x);
        } else {
            helper.add(helper.peek());
        }
    }

    public void pop() {
        if (!data.isEmpty()) {
            data.pop();
            helper.pop();
        }
    }

    public int top() {
        if (!data.isEmpty()) {
            return data.peek();
        }
        throw new RuntimeException("The element in the stack is empty, this operation is illegal");
    }

    public int getMin() {
        if (!data.isEmpty()) {
            return helper.peek();
        }
        throw new RuntimeException("The element in the stack is empty, this operation is illegal");
    }
}

Method 1: Assist stack and data stack synchronization

class MinStack {
     // Data stack
    private Stack<Integer> data;
    // Auxiliary Stack
    private Stack<Integer> helper;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        data = new Stack<>();
        helper = new Stack<>();
    }

    public void push(int x) {
        // Data stack and auxiliary stack must add elements
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x) {
            helper.add(x);
        }
    }

    public void pop() {
        if (!data.isEmpty()) {
            Integer pop = data.pop();
            if (pop <= helper.peek()) {
                helper.pop();
            }
        }
    }

    public int top() {
        if (!data.isEmpty()) {
            return data.peek();
        }
        throw new RuntimeException("The element in the stack is empty, this operation is illegal");
    }

    public int getMin() {
        if (!data.isEmpty()) {
            return helper.peek();
        }
        throw new RuntimeException("The element in the stack is empty, this operation is illegal");
    }
}