1.1.4 棧stack與隊列queue

棧stack

部分定義參考自百度百科棧

• 棧（stack）在計算機(jī)科學(xué)中是限定僅在表尾進(jìn)行插入或刪除操作的線性表,，是一種后進(jìn)先出（LIFO )的數(shù)據(jù)結(jié)構(gòu)。
• 棧是一種數(shù)據(jù)結(jié)構(gòu)，它按照后進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)。
• 棧是只能在某一端插入和刪除的特殊線性表。
• 棧的底層實現(xiàn)是基于數(shù)組或者鏈表
• c++ stl中stack是一個容器適配器，stack默認(rèn)的基礎(chǔ)容器為deque容器（一種雙端都可以進(jìn)行刪除插入操作的數(shù)據(jù)結(jié)構(gòu)）

下面的例子說明圖片來自維基百科：

Lifo_stack.png

queue隊列

部分定義參考自百度百科隊列

• 隊列是一種特殊的線性表，是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。
• 隊列只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。
• 隊列的底層實現(xiàn)也是基于數(shù)組或者鏈表。
• c++ stl中queue是一個容器適配器，vector、list和deque都能夠作為queue的基礎(chǔ)容器，而與stack一樣queue默認(rèn)的基礎(chǔ)容器也為deque容器

queue.png

232. Implement Queue using Stacks

使用stack模擬實現(xiàn)queue的功能，包括push、pop、peek、empty

1.舉例子-畫圖-解題思路

實現(xiàn)queue的push，意味著每次的元素都要放在stack的底部，為了完成這樣的效果，我們首先需要把stack1中的元素挨個取出放到輔助棧stack2中，然后把新來的元素直接放到stack1中，最后把stack2中的元素取出來再放到stack1中。

push示意圖：

stack-queue.png

pop示意圖：

queue的pop即stack1的top+pop操作（c++的stack，top只返回最頂元素，不會出棧，pop才會執(zhí)行出棧操作）

2. 寫核心邏輯代碼

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stack<int> stack2;
        // 將stack1中的元素移動到stack2中
        while(!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
        //將新push的元素放入stack1中
        stack1.push(x);
        //將stack2中的元素放回stack1中
        while(!stack2.empty())
        {
            stack1.push(stack2.top());
            stack2.pop();
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        //top方法只返回棧的頂值，不會出棧
        int value = stack1.top();
        //出棧操作是pop，但沒有返回值
        stack1.pop();
        return value;
    }
    
    /** Get the front element. */
    int peek() {
        return stack1.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stack1.empty();
    }
private:
    stack<int> stack1;
};

3. 邊界條件-無

4. 優(yōu)化

每次push元素都要把元素經(jīng)歷stack1-stack2-stack1這樣的流程是有些浪費(fèi)的?？梢钥紤]一種lazy的方式，同樣準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)與算法兩個stack，pushi時候新元素直接放到stack1，pop或者peek時候，先看stack2中是否有元素，有直接出棧，沒有則把stack1中的元素移動到stack2中。

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stack1.push(x);
    }
    
    void shiftStack()
    {
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        shiftStack();
        if(!stack2.empty())
        {
            int value = stack2.top();
            stack2.pop();
            return value;
        }
        return 0;
    }
    
    /** Get the front element. */
    int peek() {
        shiftStack();
        if(!stack2.empty())
        {
            return stack2.top();
        }
        return 0;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stack1.empty() && stack2.empty();
    }

private:
    stack<int> stack1,stack2;
};

5. 小結(jié)

stack 經(jīng)常作為一種輔助手段實現(xiàn)更為復(fù)雜的一些算法（圖的深度優(yōu)先遍歷），我們后面也會看到。常用的語言c++/java中都內(nèi)置了stack的數(shù)據(jù)類型，請小伙伴們嘗試?yán)斫夂褪褂胹tack。框架圖將在225題目的小結(jié)中一并給出。

225. Implement Stack using Queues

使用隊列queue模擬實現(xiàn)stack的push、pop、top、empty函數(shù)

1.舉例子-畫圖-解題思路

先考慮利用queue實現(xiàn)stack的push函數(shù)。我們要想辦法每次把push的數(shù)據(jù)放到q1（queue）的頭部，這時需要借助另外一個q2（queue），push到q1前先把q1中的數(shù)據(jù)依次取出放到q2中，然后將新數(shù)據(jù)push到q1中，最后把q2中數(shù)據(jù)依次取出再放回q1中。

217-op (7).png

2. 寫核心邏輯代碼

class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        queue<int> q2;
        //step1 step2 將queue1中元素放到queue2中
        while(!q1.empty())
        {
            q2.push(q1.front());
            q1.pop();
        }
        // step2 將新元素放到queue1中
        q1.push(x);
         //step3 setp4 再將queue2中元素放回queue1中
        while(!q2.empty())
        {
            q1.push(q2.front());
            q2.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int value = q1.front();
        q1.pop();
        return value;
    }
    
    /** Get the top element. */
    int top() {
        return q1.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
private:
    queue<int> q1;

};

3. 邊界條件

題目已經(jīng)幫我們限制了各種邊界條件，不用在代碼中說明

4. 優(yōu)化

還有一種解法是只用一個queue來完成stack的push函數(shù)。具體思路是：將新元素push到queue1中，然后將新元素之前的各個元素依次取出來放到新元素后面，這樣新元素最后就位于queue1的頭部了。

//我們只重寫這個push函數(shù)，其他函數(shù)的實現(xiàn)與未優(yōu)化前的版本一致
/** Push element x onto stack. */
void push(int x) {
    int length = q1.size();
    q1.push(x);
    while(length--)
    {
        q1.push(q1.front());
        q1.pop();
    }
}

5. 小結(jié)

queue也經(jīng)常作為一種輔助手段實現(xiàn)更為復(fù)雜的一些算法（圖的廣度優(yōu)先遍歷），我們后面也會遇到相應(yīng)的例子。常用的語言c++/java中也都內(nèi)置了queue的數(shù)據(jù)類型。

怎樣應(yīng)對IT面試與筆試-（一）
怎樣應(yīng)對IT面試與筆試-（二）
怎樣應(yīng)對IT面試與筆試-（三）
怎樣應(yīng)對IT面試與筆試-（四）
怎樣應(yīng)對IT面試與筆試-（五）
怎樣應(yīng)對IT面試與筆試-（五-1）
怎樣應(yīng)對IT面試與筆試-（六）
怎樣應(yīng)對IT面試與筆試-（七）
怎樣應(yīng)對IT面試與筆試-（八）
怎樣應(yīng)對IT面試與筆試-（九）
怎樣應(yīng)對IT面試與筆試-（十）
怎樣應(yīng)對IT面試與筆試-（十一）
怎樣應(yīng)對IT面試與筆試-（十二）
怎樣應(yīng)對IT面試與筆試-（十三）
怎樣應(yīng)對IT面試與筆試-（十四）
怎樣應(yīng)對IT面試與筆試-（十五）
怎樣應(yīng)對IT面試與筆試-（十六）