title: 每日一練（4）：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

categories:[劍指offer]

tags:[每日一練]

date: 2022/01/17

每日一練（4）：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒(méi)有元素，deleteHead 操作返回 -1 )

示例 1：

輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]
示例 2：

輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多會(huì)對(duì) appendTail、deleteHead 進(jìn)行 10000 次調(diào)用

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

方法：棧一入，棧二出

算法流程：

• 棧 ： 先入后出，后入先出
• 隊(duì)列 ： 先入先出，后入后出

棧s1負(fù)責(zé)appendTail，棧s2負(fù)責(zé)deleteHead

插入元素對(duì)應(yīng)方法 appendTail

• stack1 直接插入元素

刪除元素對(duì)應(yīng)方法 deleteHead

• 如果 stack2 為空，則將 stack1 里的所有元素彈出插入到 stack2 里
• 如果 stack2 仍為空，則返回 -1，否則從 stack2 彈出一個(gè)元素并返回

復(fù)雜度分析

• 時(shí)間復(fù)雜度：對(duì)于插入和刪除操作，時(shí)間復(fù)雜度均為 O(1)。插入不多說(shuō)，對(duì)于刪除操作，雖然看起來(lái)是 O(n)的時(shí)間復(fù)雜度，但是仔細(xì)考慮下每個(gè)元素只會(huì)「至多被插入和彈出 stack2 一次」，因此均攤下來(lái)每個(gè)元素被刪除的時(shí)間復(fù)雜度仍為 O(1)。

• 空間復(fù)雜度：O(n)。需要使用兩個(gè)棧存儲(chǔ)已有的元素。

class CQueue {
    stack<int> stack1 , stack2;
public:
    CQueue() {
        while (!stack1.empty()) {
            stack1.opo();
        }
        while (!stack2.empty()) {
            stack2.pop();
        }
    }
    void appendTail(int value) {
        stack1.push(value);
    }
    
    int deleteHead() {
        //如果第二個(gè)棧為空
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if (stack2.empty()) {
            return -1;
        } else {
            int deleteItem = stack2.top();
            stack2.pop();
            return deleteItem;
        }
    }
}
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */