java 实现一个最小栈

约定不等于承诺〃 2023-10-02 22:56 6阅读 0赞

#### 文章目录 ####

*  最小栈
 *   *  1.实现思路
     *  2.实现过程演示
     *  3.代码实现思路
     *   *  3.1 压入思路
         *  3.2 弹出思路
         *  3.3 如何返回栈顶元素的下标
         *  3.4 如何返回栈的最小值
     *  4.整体代码实现

![3bf2305b361046a485818e4685ab2a68.gif_pic_center][]

## 最小栈 ##

### 1.实现思路 ###

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

### 2.实现过程演示 ###

1、先将元素压入到 stack 中，若当前的 minStack 中没有元素。则当前的元素为最小值。  
![72aa29926fbb4a6985eab5ccd6cc52f3.png_pic_center][]  
  
  
2、将最小压入到 minStack 中。  
![c778b6ed48f14fd9b3d2bbe9bd6bc7a9.png_pic_center][]

3、压入3和0这两个数据，0成为了当前的最小值。  
![3becaca5037b45c089c9b5c96d5016dc.png_pic_center][]  
  
  
4、将当前最小值0压入到 minStack 中  
![0e947bb6901d4f6baf8f260ba86a18c4.png_pic_center][]

5、继续压入9，当前的最小值还是0。  
![8d2712fcbc254a98aa99971593de0d20.png_pic_center][]  
  
  
6、此时压入 -9 ，-9为此时最小值，将它压入minStack中  
![82e9fdcddd6943f09e75714990872807.png_pic_center][]

7、如果此时压入到stack中的值等于当前最小的值，也要压入到minStack中  
![在这里插入图片描述][f47ce3d98fc841e6a9de390c4bf36b71.png_pic_center]

**总结：**

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

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

### 3.代码实现思路 ###

#### 3.1 压入思路 ####

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

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

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

stack.push(val);

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

if (minStack.empty()) {
        
         minStack.push(val);
     }

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

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

#### 3.2 弹出思路 ####

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

if (!stack.empty()) {
        
     }

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

int stackX = stack.pop();

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

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

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

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

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

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

return -1;

#### 3.4 如何返回栈的最小值 ####

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

return minStack.peek();

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

return -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();
        }
    }

![c1985c04075c4697b15cd627d34b11e2.gif_pic_center_pic_center][]

[3bf2305b361046a485818e4685ab2a68.gif_pic_center]: https://img-blog.csdnimg.cn/3bf2305b361046a485818e4685ab2a68.gif#pic_center
[72aa29926fbb4a6985eab5ccd6cc52f3.png_pic_center]: https://img-blog.csdnimg.cn/72aa29926fbb4a6985eab5ccd6cc52f3.png#pic_center
[c778b6ed48f14fd9b3d2bbe9bd6bc7a9.png_pic_center]: https://img-blog.csdnimg.cn/c778b6ed48f14fd9b3d2bbe9bd6bc7a9.png#pic_center
[3becaca5037b45c089c9b5c96d5016dc.png_pic_center]: https://img-blog.csdnimg.cn/3becaca5037b45c089c9b5c96d5016dc.png#pic_center
[0e947bb6901d4f6baf8f260ba86a18c4.png_pic_center]: https://img-blog.csdnimg.cn/0e947bb6901d4f6baf8f260ba86a18c4.png#pic_center
[8d2712fcbc254a98aa99971593de0d20.png_pic_center]: https://img-blog.csdnimg.cn/8d2712fcbc254a98aa99971593de0d20.png#pic_center
[82e9fdcddd6943f09e75714990872807.png_pic_center]: https://img-blog.csdnimg.cn/82e9fdcddd6943f09e75714990872807.png#pic_center
[f47ce3d98fc841e6a9de390c4bf36b71.png_pic_center]: https://img-blog.csdnimg.cn/f47ce3d98fc841e6a9de390c4bf36b71.png#pic_center
[c1985c04075c4697b15cd627d34b11e2.gif_pic_center_pic_center]: https://img-blog.csdnimg.cn/c1985c04075c4697b15cd627d34b11e2.gif#pic_center#pic_center