一、stack的介紹和使用

1.1 stack的介紹

• stack 是一種容器適配器，專門用在具有后進(jìn)先出的上下文環(huán)境中。只能從容器的一端進(jìn)行元素的插入與提取操作。
• stack 是作為容器適配器被實現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，使得元素在特定容器的尾部（棧頂）被壓入和彈出。
• stack 的底層容器可以使任何標(biāo)準(zhǔn)的容器類模板或者一些其它特定的容器類，這些容器類應(yīng)該支持以下操作：
  • empty：判空操作
  • back：獲取尾部元素操作
  • push_back：尾部插入元素操作
  • pop_back：尾部刪除元素操作
• 標(biāo)準(zhǔn)容器 vector、deque、list 均符合這些需求，默認(rèn)情況下，如果沒有為 stack 指定特定的底層容器，默認(rèn)情況下使用 deque。

1.2 stack的使用

1.2.1 最小棧

本題的思路是用兩個棧來實現(xiàn)，其中一個棧 _st 用來正常存儲數(shù)據(jù)，另一個棧 _minst 用來存儲最小的數(shù)據(jù)。具體實現(xiàn)就是在往 _st 中插入數(shù)據(jù)的時候進(jìn)行判斷，如果當(dāng)前插入的數(shù)據(jù) val 小于等于 _minst 棧頂?shù)臄?shù)據(jù)，那就將 val 也插入到 _minst 這個棧中。否則直將數(shù)據(jù)插入 _st 中。在 pop 數(shù)據(jù)的時候，先取 _st 的棧頂元素和 _minst 的棧頂元素進(jìn)行比較，如果二者相等，那就同時 pop _st 和 _minst 的棧頂元素，否則就值 pop _st 的棧頂元素。要獲取堆棧中的最小元素直接返回 _minst 的棧頂元素即可。

class MinStack 
{
public:
    MinStack() {}
    void push(int val) 
    {
        _st.push(val);
        if(_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }
    void pop() 
    {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    int top() 
    {
        return _st.top();
    }
    int getMin() 
    {
        return _minst.top();
    }
private:
    stack<int> _st;
    stack<int> _minst;
};

1.2.2 棧的壓入、彈出序列

本題的解題思路是用一個棧來模擬。即先定義一個棧 st 然后給棧中入一個數(shù)據(jù)，接著取棧頂?shù)臄?shù)據(jù)和出棧序列 popV 當(dāng)前位置元素進(jìn)行比較進(jìn)行比較，如果不相等則繼續(xù)從入棧序列 pushV 中拿數(shù)據(jù)往棧 st 中入，如果相等就出棧。這里需要注意，有可能需要連續(xù)多次出棧。直到最終將入棧序列 pushV 中的數(shù)據(jù)全入棧，最后判斷棧 st 是否為空，如果為空，就說明該出棧序列正確。如果不空就說明該出棧序列有問題。

class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布爾型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        // write code here
        stack<int> st;
        size_t push_pos = 0, pop_pos = 0;
        while(push_pos < pushV.size())
        {
            //先入一個元素
            st.push(pushV[push_pos++]);
            if(st.top() != popV[pop_pos])
            {
                //不匹配繼續(xù)入數(shù)據(jù)
                continue;
            }
            while(!st.empty() && st.top() == popV[pop_pos])
            {
                //匹配，出數(shù)據(jù)
                st.pop();
                pop_pos++;
            }
        }
        return st.empty();
    }
};

代碼優(yōu)化：我們可以發(fā)現(xiàn)上面代碼中不匹配邏輯里面其實啥也沒干，因此我們可以把這段代碼給刪掉，上面加上是為了使邏輯更加清晰。

class Solution {
public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布爾型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        // write code here
        stack<int> st;
        size_t push_pos = 0, pop_pos = 0;
        while(push_pos < pushV.size())
        {
            //先入一個元素
            st.push(pushV[push_pos++]);
            while(!st.empty() && st.top() == popV[pop_pos])
            {
                //匹配，出數(shù)據(jù)
                st.pop();
                pop_pos++;
            }
        }
        return st.empty();
    }
};

