C++使用適配器模式模擬實現(xiàn)棧和隊列
1.容器適配器
適配器是一種設計模式 ( 設計模式是一套被反復使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設計經(jīng)驗的總結) ， 該種模式是將一個類的接口 轉(zhuǎn)換 成客戶希望的另外一個接口 。
比如說我們?nèi)粘Ｉ钪杏玫某潆娖?，就是一種電源適配器，本質(zhì)就是對電流電壓 轉(zhuǎn)換成我們需要的大小。
2. stack模擬實現(xiàn)
stack滿足只能在一端插入和刪除就行，我們的底層用vector的話可以滿足這個條件，底層用list同樣也可以滿足這個條件。
既然如此，我們就不需要原生實現(xiàn)棧，直接用vector或者list封裝轉(zhuǎn)換一下不就好了。
如果是用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適配轉(zhuǎn)換出stack，傳vector就封裝vector實現(xiàn)，傳list就封裝list實現(xiàn)。
2.2 棧的接口實現(xiàn)
構造函數(shù)我們不用寫，因為_con肯定是自定義結構，所以會調(diào)用自己的構造函數(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封裝轉(zhuǎn)換一下。
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肯定是自定義結構，所以會調(diào)用自己的構造函數(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 按需實例化
我們前面的測試代碼并沒有調(diào)用pop這個接口，當我們調(diào)用pop這個接口時，就會立馬報錯。
void test3()
{
lyj::queue<int, vector<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.pop(); //調(diào)用pop
}
這是因為，類在實例化的時候，不會實例化所有的成員函數(shù)，我們用哪些函數(shù)，就實例化哪些。
前面沒報錯，因為我們根本沒有調(diào)用pop這個成員函數(shù)，可以理解為沒有觸發(fā)到這個錯誤。
編譯器對模板檢查的時候，只會檢查一個大概，明顯的語法錯誤能檢查出來，但是不會檢查細節(jié)，比如說我們在這里調(diào)錯了函數(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的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經(jīng)常遍歷，因此在實際中，需要線性結時，大多數(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 不僅效率高，而且內(nèi)存使用率高。
結合了 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)棧和隊列的詳細內(nèi)容，更多關于C++實現(xiàn)棧和隊列的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了Qt實現(xiàn)界面滑動切換效果,主要包括設計思路及主要函數(shù)講解，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-07-07
掌握C語言數(shù)據(jù)結構的關鍵在于理解其核心概念,擴展字符作為其中的重要一環(huán),對于編程人員來說至關重要,本指南將為您深入剖析擴展字符的相關知識,帶您輕松掌握C語言數(shù)據(jù)結構,讓我們一起探索這個令人著迷的領域吧！2024-03-03
本篇文章是對使用C++實現(xiàn)全排列算法的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++實現(xiàn)LeetCode(43.字符串相乘),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
uboot 屬于bootloader的一種，是用來引導啟動內(nèi)核的，它的最終目的就是從flash中讀出內(nèi)核，放到內(nèi)存中，啟動內(nèi)核，這篇文章主要介紹了uboot添加自定義命令的實現(xiàn)步驟,需要的朋友可以參考下2022-11-11
序列式容器如vector、list等存儲數(shù)據(jù)的邏輯結構為線性序列,元素的存儲和訪問是按位置順序進行的,而關聯(lián)式容器如set、map等,本文給大家介紹C++?set的使用示例詳解,感興趣的朋友一起看看吧2024-10-10
經(jīng)典的推箱子是一個的古老游戲，目的是在訓練你的邏輯思考能力。在一個狹小的倉庫中，要求把木箱放到指定的位置，稍不小心就會出現(xiàn)箱子無法移動或者通道被堵住的情況，所以需要巧妙的利用有限的空間和通道，合理安排移動的次序和位置，才能順利的完成任務2021-11-11
這篇文章主要介紹了C++ lambda 捕獲模式與右值引用的使用,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
這篇文章主要來和大家分享一下C++中，設計一個類要注意哪些東西，這往往也是C++面試時會考到的問題，感興趣的小伙伴可以跟隨小編一起學習一下2023-06-06
這篇文章主要介紹了C++中命名空間的概念及使用詳解,使用命名空間的目的是對標識符的名稱進行本地化，以避免命名沖突或名字污染，namespace關鍵字就是針對這種問題而出現(xiàn)的,需要的朋友可以參考下2023-08-08