Design a stack with getmin function

subject ： Implement a special stack , On the basis of realizing the basic functions of stack , The operation of the smallest element in the return stack .

requirement ：1. pop、push、getMin The time complexity of operation is O(1).

2. The designed stack type can use the existing stack structure

answer ： Use two stacks , A stack stackData Is to save all the elements , Another stack stackMin Is to save the minimum value of each step in the current stack . There are two ways to realize it ：

The first one is ：

Push in data rules ：

Put the current number num Put it in stackData When the stack , Judge stackMin Is the stack empty , If it is empty , The current number num Also put stackMin in , If it's not empty , Will judge stackMin Stack top elements and num Size , If num<=stackMin Top element of stack , Just put num Also put stackMin Inside the stack .

Pop up data rules ：

Now? stackData The stack pops up the top element num, Judge num and stackMin Whether the elements at the top of the stack are equal . If it's not equal （ The inequality here must be greater than ） Don't worry ; If equal , Just put that stackMin The top element of the stack also pops out .

Query minimum ：

stackData The minimum value of is always stackMin The top element of the stack .

Code ：

package text11;

import java.util.Stack;

public class MyStack1 {
	private Stack<Integer> stackData;
	private Stack<Integer> stackMin;
	public MyStack1() {
		this.stackData=new Stack<Integer>();
		this.stackMin=new Stack<Integer>();
	}
	
	public void push(int newNum) {
		if (this.stackMin.isEmpty()) {
			this.stackMin.push(newNum);
		}else if(newNum<=this.getmin()) {
			this.stackMin.push(newNum);
		}
		this.stackData.push(newNum);
	}
	public int pop() {
		if (this.stackData.isEmpty()) {
			throw new RuntimeException("Your stack is empty.");
		}
		int value=this.stackData.pop();
		if(value==this.getmin()) {
			this.stackMin.pop();
		}
		return value;
	}
	public int getmin() {
		if(this.stackMin.empty()){
			throw new RuntimeException("Your stack is empty.");
		}
		return this.stackMin.peek();
	}
}

The second kind ：

Push in data rules ：

Put the current number num Put it in stackData When the stack , Judge stackMin Is the stack empty , If it is empty , The current number num Also put stackMin in , If it's not empty , Will judge stackMin Stack top elements and num Size , If num<=stackMin To the top of the stack Elements , Just put num Also put stackMin Inside the stack . otherwise , take stackMin Stack top element re pressing stackMin In the stack .

Pop up data rules ：

Pop up a stackData Stack element , At the same time, a stackMin Stack element

Query minimum ：

stackData The minimum value of is always stackMin The top element of the stack .

Code ：

package text11;

import java.util.Stack;

public class MyStack2 {
	private Stack<Integer> stackData;
	private Stack<Integer> stackMin;
	public MyStack2() {
		this.stackData=new Stack<Integer>();
		this.stackMin=new Stack<Integer>();
	}
	
	public void push(int newNum) {
		if (this.stackMin.isEmpty()) {
			this.stackMin.push(newNum);
		}else if(newNum<=this.getmin()) {
			this.stackMin.push(newNum);
		}else {
			int value1=getmin();
			this.stackMin.push(value1);
		}
		this.stackData.push(newNum);
	}
	public int pop() {
		if (this.stackData.isEmpty()) {
			throw new RuntimeException("Your stack is empty.");
		}
		int value=this.stackData.pop();
		
		this.stackMin.pop();
		
		return value;
	}
	public int getmin() {
		if(this.stackMin.empty()){
			throw new RuntimeException("Your stack is empty.");
		}
		return this.stackMin.peek();
	}

}