1.2.3 逆波蘭表達(dá)式求值

逆波蘭表達(dá)式也被叫做后綴表達(dá)式。什么是后綴表達(dá)式呢？先來了解一下中綴表達(dá)式，中綴表達(dá)式就是我們平時最常見的，例如： 2 + 3 ∗ 1 2+3*1 2+3∗1，就是一個典型的中綴表達(dá)式。將前面的中綴表達(dá)式變成后綴表達(dá)式得到： 2 1 3 * + ，這就是一個后綴表達(dá)式，后綴表達(dá)式相較于中中綴表達(dá)式，操作數(shù)順序不變，操作符按優(yōu)先級重排。這道題目就是要求我們對后綴表達(dá)式進(jìn)行求解。求解后綴表達(dá)式，我們可以借助一個棧，遇到操作數(shù)入棧，遇到操作符從棧中出兩個元素進(jìn)行運算，將運算結(jié)果繼續(xù)入棧。最終棧頂?shù)脑鼐褪钦麄€逆波蘭表達(dá)式的結(jié)果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        size_t pos = 0;
        while(pos < tokens.size())
        {
            if(tokens[pos] != "+" && tokens[pos] != "-" && tokens[pos] != "*" && tokens[pos] != "/")
            {
                //如果是數(shù)字就入棧
                int num = stoi(tokens[pos]);
                st.push(num);
            }
            else
            {
                //不是數(shù)字就從棧中取兩個元素出來
                int val1 = st.top();
                st.pop();
                int val2 = st.top();
                st.pop();
                int ret = 0;
                if(tokens[pos] == "+")
                {
                    ret = val2 + val1;
                }
                else if(tokens[pos] == "-")
                {
                    ret = val2 - val1;
                }
                else if(tokens[pos] == "*")
                {
                    ret = val2 * val1;
                }
                else if(tokens[pos] == "/")
                {
                    ret = val2 / val1;
                }
                //將計算結(jié)果繼續(xù)入棧
                st.push(ret);
            }
            pos++;
        }
        return st.top();
    }
};

注意：在寫上面這段代碼的時候有下面幾點需要特別注意，首先這是一個 string 數(shù)組，會涉及到 string 轉(zhuǎn) int 。其次需要注意在從棧中取數(shù)的時候，第一次取出的是右操作數(shù)，第二次取出的是左操作數(shù)，因此 val2 應(yīng)該做左操作數(shù)， val1 應(yīng)該做右操作數(shù)，尤其是減法運算和除法運算，這兩個操作數(shù)的順序必須得到保證。

補(bǔ)充：這里補(bǔ)充一個小知識點：如何將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。主要過程分為以下幾步：

• 遇到操作數(shù)就輸出（這里的輸出是將其存儲到某種容器里）。
• 遇到操作符，根據(jù)優(yōu)先級的順序分為以下兩種情況：
  • 棧為空或當(dāng)前操作符比棧頂?shù)膬?yōu)先級高，繼續(xù)入棧。
  • 棧不為空且當(dāng)前操作符比棧頂?shù)膬?yōu)先級低或者相等，則輸出棧頂操作符，繼續(xù)執(zhí)行第二步。
• 中綴表達(dá)式結(jié)束后，依次出棧里面的操作符。

小Tips：當(dāng)前操作符能否計算取決于后一個操作符的優(yōu)先級是否高于自己，所以每當(dāng)我們遇到一個操作符的時候，先不著急將它入棧，先和棧頂?shù)牟僮鞣M(jìn)行優(yōu)先級比較，如果當(dāng)前操作符的優(yōu)先級比棧頂操作符的優(yōu)先級低或者相等，我們就可以取出棧頂這個操作符進(jìn)行運算。如果遇到括號可以走一個遞歸。其次就是需要想辦法確定符號的優(yōu)先級。

1.2.4 用棧實現(xiàn)隊列

