C++使用適配器模式模擬實現(xiàn)棧和隊列
1.容器適配器
適配器是一種設計模式 ( 設計模式是一套被反復使用的、多數(shù)人知曉的、經過分類編目的、代碼設計經驗的總結) ， 該種模式是將一個類的接口 轉換 成客戶希望的另外一個接口 。
比如說我們日常生活中用的充電器，就是一種電源適配器，本質就是對電流電壓 轉換成我們需要的大小。
2. stack模擬實現(xiàn)
stack滿足只能在一端插入和刪除就行，我們的底層用vector的話可以滿足這個條件，底層用list同樣也可以滿足這個條件。
既然如此，我們就不需要原生實現(xiàn)棧，直接用vector或者list封裝轉換一下不就好了。
如果是用vector實現(xiàn)棧，就是數(shù)組棧，用list實現(xiàn)棧，就是鏈式棧。
2.1 準備工作
我們把棧的所有實現(xiàn)都放在stack.h里，在test.cpp里測試。
在stack.h里，包含會用到的頭文件，用命名空間namespace與庫里面的stack分隔開。
#pragma once
#include <iostream>
#include <list>
#include <vector>
using namespace std;
namespace lyj
{
}在namespace里用模板。
namespace lyj
{
template<class T, class Container>
class stack
{
private:
Container _con;
};
}第一個模板參數(shù)T是棧要存的數(shù)據(jù)類型，第二個模板參數(shù)Container是底層實現(xiàn)的類型，用Container適配轉換出stack，傳vector就封裝vector實現(xiàn)，傳list就封裝list實現(xiàn)。
2.2 棧的接口實現(xiàn)
構造函數(shù)我們不用寫，因為_con肯定是自定義結構，所以會調用自己的構造函數(shù)。
我們把尾當作棧頂。
namespace lyj
{
template<class T, class Container>
class stack
{
public:
void push(const T& x) //插入
{
_con.push_back(x);
}
void pop() //刪除
{
_con.pop_back();
}
const T& top() const //獲取棧頂元素
{
return _con.back();
}
size_t size() const //獲取有效個數(shù)
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};
}就非常方便簡潔。
在test.cpp中使用一下我們寫的這個stack。記得包含頭文件#include "stack"
#include "stack.h"
void test1()
{
lyj::stack<int, vector<int>> st;//注意參數(shù)
st.push(1);
st.push(2);
st.push(3);
}
int main()
{
test1();
return 0;
}
上面顯示就是底層是vector的棧，數(shù)組棧，然后我們插入了一些數(shù)據(jù)。
我們再演示一下底層是list的棧，鏈式棧，只需要把第二個參數(shù)換成list<int>就行。
void test2()
{
lyj::stack<int, list<int>> st;
st.push(1);
st.push(2);
st.push(3);
}
此時，棧的底層發(fā)生了巨大的變化，我們可以把數(shù)據(jù)存在vector實現(xiàn)的棧里面，也可以存在list實現(xiàn)的棧里面。
我們也可以給第二個參數(shù)Container給缺省值。
template<class T, class Container = vector<T>>
3.queue模擬實現(xiàn)
queue要滿足在一端插入，在另一端刪除，我們的底層用list的話可以滿足這個條件，但是此時vector就不滿足這個條件了。那我們先用list封裝轉換一下。
3.1 準備工作
我們把隊列的所有實現(xiàn)都放在queue.h里，在原來的test.cpp里測試。
在queue.h里用命名空間namespace與庫里面的queue分隔開，這個命名空間名字和棧取一樣的。
namespace lyj
{
template<class T, class Container = list<T>>
class queue
{
public:
private:
Container _con;
};
}第一個模板參數(shù)T是棧要存的數(shù)據(jù)類型，第二個模板參數(shù)Container是底層實現(xiàn)的類型，這里Container缺省值給list<T>。
3.2 隊列的接口實現(xiàn)
構造函數(shù)我們還是不用寫，因為_con肯定是自定義結構，所以會調用自己的構造函數(shù)。
queue的代碼和stack大差不差，只是把pop部分變成_con里的頭刪。
template<class T, class Container = list<T>>
class queue
{
public:
void push(const T& x) //隊尾插入
{
_con.push_back(x);
}
void pop() //隊頭刪除
{
_con.pop_front();
}
const T& top() const //獲取隊尾元素
{
return _con.back();
}
const T& front() const //獲取隊頭元素
{
return _con.front();
}
size_t size() const //獲取有效個數(shù)
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};在test.cpp中使用一下我們寫的這個queue。記得包含頭文件#include "squeue"
void test3()
{
lyj::queue<int, list<int>> q;
q.push(1);
q.push(2);
q.push(3);
}
看著沒啥問題。
但是我們給Container傳vector類型時，這個測試代碼居然也可以。
void test3(){lyj::queue<int, vector<int>> q;q.push(1);q.push(2);q.push(3);}vector按理來說不能實現(xiàn)queue，在實現(xiàn)queue的pop部分，vector也沒有pop_front（頭刪）這個接口。代碼為什么沒報錯？
這里就要補充一個知識，按需實例化。
3.3 按需實例化
我們前面的測試代碼并沒有調用pop這個接口，當我們調用pop這個接口時，就會立馬報錯。
void test3()
{
lyj::queue<int, vector<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.pop(); //調用pop
}
這是因為，類在實例化的時候，不會實例化所有的成員函數(shù)，我們用哪些函數(shù)，就實例化哪些。
前面沒報錯，因為我們根本沒有調用pop這個成員函數(shù)，可以理解為沒有觸發(fā)到這個錯誤。
編譯器對模板檢查的時候，只會檢查一個大概，明顯的語法錯誤能檢查出來，但是不會檢查細節(jié)，比如說我們在這里調錯了函數(shù)，用到這個接口時，才會報錯。
所以，在類模板實例化時，只會實例化用到的函數(shù)，這就是按需實例化。
4.deque
4.1 STL標準庫中stack和queue的底層結構
雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為 容器適配器，這是因為stack和queue只是 對其他容器的接口進行了包裝，STL中stack和queue默認 使用deque。
4.2 deque的簡單介紹
我們看deque的成員函數(shù)，會發(fā)現(xiàn)deque有點像vector和list的結合。
vector支持[]，但是vector不直接支持頭刪尾刪。
list支持各種位置插入刪除，但是不支持[]。
既然說到這里了，我們也順便說一下vector和list各自的優(yōu)缺點
4.2.1 vector和list各自的優(yōu)缺點
vector：
優(yōu)點：1.尾插尾刪的效率還不錯，并且支持高效的下標隨機訪問。
2.物理空間連續(xù)，所以高速緩存利用率高。
缺點：1.空間需要擴容，擴容會帶來效率問題和空間的浪費。
2.頭部和中間部分的插入刪除操作效率低。
list：
優(yōu)點：1.按需申請釋放空間，不需要擴容。
2.可以在任意位置插入刪除。
缺點：不支持下標隨機訪問。
4.2.2 deque的優(yōu)缺點
deque的具體底層原理在這里就不詳細說明了，有興趣的可以去查閱資料。我們直接來說一下deque的優(yōu)缺點。
deque：
優(yōu)點：
1.可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)。
2.與vector比較，頭插效率高，不需要搬移元素。
3.與list比較，空間利用率比較高。
缺點：
不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結時，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應用并不多，而目前能看 到的一個應用就是，STL用其作為stack和queue的底層數(shù)據(jù)結構。
4.2.3 選deque做棧和隊列的底層默認容器的原因
1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2. 在 stack 中元素增長時， deque 比 vector 的效率高 ( 擴容時不需要搬移大量數(shù)據(jù) ) ； queue 中的元素增長時，deque 不僅效率高，而且內存使用率高。
結合了 deque 的優(yōu)點，而完美的避開了其缺陷。
5. STL標準庫中對于stack和queue的模擬實現(xiàn)
使用deque時要包含頭文件#include <deque>
5.1 stack
代碼和原來一樣，只是缺省參數(shù)換成deque<T>。
#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
namespace lyj
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x) //插入
{
_con.push_back(x);
}
void pop() //刪除
{
_con.pop_back();
}
const T& top() const //獲取棧頂元素
{
return _con.back();
}
size_t size() const //獲取有效個數(shù)
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};
}在test.cpp里測試一下。
void test4()
{
lyj::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
5.2 queue
代碼和原來一樣，也是缺省參數(shù)換成deque<T>。
#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
namespace lyj
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x) //隊尾插入
{
_con.push_back(x);
}
void pop() //隊頭刪除
{
_con.pop_front();
}
const T& top() const //獲取隊尾元素
{
return _con.back();
}
const T& front() const //獲取隊頭元素
{
return _con.front();
}
size_t size() const //獲取有效個數(shù)
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};
}在test.cpp里測試一下。
void test5()
{
lyj::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
以上就是C++使用適配器模式模擬實現(xiàn)棧和隊列的詳細內容，更多關于C++實現(xiàn)棧和隊列的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要為大家詳細介紹了基于MFC實現(xiàn)貪吃蛇小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
C語言如何求整數(shù)的位數(shù)及各位數(shù)字之和
這篇文章主要介紹了C語言如何求整數(shù)的位數(shù)及各位數(shù)字之和，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了Effective C++ 入門學習筆記,需要的朋友可以參考下2023-08-08
本文詳細介紹了C++中指針類型轉換的必要性、不同類型的指針及其轉換方式,包括static_cast、const_cast、reinterpret_cast和C風格轉換,重點強調了類型安全和內存管理的重要性,并提供了最佳實踐和常見誤區(qū)解答,感興趣的朋友跟隨小編一起看看吧2026-02-02
這篇文章主要為大家詳細介紹了C語言實現(xiàn)基于控制臺的電子時鐘，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹了C++變量和基本類型,,一定要注意局部變量與全局變量的作用范圍,需要的朋友可以參考下,希望能夠給你帶來幫助2021-10-10
這篇文章主要介紹了C++中對象與類的詳解及其作用介紹，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
這篇文章主要和大家詳細介紹如何利用C++做一個簡易的猜數(shù)游戲，分為用戶猜數(shù)和系統(tǒng)猜數(shù)。文中的示例代碼講解詳細 ，感興趣的小伙伴可以嘗試一下2022-11-11
這篇文章主要介紹了Cocos2d-x學習入門之HelloWorld程序,是學習Cocos2d-x的入門程序,其重要性不言而喻,需要的朋友可以參考下2014-08-08
在C語言中調用?Python?腳本的方式有很多,這篇文章主要為大家介紹了人家使用?Python?的?C?API?進行調用?Python?腳本,需要的可以參考一下2025-05-05