容器適配器

適配器是一種設(shè)計(jì)模式（設(shè)計(jì)模式是一套反復(fù)使用的、大部分人知道的代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)），該模式試講一個(gè)類的接口轉(zhuǎn)化為用戶希望的另一個(gè)接口，雖然stack與queue中也可以存放元素，但在STL中并沒(méi)有將其劃分為容器，而是成為容器適配器，這是因?yàn)閟tack與隊(duì)列只是堆其他容器進(jìn)行了包裝，STL中的stack和queue是使用雙端隊(duì)列進(jìn)行封裝的。

雙端隊(duì)列

概念

它是一種雙開(kāi)口的連續(xù)空間數(shù)據(jù)結(jié)構(gòu)（與隊(duì)列沒(méi)有關(guān)系），雙開(kāi)口的含義是可以再兩端進(jìn)行插入刪除操作，且時(shí)間復(fù)雜度為O(1)，與vector比較，頭插效率比較高，不需要移動(dòng)數(shù)據(jù)，與list比較，空間利用率高。

結(jié)構(gòu)

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

中控?cái)?shù)組map： map數(shù)組是一個(gè)指針數(shù)組，指向多個(gè)buff數(shù)組用來(lái)儲(chǔ)存數(shù)據(jù)，當(dāng)buff數(shù)組頭或尾滿了，就新開(kāi)辟一個(gè)buff數(shù)組，其指針存在map的相對(duì)應(yīng)位置，當(dāng)map數(shù)組滿了，會(huì)對(duì)map數(shù)組擴(kuò)容(指針數(shù)組的擴(kuò)容并不會(huì)效率低)

deque迭代器

deque所謂的連續(xù)空間是一個(gè)假象，是他底層復(fù)雜的迭代器實(shí)現(xiàn)

STL源碼：

typedef T** map_pointer;
T* cur;
T* first;
T* last;
map_pointer node

• cur:是當(dāng)前的node指向的buff數(shù)組當(dāng)前指向的地址
• first：是當(dāng)前node指向的buff數(shù)組，第一個(gè)元素的地址。
• last:是當(dāng)前node指向的buff數(shù)組，最后一個(gè)元素的地址。
• node：是指向當(dāng)前map數(shù)組對(duì)應(yīng)的指針，由于他指向的也是一個(gè)指針·，所以為二級(jí)指針。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

雙端隊(duì)列，說(shuō)明他很合適頭插頭刪，尾插尾刪，他去做stack和queue的容器適配器很合適。

缺點(diǎn)：

雙端隊(duì)列中間插入刪除非常麻煩，效率不高。

deque是一種折中的方案設(shè)計(jì)，隨機(jī)訪問(wèn)效率不如vector，任意插入刪除不及l(fā)ist

stack模擬

stack是一種容器適配器，專門(mén)在具有后進(jìn)先出的上下文環(huán)境中，其刪除只能是在一端進(jìn)行操作。

stack是作為容器適配器被實(shí)現(xiàn)的，容器適配器即是對(duì)特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出 。

stack的底層原理可以是任何標(biāo)椎的容器類模板或者一些特定的容器類，這些容器類應(yīng)該支持以下操作：

• empty:判空操作。
• back:尾部元素獲取。
• push_back：尾部插入元素操作
• pop_back:尾部刪除元素操作。

模擬實(shí)現(xiàn)

template<class T, class Con = deque<T>>
    class stack
    {
    public:
        stack();
        void push(const T& x)
        {
            _c.push_back(x);
        }
        void pop()
        {
            _c.pop_back();
        }
        T& top()
        {
            return _c.back()
        }
        const T& top()const
        {
            return _c.back();
        }
        size_t size()const
        {
            return _c.size();
        }
        bool empty()const
        {
            return _c.empty();
        }
    private:
        Con _c;
    };
?

queue模擬實(shí)現(xiàn)

隊(duì)列是一種容器適配器，專門(mén)用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素

隊(duì)列作為容器適配器實(shí)現(xiàn)，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來(lái)訪問(wèn)其元素。元素從隊(duì)尾入隊(duì)列，從隊(duì)頭出隊(duì)列

底層容器可以是標(biāo)準(zhǔn)容器類模板之一，也可以是其他專門(mén)設(shè)計(jì)的容器類。該底層容器應(yīng)至少支持以下操作:

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

模擬實(shí)現(xiàn)

template<class T, class Con = deque<T>>
    class queue
    {
        public:
            queue();
            void push(const T& x)
            {
                _c.push_back(x);
            }
            void pop()
            {
                _c.pop_front();
            }
            T& back()
            {
                return _c.back();
            }
            const T& back()const
            {
                return _c.back();
            }
            T& front()
            {
                return _c.front();
            }
            const T& front()const
            {
                return _c.front();
            }
            size_t size()const
            {
                return _c.size();
            }
            bool empty()const
            {
                return _c.empty();
            }
        private:
            Con _c;
    };

到此這篇關(guān)于C++ 詳細(xì)講解stack與queue的模擬實(shí)現(xiàn) 的文章就介紹到這了,更多相關(guān)C++ stack與queue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論