將一個棧當(dāng)做輸入棧，用于壓入 push 傳入的數(shù)據(jù)，另一個棧當(dāng)做輸出棧，用于 pop 和 peek 操作。每次 pop 或 peek 時，若輸出棧為空則將輸入棧的全部數(shù)據(jù)依次彈并壓入輸出棧，這樣輸出棧從棧頂往棧底的順序就是隊列從隊首往隊尾的順序。

class MyQueue {
public:
    MyQueue() 
    {}
    void push(int x) 
    {
        input_st.push(x);
    }
    int pop() 
    {
        if(output_st.empty())
        {
            while(!input_st.empty())
            {
                output_st.push(input_st.top());
                input_st.pop();
            } 
        }
        int ret = output_st.top();
        output_st.pop();
        return ret;
    }
    int peek() 
    {
        if(output_st.empty())
        {
            while(!input_st.empty())
            {
                output_st.push(input_st.top());
                input_st.pop();
            }
        }
        return output_st.top();
    }
    bool empty() 
    {
        return input_st.empty() && output_st.empty();
    }
private:
    stack<int> input_st;
    stack<int> output_st;
};

二、queue的介紹和使用

2.1 queue的介紹

• 隊列是一種容器適配器，專門用于在FIFO上下文中執(zhí)行先進(jìn)先出操作，其中從容器的一端插入元素，另一端提取元素。
• 隊列作為容器適配器實現(xiàn)，容器適配器即將特定的容器類封裝最為其底層容器，queue 提供一組特定的成員函數(shù)來訪問其元素。元素從隊尾入隊列，從對頭出隊列。
• 底層容器可以是標(biāo)準(zhǔn)容器模板之一，也可以是其他專門設(shè)計的容器類。該底層容器應(yīng)至少支持以下操作：
  • empty：檢查隊列是否為空
  • size：返回隊列中有效元素的個數(shù)
  • front：返回對頭元素的引用
  • back：返回隊尾元素的引用
  • push_back：在隊列尾部入隊列
  • pop_front：在隊列頭部出隊列
• 標(biāo)準(zhǔn)容器類 deque 和 list 滿足了這些要求。默認(rèn)情況下，如果沒有為 queue 實例化指定容器類，則使用標(biāo)準(zhǔn)容器 deque。

2.2 queue的使用

2.2.1 二叉樹的層序遍歷

二叉樹的層序遍歷可以借助隊列來實現(xiàn)，從根節(jié)點開始，先讓父節(jié)點入隊列，在出隊尾節(jié)點的同時，將該節(jié)點的左孩子和右孩子依次入隊列。直到隊列為空，從隊列中出出來的結(jié)果就是層序遍歷的結(jié)果。這道題目需要將同一層的所有節(jié)點都存入一個一維數(shù)組，再將這些一維數(shù)組組合成一個二維數(shù)組返回。我們前面的這種做法會導(dǎo)致隊列中出現(xiàn)兩層節(jié)點混在意的情況，因此我們可以定義一個變量 levelSize 來記錄每一層的節(jié)點數(shù)。具體代碼如下：

class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> retV;
        queue<TreeNode*> qu;
        int levelSize = 0;
        qu.push(root);
        while(!qu.empty())
        {
            vector<int> tmp;
            levelSize = qu.size();
            while(levelSize != 0)
            {
                TreeNode* top = qu.front();
                if(top != nullptr)
                {
                    tmp.push_back(top->val);
                    qu.push(top->left);
                    qu.push(top->right);
                } 
                qu.pop();
                levelSize--;
            }
            if(!tmp.empty())
            {
                retV.push_back(tmp);
            }
        }
        return retV;
    }
};

三、模擬實現(xiàn)

3.1 stack模擬實現(xiàn)

template<class T, class Continer = vector<T>>
	class stack
	{
	public:
		stack()
		{}
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_back();
		}
		T& top()
		{
			return _con.back();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Continer _con;
	};

小Tips：stack 可以使用 vector 或者 list 來實現(xiàn)，效率相當(dāng)。插入數(shù)據(jù)就相當(dāng)于尾插，刪除棧頂元素就相當(dāng)于尾刪。

