前言

今天咱們學(xué)習(xí)stack和queue，咱們還是依照官網(wǎng)來(lái)學(xué)習(xí)：

stack - C++ Reference (cplusplus.com)

queue - C++ Reference (cplusplus.com)

主體

        在數(shù)據(jù)結(jié)構(gòu)初階中，我們模擬實(shí)現(xiàn)了stack和queue，只能說(shuō)我們知道棧和隊(duì)列，但是棧和隊(duì)列的底層是如何實(shí)現(xiàn)的我們就不得而知了，面對(duì)這個(gè)現(xiàn)象我們從新學(xué)習(xí)棧和隊(duì)列，深度解剖。學(xué)習(xí)這個(gè)版塊，咱們按照下面的圖解進(jìn)行學(xué)習(xí)：

stack的介紹和使用

stack的介紹

stack - C++ Reference (cplusplus.com)

stack是一種容器適配器，其本質(zhì)是數(shù)據(jù)結(jié)構(gòu)中的棧。它是一種只能在一端進(jìn)行插入和刪除操作的線性表。stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類(lèi)封裝作為其底層的容器，并提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素，將特定類(lèi)作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒(méi)有為stack指定特定的底層容器，默認(rèn)情況下使用deque。棧和隊(duì)列都叫做適配器/配接器，不是直接實(shí)現(xiàn)的，而是封裝其他容器，包裝轉(zhuǎn)換實(shí)現(xiàn)出來(lái)的stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類(lèi)模板或者一些其他特定的容器類(lèi)，這些容器類(lèi)應(yīng)該支持以下： empty：判空操作。back：獲取尾部元素的操作，這是因?yàn)闂５膖op操作相當(dāng)于拿取尾部元素。push_back：尾部插入元素操作。pop_back：尾部刪除元素操作。

 stack的使用

代碼訓(xùn)練：

#include<iostream>
#include<stack>
#include<queue>
 
using namespace std;
 
void test_stack()
{
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
    
    cout << st.empty() << endl; // 檢測(cè)stack是否為空
    cout << st.size() << endl;  // 返回stack中元素的個(gè)數(shù)
    
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
}
int main()
{
    test_stack();
    return 0;
}

代碼訓(xùn)練：tack的案例，首先先創(chuàng)建一個(gè)stack容器，<int>這里表示我這個(gè)容器存放的是int類(lèi)型的數(shù)據(jù)。然后通過(guò)push()將數(shù)據(jù)壓入棧中，stack并不支持迭代器訪問(wèn)，我們通過(guò)接口empty()判斷棧是否為空，通過(guò)top()訪問(wèn)棧頂元素，pop()將數(shù)據(jù)出棧。

stack的應(yīng)用

1.最小棧

問(wèn)題分析：設(shè)計(jì)兩個(gè)棧，一個(gè)負(fù)責(zé)保存棧的元素，一個(gè)負(fù)責(zé)保存棧的最小值。只要有元素比最小值棧的頂部元素還有小，那么，就將這個(gè)值壓入最小值棧中，這樣就能保證，最小值棧的頂部元素永遠(yuǎn)是當(dāng)前壓入的所有元素中最小的。

代碼：

class MinStack {
public:
    MinStack() 
    {
 
    }
    
    void push(int val) 
    {
        st.push(val);
        if(minst.empty() || val <= minst.top())
        {
            minst.push(val);
        }
    }
    
    void pop() 
    {
        if(minst.top() == st.top())
        {
            minst.pop();
        }
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return minst.top();
    }
private:
    stack<int> st;
    stack<int> minst; // 輔助棧
};

2.棧的壓入、彈出序列

問(wèn)題分析：借助一個(gè)輔助棧，首先，創(chuàng)建兩個(gè)變量i和j，分別指向pushV數(shù)組的元素和popV數(shù)組的元素，然后將pushV的數(shù)據(jù)壓入棧中，直到遇到頂部元素恰好等于出棧序列的元素，那么就將棧頂元素出棧，并且j++。最后，如果棧的元素不為空，那么說(shuō)明當(dāng)前出棧序列不符合。

代碼：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) 
    {
        stack<int> st;
        int i = 0, j = 0; // i 指向push數(shù)組的元素 ， j 指向pop數(shù)組元素
        for(; i < pushV.size();i++)
        {
            st.push(pushV[i]);
            while(!st.empty() && st.top() == popV[j])
            {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};

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

問(wèn)題分析：同樣借助一個(gè)輔助棧來(lái)完成，遍歷數(shù)組tokens，遇到數(shù)值就壓入棧中，遇到符號(hào)，就彈出兩個(gè)元素，并且根據(jù)符號(hào)進(jìn)行求值。最后，棧頂元素就是最終的表達(dá)式結(jié)果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        for(int i = 0;i<tokens.size();++i)
        {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if(tokens[i] == "+") st.push(num2 + num1);
                else if(tokens[i] == "-") st.push(num2 - num1);
                else if(tokens[i] == "*") st.push(num2 * num1);
                else if(tokens[i] == "/") st.push(num2 / num1);
            }
            else 
            {
                st.push(stoi(tokens[i])); // stoi 把字符串轉(zhuǎn)為數(shù)字
            }
        }
        int result = st.top();
        st.pop();
        return result;
    }
};

4.用棧實(shí)現(xiàn)隊(duì)列

問(wèn)題分析：設(shè)計(jì)兩個(gè)棧，一個(gè)棧用來(lái)入數(shù)據(jù)，一個(gè)棧用來(lái)出數(shù)據(jù)。入隊(duì)列操作，可以直接將數(shù)據(jù)插入到stIn中，出隊(duì)列的時(shí)候，如果stOut為空，就將stIn的數(shù)據(jù)放到stOut中，我們直到棧的特性是后進(jìn)先出，隊(duì)列的特性是先進(jìn)先出，那么將元素放到一個(gè)棧中，再出棧到另一個(gè)棧中，相當(dāng)于元素原本的順序不變，恰好符合隊(duì)列的要求。

代碼：

class MyQueue {
public:
    stack<int> stIn;  // 用來(lái)入數(shù)據(jù)
    stack<int> stOut; // 用來(lái)出數(shù)據(jù)
    MyQueue() 
    {
 
    }
    
    void push(int x) 
    {
        stIn.push(x);
    }
    
    int pop() 
    {
        if(stOut.empty())
        {
            while(!stIn.empty())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    // 獲取頭部元素
    int peek() 
    {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() 
    {
        return stIn.empty() && stOut.empty();
    }
};

queue的介紹和使用

queue的介紹

queue - C++ Reference (cplusplus.com)

queue是一種容器適配器，專門(mén)用于在先進(jìn)先出上下文中操作，在容器的一端插入元素，另一端刪除元素。

queue的底層也是用作容器來(lái)進(jìn)行封裝，底層容器必須支持以下操作：

empty：檢測(cè)隊(duì)列是否為空。size：返回隊(duì)列的有效元素個(gè)數(shù)front：返回隊(duì)頭元素的引用back：返回隊(duì)尾元素的引用push_back：在隊(duì)列尾部入隊(duì)列pop_front：在隊(duì)列頭部出隊(duì)列

標(biāo)準(zhǔn)容器中的deque、list滿足了這些要求，默認(rèn)情況下，使用deque作為底層容器類(lèi)。

queue的使用

代碼訓(xùn)練：

#include<iostream>
#include<stack>
#include<queue>
 
using namespace std;
 
void test_queue()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
 
    cout << q.empty() << endl;
    cout << q.size() << endl;
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}
int main()
{
    test_queue();
    return 0;
}

運(yùn)行結(jié)果：

queue的應(yīng)用

用隊(duì)列實(shí)現(xiàn)棧

問(wèn)題分析：使用兩個(gè)隊(duì)列，重點(diǎn)在于出棧操作，出棧操作，將隊(duì)列1的元素，放到隊(duì)列2，隊(duì)列1的元素只剩下1個(gè)，然后這個(gè)作為出棧的元素，之后q1 = q2，然后將q2的元素進(jìn)行出隊(duì)。

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    MyStack() {
 
    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        int size = q1.size();
        size--;
        while(size--)
        {
            q2.push(q1.front());
            q1.pop();
        }
        int result = q1.front();
        q1.pop();
        q1 = q2;
        while(!q2.empty())
        {
            q2.pop();
        }
        return result;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty();
    }
};

priority_queue的介紹和使用

priority_queue的介紹

priority_queue::priority_queue - C++ Reference (cplusplus.com)

優(yōu)先級(jí)隊(duì)列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個(gè)元素是所有元素中最大的。優(yōu)先級(jí)隊(duì)列的底層是用堆進(jìn)行實(shí)現(xiàn)的，大根堆的堆頂是最大的。標(biāo)準(zhǔn)容器vector和queue都滿足以上要求，如果沒(méi)有特定要求，默認(rèn)使用vector作為底層容器類(lèi)。需要支持隨機(jī)訪問(wèn)迭代器，保證內(nèi)部始終保持堆結(jié)構(gòu)。容器適配器在需要的時(shí)候調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來(lái)自動(dòng)完成此操作。優(yōu)先級(jí)隊(duì)列的底層容器可以使任何標(biāo)準(zhǔn)容器類(lèi)模板，也可以是其他特定設(shè)計(jì)的容器類(lèi)。容器應(yīng)該可以通過(guò)隨機(jī)訪問(wèn)迭代器訪問(wèn)，并支持以下操作： empty()：檢測(cè)容器是否為空。size()：返回容器有效元素個(gè)數(shù)。front()：返回容器第一個(gè)元素的引用push_back()：在容器尾部插入元素pop_back()：刪除容器尾部元素 ??容器適配器 ??什么是適配器

適配器是一種設(shè)計(jì)模式，假設(shè)已經(jīng)有一個(gè)設(shè)計(jì)系統(tǒng)，你需要把新的廠商類(lèi)整合進(jìn)去，但是，新的廠商類(lèi)的接口和原來(lái)的接口不一致，但是，又不可以修改原有的代碼，這個(gè)時(shí)候，就可以設(shè)計(jì)一個(gè)適配器作為中間人，實(shí)現(xiàn)所期望的接口，與新的廠商類(lèi)進(jìn)行對(duì)接。

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

stack和queue是對(duì)標(biāo)準(zhǔn)庫(kù)的其他容器的接口進(jìn)行了包裝，STL的stack和queue默認(rèn)使用deque。

deque的介紹和使用

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

到此這篇關(guān)于圖解C++的STL之stack和queue,輕松理解數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)STL之stack和queue詳解內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論