用兩個棧實現(xiàn)一個隊列。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead ，分別完成在隊列尾部插入整數(shù)和在隊列頭部刪除整數(shù)的功能。(若隊列中沒有元素，deleteHead?操作返回 -1 )
示例 1：
輸入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
輸出：[null,null,3,-1,-1]
示例 2：
輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]
重慶分公司
重慶分公司
class CQueue {
public CQueue() {
}
public void appendTail(int value) {
}
public int deleteHead() {
}
}棧實現(xiàn)隊列的出隊操作效率低下：棧底元素（對應(yīng)隊首元素）無法直接刪除，需要將上方所有元素出棧。
列表倒序操作可使用雙棧實現(xiàn)：設(shè)有含三個元素的棧 A = [1,2,3] 和空棧 B = [] 。若循環(huán)執(zhí)行 A 元素出棧并添加入棧 B ，直到棧 A 為空，則 A = [] , B = [3,2,1] ，即棧 B 元素為棧 A 元素倒序。
利用棧 B 刪除隊首元素：倒序后，B 執(zhí)行出棧則相當(dāng)于刪除了 A 的棧底元素，即對應(yīng)隊首元素。
函數(shù)設(shè)計：
加入隊尾 appendTail() ： 將數(shù)字 val 加入棧 A 即可。
刪除隊首deleteHead() ： 有以下三種情況。
當(dāng)棧 B 不為空： B中仍有已完成倒序的元素，因此直接返回 B 的棧頂元素。
否則，當(dāng) A 為空： 即兩個棧都為空，無元素，因此返回 -1 。
否則： 將棧 A 元素全部轉(zhuǎn)移至棧 B 中，實現(xiàn)元素倒序，并返回棧 B 的棧頂元素。
代碼如下：
class CQueue {
LinkedListA, B;
public CQueue() {
A = new LinkedList();
B = new LinkedList();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) return B.removeLast();
if(A.isEmpty()) return -1;
while(!A.isEmpty())
B.addLast(A.removeLast());
return B.removeLast();
}
} 定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時間復(fù)雜度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); ? -->返回 -3.
minStack.pop();
minStack.top(); ? ? ?-->返回 0.
minStack.min(); ? -->返回 -2.
class MinStack {
public MinStack() {
}
public void push(int x) {
}
public void pop() {
}
public int top() {
}
public int min() {
}
}普通棧的 push() 和 pop() 函數(shù)的復(fù)雜度為 O(1)O(1) ；而獲取棧最小值 min() 函數(shù)需要遍歷整個棧，復(fù)雜度為 O(N)O(N) 。
本題難點： 將 min() 函數(shù)復(fù)雜度降為 O(1)O(1) ?？山柚o助棧實現(xiàn)：
數(shù)據(jù)棧 A ： 棧 A 用于存儲所有元素，保證入棧 push() 函數(shù)、出棧 pop() 函數(shù)、獲取棧頂 top() 函數(shù)的正常邏輯。
輔助棧 B ： 棧 B 中存儲棧 A 中所有 非嚴(yán)格降序 元素的子序列，則棧 A 中的最小元素始終對應(yīng)棧 B 的棧頂元素。此時， min() 函數(shù)只需返回棧 B 的棧頂元素即可。
函數(shù)設(shè)計：
push(x) 函數(shù)： 重點為保持棧 B 的元素是 非嚴(yán)格降序 的；
執(zhí)行「元素 x 壓入棧 A」 ；
若「棧 B 為空」或「x ≤ 棧 B 的棧頂元素」，則執(zhí)行「元素 x 壓入棧 B」 ；
pop() 函數(shù)： 重點為保持棧 A , B 的 元素一致性 ；
執(zhí)行「棧 A 元素出?！?，將出棧元素記為 y ；
若 「y 等于棧 B 的棧頂元素」，則執(zhí)行「棧 B 元素出?！?；
top() 函數(shù)： 直接返回棧 A 的棧頂元素，即返回 A.peek() ；
min() 函數(shù)： 直接返回棧 B 的棧頂元素，即返回 B.peek() ；
采用 “非嚴(yán)格” 降序原因：
在棧?A具有?重復(fù)?最小值元素時，非嚴(yán)格降序可防止棧?B提前彈出最小值元素，示例如下：
代碼如下：
注：Java 代碼中，由于 Stack 中存儲的是 int 的包裝類 Integer ，因此需要使用?equals()代替?==，以比較對象的值。?
class MinStack {
StackA, B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int x) {
A.add(x);
if(B.empty() || B.peek() >= x)
B.add(x);
}
public void pop() {
if(A.pop().equals(B.peek()))
B.pop();
}
public int top() {
return A.peek();
}
public int min() {
return B.peek();
}
} 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
