目錄

• • 什么是容器適配器
  • stack
  • • stack的文檔介紹-（來自cplusplus）
    • stack的實現(xiàn)
  • queue
  • • queue的文檔介紹-（來自cplusplus）
    • queue的實現(xiàn)

---

什么是容器適配器

之前模擬實現(xiàn)的vector,string,list等都是容器，而這次要實現(xiàn)的stack和queue則是容器適配器，那么什么是容器適配器呢？
適配器其實就是一個轉換裝置，這種東西在生活中非常常見。例如將USB接口轉為Type-c接口，就可以在手機上用U盤，又或者三腳插頭轉二腳插頭，方便使用更多的插座。適配器的作用就是在不更換設備的情況下，能讓我們的設備適用于其他情景，或者擁有別的功能。
在STL中，stack和queue其實就是傳統(tǒng)數(shù)據(jù)結構中的棧和隊列，我們并不關心他的底層是什么，因為我們只需要保證他具有后進先出和先進先出的特點即可，這個特點，無論是使用vector，還是list都可以實現(xiàn)，既然這樣，那就干脆將其作為一個適配器，不需要再創(chuàng)建新的容器，而是直接在原有的容器上實現(xiàn)他的特性即可，并且這個容器可以有多種選擇。

---

stack

stack的文檔介紹-（來自cplusplus）

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

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

stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應該支持以下 操作： empty：判空操作 back：獲取尾部元素操作 push_back：尾部插入元素操作 pop_back：尾部刪除元素操作

標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器， 默認情況下使用deque。

---

stack的實現(xiàn)

stack的實現(xiàn)其實就是棧的實現(xiàn)，只需要在復用原有代碼的基礎上增加stl的特性即可，
下面是之前數(shù)據(jù)結構篇章時實現(xiàn)的棧
棧的實現(xiàn)

庫中默認選擇的容器是deque

#include<deque>namespace lee {/*STL底層中的容器選擇的是deque，因為deque是假想的連續(xù)空間，他每次插入時擴容都會直接在插入的地方直接插入一片固定大小的空間，這樣就保證了邏輯上的線性，不需要拷貝數(shù)據(jù)。而vector每次擴容，都需要創(chuàng)建新空間，拷貝原數(shù)據(jù)，銷毀原空間，并且開的空間是原數(shù)據(jù)的1.5倍或2倍（不同版本）vector不僅效率不比deque高，空間的利用率也不高，多次擴容會導致空間的碎片化*/template<class T, class Container = std::deque<T>>class stack{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}T& top() {return _con.back();}const T& top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;}; }

---

queue

queue的文檔介紹-（來自cplusplus）

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

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

底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。該底層容器應至少支持以下操 作: empty：檢測隊列是否為空 size：返回隊列中有效元素的個數(shù) front：返回隊頭元素的引用 back：返回隊尾元素的引用 push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列

標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標 準容器deque。

---

queue的實現(xiàn)

隊列的實現(xiàn)

庫中默認選擇的容器是deque

#include<deque>namespace lee {/*STL中queue底層的容器是deque，因為deque和list一樣插入刪除的效率都是O（1），并且deque的效率更高，因為list是一次創(chuàng)建一個結點后插入，并且這些空間是離散分布的.deque是每次創(chuàng)建一個固定大小的空間，并在這塊空間上面進行插入刪除，這樣的效率更高，并且因為申請的空間都是一段一段的連續(xù)空間，內存的利用率更高*/template<class T, class Container = std::deque<T>>class queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;}; }

總結

以上是生活随笔為你收集整理的C++ STL : 模拟实现STL中的容器适配器stack和queue的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。