方法一：雙棧
思路和算法

維護(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è)元素并返回

image.png

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)注明出處。