方法一：雙棧
思路和算法
維護(hù)兩個(gè)棧，第一個(gè)棧支持插入操作，第二個(gè)棧支持刪除操作禀横。
根據(jù)棧先進(jìn)后出的特性，我們每次往第一個(gè)棧里插入元素后粥血，第一個(gè)棧的底部元素是最后插入的元素柏锄，第一個(gè)棧的頂部元素是下一個(gè)待刪除的元素。為了維護(hù)隊(duì)列先進(jìn)先出的特性立莉，我們引入第二個(gè)棧绢彤，用第二個(gè)棧維護(hù)待刪除的元素，在執(zhí)行刪除操作的時(shí)候我們首先看下第二個(gè)棧是否為空蜓耻。如果為空茫舶，我們將第一個(gè)棧里的元素一個(gè)個(gè)彈出插入到第二個(gè)棧里，這樣第二個(gè)棧里元素的順序就是待刪除的元素的順序刹淌，要執(zhí)行刪除操作的時(shí)候我們直接彈出第二個(gè)棧的元素返回即可饶氏。
成員變量
維護(hù)兩個(gè)棧 stack1 和 stack2，其中 stack1 支持插入操作有勾，stack2 支持刪除操作
構(gòu)造方法
初始化 stack1 和 stack2 為空
插入元素
插入元素對(duì)應(yīng)方法 appendTail
stack1 直接插入元素
刪除元素
刪除元素對(duì)應(yīng)方法 deleteHead
如果 stack2 為空疹启，則將 stack1 里的所有元素彈出插入到 stack2 里
如果 stack2 仍為空，則返回 -1蔼卡，否則從 stack2 彈出一個(gè)元素并返回
class CQueue {
Deque<Integer> stack1;
Deque<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
// 如果第二個(gè)棧為空
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
if (stack2.isEmpty()) {
return -1;
} else {
int deleteItem = stack2.pop();
return deleteItem;
}
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：對(duì)于插入和刪除操作喊崖，時(shí)間復(fù)雜度均為 O(1)O(1)。插入不多說(shuō)，對(duì)于刪除操作荤懂，雖然看起來(lái)是 O(n)O(n) 的時(shí)間復(fù)雜度茁裙，但是仔細(xì)考慮下每個(gè)元素只會(huì)「至多被插入和彈出 stack2 一次」，因此均攤下來(lái)每個(gè)元素被刪除的時(shí)間復(fù)雜度仍為 O(1)O(1)节仿。
空間復(fù)雜度：O(n)O(n)晤锥。需要使用兩個(gè)棧存儲(chǔ)已有的元素。
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-3/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有廊宪。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)矾瘾，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
