1.1、題目1
劍指 Offer 09. 用兩個堆疊實作佇列
1.2、解法
解法如題目所說，定義兩個堆疊，這里假設第一個堆疊為a，第二個堆疊為b，
實作兩個函式增加尾和洗掉頭，
增加即直接push入第一個堆疊，
洗掉函式：通過判斷a是否為空進行回圈，將已經存入的a的堆疊頂pop存到b中，以此達到倒置的效果，
再將b的堆疊頂pop出來即可達到洗掉，
此時a堆疊為空，下次判斷若b堆疊為空，則輸出-1，
否則則繼續通過b堆疊輸出堆疊頂，
1.3、代碼
class CQueue {
Deque<Integer> a;
Deque<Integer> b;
public CQueue() {
a = new LinkedList<Integer>();
b = new LinkedList<Integer>();
}
public void appendTail(int value) {
a.push(value);
}
public int deleteHead() {
if(b.isEmpty()){
while(!a.isEmpty()){
b.push(a.pop());
}
}
if(b.isEmpty()){
return -1;
}else{
return (int)b.pop();
}
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
2.1、題目2
劍指 Offer 30. 包含min函式的堆疊
2.2、解法
仍是通過兩個堆疊的方式，第一個堆疊為d1，第二個堆疊為d2
d1的push、pop、top不受影響，
至于d2，push時需將d2堆疊頂元素與目前元素判斷，若大于或者等于，則存進d2
pop時，若d2堆疊頂元素與d1 pop的元素相同，則共同pop
此時d2的堆疊頂為最小值，
2.3、代碼
class MinStack {
Deque<Integer> d1,d2;
/** initialize your data structure here. */
public MinStack() {
d1 = new LinkedList<Integer>();
d2 = new LinkedList<Integer>();
}
public void push(int x) {
d1.push(x);
if(d2.isEmpty()||d2.peek()>=x){
d2.push(x);
}
}
public void pop() {
if(d1.pop().equals(d2.peek())){
d2.pop();
}
}
public int top() {
return (int)d1.peek();
}
public int min() {
return (int)d2.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/296716.html
標籤：Java
上一篇：并發編程之：Atomic
下一篇：gateway 報錯 allowedOrigins cannot contain the special value "*"