# Design the smallest stack, that is, there are the basic operations of the stack, push, pop, peek, and the function of returning the minimum value in the stack, getMin

Tip: previously, we said that the system stack can push, pop and peek normally
Now we need to design a minimum stack, and the o(1) speed returns the minimum value in the current stack.

# subject

Design the minimum stack, that is, the basic operations of the stack push, pop, peek,
There is also a new function: getMin() that returns the minimum value in the current stack

# 1, Examining questions

Example: for example, press in 2 3 1 4 5
The corresponding minimum value in the stack should be:
2 2 1 1 1
Please implement such a stack: the smallest stack

# 2, Design method of minimum stack

In fact, the smallest stack can also be seen from the example, that is, two system stacks: data stack and min stack
data is responsible for daily push, pop and peek functions
Each time you push, you need to compare the new value and the value at the top of the stack in min
If:
(1) Value > = the value at the top of Min stack: you need to assign the top of Min stack to value and store it in min, which means that the minimum value has remained unchanged
(2) Value < min the value at the top of the stack: a new minimum value does come. Just store value in Min directly, which means that the new minimum value comes
In that case, data will do its own thing
Min ensures that the quantity is the same as that of data. Moreover, the minimum value of data in the current range is placed in min and will not be disordered

Just look at the picture
When there is only 2 in data, min must also be only 2, which is the minimum value
When there is 32 in the data, the minimum value is naturally 2,
When there is 132 in the data, a 1 is smaller than 2. Naturally, 1 will be the minimum from now on
If the subsequent number is greater than or equal to 1, 1 will naturally be stored at the top of the stack in min
Unless there is a 0 or smaller, let min put a smaller one

(3) When pop-up, data will perform its own routine operation, and then min will pop up one to ensure that the quantity within the range is consistent with data;

Hand tear Code:

```//Review the minimum stack, very simple, is to take another system stack and put the minimum value entered each time
public static class MinStack{
//Dual system stack
public Stack<Integer> dataStack;
public Stack<Integer> minStack;

public MinStack(){
dataStack = new Stack<>();
minStack = new Stack<>();
}

//isEmpty
public boolean isEmpty(){
return dataStack.isEmpty();
}

//push
public void push(int value){
//You can play your own game normally
dataStack.push(value);
//The key is to judge the new value and the top of minStack
if (minStack.isEmpty()) minStack.push(value);//The number that comes first must be the smallest
else if (value >= minStack.peek()) {
value = minStack.peek();//Re assign value and then add min. don't forget
minStack.push(value);
}
else minStack.push(value);//If you skip the above if, it means that the smaller one is coming
}

//pop
public int pop(){
//No error reporting
if (dataStack.isEmpty()) throw new RuntimeException("No number!");
//min should be consistent with the data quantity and range, so a pop-up should be made first
minStack.pop();
return dataStack.pop();
}

//peek
public int peek(){
//Report an error if there is no one
if (dataStack.isEmpty()) throw new RuntimeException("No number!");
//It depends on the top of the stack. It has nothing to do with min
return dataStack.peek();
}

//Here comes the key function, getMin
public int getMin(){
//No element, error reported
if (minStack.isEmpty()) throw new RuntimeException("No number!");
//If yes, naturally, it will return to the top of minStack, which has nothing to do with data
return minStack.peek();
}
}
public static void test2(){
MinStack stack = new MinStack();

stack.push(2);
System.out.println("Current minimum:"+ stack.getMin());//2
stack.push(3);
System.out.println("Current minimum:"+ stack.getMin());//2
stack.push(1);
System.out.println("Current minimum:"+ stack.getMin());//1
stack.push(4);
System.out.println("Current minimum:"+ stack.getMin());//1
stack.push(5);
System.out.println("Current minimum:"+ stack.getMin());//1
System.out.println("Stack top data:"+ stack.peek());//5
System.out.println(stack.isEmpty());
System.out.println(stack.pop());//5
System.out.println("Current minimum:"+ stack.getMin());//1
System.out.println(stack.pop());//4
System.out.println("Current minimum:"+ stack.getMin());//1
System.out.println(stack.pop());//1
System.out.println("Current minimum:"+ stack.getMin());//2
System.out.println(stack.pop());//3
System.out.println("Current minimum:"+ stack.getMin());//2
System.out.println(stack.pop());//2
System.out.println(stack.isEmpty());
}

public static void main(String[] args) {
//        test();
test2();
}
```

Look at the result, it's perfect:

```Current minimum: 2
Current minimum: 2
Current minimum: 1
Current minimum: 1
Current minimum: 1
Stack top data: 5
false
5
Current minimum: 1
4
Current minimum: 1
1
Current minimum: 2
3
Current minimum: 2
2
true
```

# summary

Tip: important experience:

1) The smallest stack is nothing more than a stack that stores the minimum value. If it is replaced by the largest stack, it is estimated to be very simple
2) Use the underlying system data structure to realize the new data structure you want, which is the significance of learning data structure and algorithm. This is the essence of large factories to recruit you to enter the optimization algorithm and realize new business functions in the future.

Posted by dragon_sa on Sun, 01 May 2022 01:52:25 +0300