C++ 詳細講解stack與queue的模擬實現

2022-04-15 16:00:37

容器介面卡

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

雙端佇列

概念

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

結構

deque並不是真正的連續空間，而是使用一小段連續的小空間拼接而成，實際上deque類似於一個動態的二維陣列，其底層結構如下圖所示：

中控陣列map： map陣列是一個指標陣列，指向多個buff陣列用來儲存資料，當buff陣列頭或尾滿了，就新開闢一個buff陣列，其指標存在map的相對應位置，當map陣列滿了，會對map陣列擴容(指標陣列的擴容並不會效率低)

deque迭代器

deque所謂的連續空間是一個假象，是他底層複雜的迭代器實現

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陣列對應的指標，由於他指向的也是一個指標·，所以為二級指標。

優缺點

優點：

雙端佇列，說明他很合適頭插頭刪，尾插尾刪，他去做stack和queue的容器介面卡很合適。

缺點：

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

deque是一種折中的方案設計，隨機存取效率不如vector，任意插入刪除不及list

stack模擬

stack是一種容器介面卡，專門在具有後進先出的上下文環境中，其刪除只能是在一端進行操作。

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：在佇列頭部出佇列