您好,登錄后才能下訂單哦!
看書時遇到這樣一道題,挺有趣的數(shù)據(jù)結(jié)構(gòu),所以記錄下來
實現(xiàn)一個棧,該棧帶有出棧(pop),入棧(push),取最小元素(getMin),三個方法。要保證這3個方法的時間復雜度都是O(1)
1.定義兩個棧,一個棧自定義棧用于入棧、出棧,一個輔助棧用于動態(tài)存放自定義棧的最小值
2.入棧操作,當元素壓入 自定義棧 的時候,會判斷輔助棧是否為空,
如果輔助棧為空,或者新元素小于等于輔助棧棧頂,則將新元素壓入(push) 輔助棧。
因為當?shù)谝粋€元素入棧時,這個唯一的元素也就是自定義棧當前最小的值,所以也壓入(push) 輔助棧
3.出棧操作,如果出棧元素和輔助棧棧頂元素值相等,輔助棧出棧(pop)。
代碼如下:
如果輔助棧為空,或者新元素小于等于輔助棧棧頂,則將新元素壓入輔助棧
/**
* 入棧操作
* @param element 入棧的元素
*/
public void push(int element){
mainStack.push(element);
//如果輔助棧為空,或者新元素小于等于輔助棧棧頂,則將新元素壓入輔助棧
if(minStack.empty()|| element <= minStack.peek()){
//empty() 表示的是測試堆棧是否為空。
//peek() 表示的是查看堆棧頂部的對象,但不從堆棧中移除它。
minStack.push(element);
}
}
如果出棧元素和輔助棧棧頂元素值相等,輔助棧出棧(pop)。
/**
* 出棧操作
*/
public Integer pop(){
//如果出棧元素和輔助棧棧頂元素值相等,輔助棧出棧
if(mainStack.peek().equals(minStack.peek())){
minStack.pop();
}
return mainStack.pop();
}
/**
* 獲取棧的最小元素
*/
public int getMin() throws Exception{
if(mainStack.empty()){
throw new Exception ("stack is empty");
}
return minStack.peek();
}
元素入棧,輸出最小值,元素出棧,再輸出最小值
public static void main(String[] args) throws Exception {
MinStack stack=new MinStack();
stack.push(4);
stack.push(9);
stack.push(7);
stack.push(3);
stack.push(8);
stack.push(5);
System.out.println(stack.getMin());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.getMin());
}
運行結(jié)果:
3
4
package min_ini;
import java.util.Stack;
public class MinStack {
private Stack<Integer> mainStack=new Stack<Integer>();
private Stack<Integer> minStack=new Stack<Integer>();
/**
* 入棧操作
* @param element 入棧的元素
*/
public void push(int element){
mainStack.push(element);
//如果輔助棧為空,或者新元素小于等于輔助棧棧頂,則將新元素壓入輔助棧
if(minStack.empty()|| element <= minStack.peek()){
//empty() 表示的是測試堆棧是否為空。
//peek() 表示的是查看堆棧頂部的對象,但不從堆棧中移除它。
minStack.push(element);
}
}
/**
* 出棧操作
*/
public Integer pop(){
//如果出棧元素和輔助棧棧頂元素值相等,輔助棧出棧
if(mainStack.peek().equals(minStack.peek())){
minStack.pop();
}
return mainStack.pop();
}
/**
* 獲取棧的最小元素
*/
public int getMin() throws Exception{
if(mainStack.empty()){
throw new Exception ("stack is empty");
}
return minStack.peek();
}
public static void main(String[] args) throws Exception {
MinStack stack=new MinStack();
stack.push(4);
stack.push(9);
stack.push(7);
stack.push(3);
stack.push(8);
stack.push(5);
System.out.println(stack.getMin());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.getMin());
}
}
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。