~~~
package stackAndQueue;
import java.util.Stack;
import org.junit.Test;
/**
*
* 設計一個有getMin功能的棧：StackGetMin【1】.
*
* 【實現一個特殊的棧，在實現棧的基本功能的基礎上，再實現返回棧中最小元素的操作】
*
* 要求：1、pop、push、getMin操作的時間復雜度都是O(1);2、設計的棧類型可以使用現成的棧結構。
*
* 設計思路：兩個棧-普通棧+getMin棧
*
* @author xiaofan.
*/
public class StackGetMin {
private Stack<Integer> stackData;
private Stack<Integer> stackGetMin;
/**
* 構造函數.
*/
public StackGetMin() {
this.stackData = new Stack<Integer>();
this.stackGetMin = new Stack<Integer>();
}
public void push(int item) { // 壓入稍省空間
this.stackData.push(item);
if (this.stackGetMin.isEmpty()) {
this.stackGetMin.push(item);
} else if (item <= this.getMin()) { // 小于等于:避免插入多個最小值再彈出后，棧中無最小值
this.stackGetMin.push(item);
}
}
public int pop() { // 彈出稍費時間
if (this.stackData.isEmpty()) { // 判空
throw new RuntimeException("Your Stack is empty.");
}
int value = this.stackData.pop();
if (value == this.getMin()) { // 兩個棧同步彈出
this.stackGetMin.pop();
}
return value;
}
public int getMin() {
if (this.stackGetMin.isEmpty()) {
throw new RuntimeException("Your Stack is empty.");
}
return this.stackGetMin.peek();
}
//////////// 測試類/////////////////
@Test
public void test() {
StackGetMin myStack = new StackGetMin();
myStack.push(2);
myStack.push(5);
myStack.push(4);
myStack.push(1);
myStack.push(1);
System.out.println(myStack.pop());
System.out.println(myStack.getMin());
StackGetMin myStack1 = new StackGetMin();
myStack1.pop(); // RuntimeException("Your Stack is empty.")
}
///////// 方案2//////
// 如果StackGetMin棧頂元素比比newNum小，則將棧頂元素重復壓入
// 壓入稍費空間，彈出稍省時間
}
~~~
代碼地址：[https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue](https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue)