3.2 queue模擬實現(xiàn)

template<class T, class Continer = std::list<T>>
class queue
{
public:
	queue()
	{}
	void push(const T& val)
	{
		_con.push_back(val);
	}
	void pop()
	{
		_con.pop_front();//這里不再支持vector
	}
	T& front()
	{
		return _con.front();
	}
	T& back()
	{
		return _con.back();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Continer _con;
};

小Tips：棧不能借助 vector 來實現(xiàn)，因為出隊列，相當(dāng)于刪除 vector 中的第一個元素，而對 vector 頭刪會涉及挪動數(shù)據(jù)，效率相較于 list 會有所下降。

四、容器適配器

4.1 什么是適配器？

適配器是一種設(shè)計模式（設(shè)計模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計經(jīng)驗的總結(jié)），該種模式是將一個類的接口轉(zhuǎn)換成客戶希望的另外一個接口。

4.2 STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)

雖然 stack 和 queue 中也可以存放元素，但在 STL 中并沒有將其劃分在容器行列，而是將其稱為容器適配器，這是因為 stack 和 queue 只是對其他容器的接口進(jìn)行了包裝，STL 中 stack 和 queue 默認(rèn)使用 deque。

4.3 deque的簡單介紹

4.3.1 deque的原理介紹

deque（雙端隊列）：是一種雙開口的“連續(xù)”空間的數(shù)據(jù)結(jié)構(gòu)，雙開口的含義是：可以在頭尾兩端進(jìn)行插入和刪除操作，且時間復(fù)雜度為O(1)，與 vector 比較，頭插效率高，不需要搬移元素；與 list 比較，空間利用率比較高。

deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實際 deque 類似于一個動態(tài)的二維數(shù)組，其底層結(jié)構(gòu)如下圖所示：

雙端隊列底層是一段假象的連續(xù)空間，實際是分段連續(xù)的，為了維護(hù)其“整體連續(xù)”以及隨機(jī)訪問的假象，落在了 deque 的迭代器身上，因此 deque 的迭代器設(shè)計的就比較復(fù)雜，如下圖所示：

4.3.2 deque的缺陷

• 與 vector 比較，deque 的優(yōu)勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴(kuò)容時，也不需要搬移大量的元素，因此其效率是比 vector 高的。
• 與 list 比較，其底層空間是連續(xù)的，空間利用率比較高，不需要存儲額外字段。
• 但是，deque 有一個致命缺陷：不適合遍歷，因為在遍歷時，deque 的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導(dǎo)致效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實際中，需要線性結(jié)構(gòu)式，大多數(shù)情況下優(yōu)先考慮 vector 和 list，deque 的應(yīng)用并不多，而目前能看到的一個應(yīng)用場景就是，STL 用其作為 stack 和 queue 的底層數(shù)據(jù)結(jié)構(gòu)。

4.4 為什么選擇deque作為stack和queue的底層默認(rèn)容器？

stack 是一種后進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要是具有 push_back() 和 pop_back() 操作的線性結(jié)構(gòu)，都可以作為 stack 的底層容器，比如 vector 和 list 都可以；queue 是先進(jìn)先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有 push_back() 和 pop_front() 操作的線性結(jié)構(gòu)，都可以作為 queue de 底層容器，比如 list。但是 STL 中對 stack 和 queue 默認(rèn)選擇 deque 作為其底層容器，主要是因為：

• stack 和 queue 不需要遍歷（因此 stack 和 queue 沒有迭代器），只需要在固定的一端或者兩端進(jìn)行操作。
• 在 stack 中元素增長時，deque 比 vector 的效率高（擴(kuò)容時不需要搬移大量數(shù)據(jù)）；queue 中的元素增長時，deque 不僅效率高，而且內(nèi)存利用率高。

五、結(jié)語

今天的分享到這里就結(jié)束啦！如果覺得文章還不錯的話，可以三連支持一下！

以上就是深入探索C++中stack和queue的底層實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++ stack和queue底層實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！