適配器是一種設計模式（設計模式是一套反復使用的、大部分人知道的代碼設計經驗的總結），該模式試講一個類的接口轉化為用戶希望的另一個接口，雖然stack與queue中也可以存放元素，但在STL中并沒有將其劃分為容器，而是成為容器適配器，這是因為stack與隊列只是堆其他容器進行了包裝，STL中的stack和queue是使用雙端隊列進行封裝的。

雙端隊列

概念

它是一種雙開口的連續(xù)空間數據結構（與隊列沒有關系），雙開口的含義是可以再兩端進行插入刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率比較高，不需要移動數據，與list比較，空間利用率高。

結構

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

中控數組map： map數組是一個指針數組，指向多個buff數組用來儲存數據，當buff數組頭或尾滿了，就新開辟一個buff數組，其指針存在map的相對應位置，當map數組滿了，會對map數組擴容(指針數組的擴容并不會效率低)

deque迭代器

deque所謂的連續(xù)空間是一個假象，是他底層復雜的迭代器實現

STL源碼：

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

cur:是當前的node指向的buff數組當前指向的地址
first：是當前node指向的buff數組，第一個元素的地址。
last:是當前node指向的buff數組，最后一個元素的地址。
node：是指向當前map數組對應的指針，由于他指向的也是一個指針·，所以為二級指針。

優(yōu)缺點

優(yōu)點：

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

缺點：

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

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

stack模擬

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

stack是作為容器適配器被實現的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。

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

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

模擬實現

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模擬實現

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

隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列

底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。該底層容器應至少支持以下操作:

empty：檢測隊列是否為空
size：返回隊列中有效元素的個數
front：返回隊頭元素的引用
back：返回隊尾元素的引用
push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列

模擬實現

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;
    };

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

您可能感興趣的文章: