1.容器適配器

適配器是一種設(shè)計模式 ( 設(shè)計模式是一套被反復使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計經(jīng)驗的總結(jié)) ， 該種模式是將一個類的接口 轉(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)

構(gòu)造函數(shù)我們不用寫，因為_con肯定是自定義結(jié)構(gòu)，所以會調(diào)用自己的構(gòu)造函數(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)

構(gòu)造函數(shù)我們還是不用寫，因為_con肯定是自定義結(jié)構(gòu)，所以會調(diào)用自己的構(gòu)造函數(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的底層結(jié)構(gòu)

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為 容器適配器，這是因為stack和queue只是 對其他容器的接口進行了包裝，STL中stack和queue默認 使用deque。

4.2 deque的簡單介紹

文檔介紹：deque - C++ Reference

我們看deque的成員函數(shù)，會發(fā)現(xiàn)deque有點像vector和list的結(jié)合。

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)常遍歷，因此在實際中，需要線性結(jié)時，大多數(shù)情況下優(yōu)先考慮vector和list，deque的應用并不多，而目前能看 到的一個應用就是，STL用其作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。

4.2.3 選deque做棧和隊列的底層默認容器的原因

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。

2. 在 stack 中元素增長時， deque 比 vector 的效率高 ( 擴容時不需要搬移大量數(shù)據(jù) ) ； queue 中的元素增長時，deque 不僅效率高，而且內(nèi)存使用率高。

結(jié)合了 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)容，更多關(guān)于C++實現(xiàn)棧和隊列的資料請關(guān)注腳本之家其它相關(guān)文章！