java 实现一个最小栈

最小栈

1.实现思路

• 实现一个stack栈 和 minStack栈。
• 先将数据一个一个压入到 stack 中。
• 找到 stack 中的最小值。
• minStack中始终要压入当前最小的值。

2.实现过程演示

1、先将元素压入到 stack 中，若当前的 minStack 中没有元素。则当前的元素为最小值。



2、将最小压入到 minStack 中。

3、压入3和0这两个数据，0成为了当前的最小值。



4、将当前最小值0压入到 minStack 中

5、继续压入9，当前的最小值还是0。



6、此时压入 -9 ，-9为此时最小值，将它压入minStack中

7、如果此时压入到stack中的值等于当前最小的值，也要压入到minStack中

总结：

如果要存放的值为x，minStack的栈顶元素为y。

• x < y 时，要压入元素到minStack中。
• x == y 时，要压入元素到minStack中。
• x > y 时，不需要压入，

3.代码实现思路

3.1 压入思路

1. 先实现两个栈，一个是普通栈，一个是最小栈。

 stack = new Stack<>();
 minStack = new Stack<>();
1
2

2. 往stack中压入一个元素。

 stack.push(val);
1

3. 若此时minStack为空，就将 stack 中元素压入到minStack中。

 if (minStack.empty()) {
     minStack.push(val);
 }
1
2
3

4. 若不为空就比较一下，将当前最小值压入到minStack中。

int stackTop = stack.peek();
if (val <= stackTop) {
    minStack.push(val);
}
1
2
3
4

3.2 弹出思路

1. stack不能是空的，若是空的就不能弹出。

 if (!stack.empty()) {
 }
1
2

2. 若当前stack不为空，弹出stack栈顶元素，定义一个变量接收。

 int stackX = stack.pop();
1

3. 如果stack栈顶的值等于minStack的栈顶的值就弹出minStack栈栈顶的元素

if (stackX == minStack.peek()) {
    minStack.pop();
}
1
2
3

3.3 如何返回栈顶元素的下标

1. 前提是栈不为空 - 直接用peek返回

if (!stack.empty()) {
    return stack.peek();
}
1
2
3

2. 若栈是空的，直接返回-1表示栈为空。

return -1;
1

3.4 如何返回栈的最小值

1. 因为此时栈顶会一直是最小值，所以直接返回栈顶元素即可

 return minStack.peek();
1

2. 前提是栈不为空，若此时栈为空，就直接返回-1表示此时栈为空。

return -1;
1

4.整体代码实现

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

    public void minStack() {
        stack = new Stack<>();
        minStack = new Stack<>();

    }

    public void push(int val) {
        stack.push(val);//给stack压入一个值
        //最小栈为空
        if (minStack.empty()) {
            minStack.push(val);//压入到最小栈
        }else {
            //比较大小
            int stackTop = stack.peek();//看一下栈顶元素的值
            if (val <= stackTop) {
                //将这个栈顶元素压入到minStack中
                minStack.push(val);
            }
        }
    }

    public void pop() {
        if (!stack.empty()) {
            int stackX = stack.pop();//压入到stackX中
            //如果stack的栈顶的值等于最小栈的栈顶的值
            if (stackX == minStack.peek()) {
                //弹出
                minStack.pop();
            }
        }
    }

    public int top() {
        //不为空
        if (!stack.empty()) {
            //返回栈顶位置的下标
            return stack.peek();
        }
        return -1;
    }

    public int getMin() {
        if (minStack.empty()) {
            return -1;
        }
        //不为空返回栈顶的下标 - 栈顶会一直放最小值
        return minStack.peek();
    }
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53