目錄

前言

stack

接口介紹

模擬實現(xiàn)

queue

接口介紹

模擬實現(xiàn)

沒有迭代器?

deque介紹

前言

stack 和 queue 本質上是一種容器配接器，就像我們平時充電時使用的電源適配器，能夠將電壓轉換成設備能夠接受的程度。

其通過封裝特定容器作為其底層容器的類，通過一組特定的成員函數(shù)來實現(xiàn)結構的功能。

stack

??stack 就是 STL 中封裝好的棧，在使用的時候我們不僅可以指定內部的數(shù)據(jù)類型，還可以指定內部的容器。

??不指定容器其實也是可以的，內部的模板參數(shù)有一個缺省值。

int main()
{
	stack<int, vector<int>> s1;     //內部容器為vector
	stack<int, list<int>> s2;       //內部容器為list
    stack<int> s3;                  //內部為默認容器deque
	return 0;
}

接口介紹

??庫中還提供了一系列的接口，我們以前如何使用棧就如何使用 stack 即可，下面用一系列代碼來示例一下。?

int main()
{
	stack<int> s;
	s.push(5);          //5
	s.push(6);          //5 6
	s.push(7);          //5 6 7
	s.push(8);          //5 6 7 8
	cout << s.size() << endl;   //打印棧的大小
	while (!s.empty())        //直到棧為空循環(huán)
	{
		cout << s.top() << endl;   //打印棧頂元素
		s.pop();                   //出棧
	}
	return 0;
}

?

模擬實現(xiàn)

??根據(jù)庫中接口簡單地實現(xiàn)一下 stack，需要注意的是這里復用的接口需要確保幾個底部容器都要同時擁有。

namespace Alpaca
{
	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()           //獲取棧頂元素
		{
			return _con.back();  //獲取最后一個元素
		}

		size_t size()            //獲取棧的大小
		{
			return _con.size();  //返回容器的大小
		}

		bool empty()              //棧的判空
		{
			return _con.empty();  //返回容器的判空
		} 

	private:
		Container _con;      //容器對象
	};
}

queue

??queue 則是封裝出來的隊列，與 stack 相反遵循著先進先出的原則(FIFO)。

??通過查詢資料我們還發(fā)現(xiàn)，要作為 queue 的容器還需要支持以下操作：

??同樣，使用 queue 時模板參數(shù)有兩個，分別是內部元素的類型和內部容器，且內部容器缺省為 deque。

int main()
{
	queue<int> q1;                //傳遞缺省模板參數(shù)
	queue<int, list<int>> q2;     //指定內部容器為list
	return 0;
}

接口介紹

??隊列與棧相反，其只在隊尾入隊，在隊頭出隊。我們可以通過實例代碼簡單使用一下。

int main()
{
	queue<int> q;
	cout << "size is: " << q.size() << endl;   //查看隊列大小
	q.push(1);                                 //數(shù)據(jù)入隊
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	cout << "size is: " << q.size() << endl;   
	cout << "first is: " << q.front() << endl; //查看首元素
	cout << "last is: " << q.back() << endl;   //查看最后一個元素
	while (!q.empty())                         //直到隊空循環(huán)
	{
		cout << q.front() << " ";              //打印隊頭
		q.pop();                               //出隊
	}
	cout << endl;
	cout << "size is: " << q.size() << endl;   //查看隊列大小
	return 0;
}

模擬實現(xiàn)

??由于是泛型在使用的時候并不會對內部函數(shù)進行提示，簡單理解就是我們復用對應容器的接口來實現(xiàn)隊列的接口函數(shù)。

namespace Alpaca
{
	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& front()             //獲取隊頭元素
		{
			return _con.front();
		}

		const T& back()              //獲取對尾元素
		{
			return _con.back();
		}

		size_t size()                //獲取隊列大小
		{
			return _con.size();      //獲取容器大小
		}

		bool empty()                 //隊列判空
		{
			return _con.empty();     //容器判空
		}

	private:
		Container _con;
	};

}

沒有迭代器?

??因為無論是 stack 和 queue?都是根據(jù)其特定的順序進行元素的插入和刪除，因此二者都不提供走訪功能，也不提供迭代器。

deque介紹

??在出現(xiàn) vector 和 list 之后，有人想到 vector 能夠隨機讀取，但擴容和隨機插入刪除效率較低，而 list 插入刪除效率都極高卻無法隨機訪問，能不能實現(xiàn)一個結構能夠同時兼顧 vector 和 list 的優(yōu)點呢？

??于是 deque 就誕生了，deque 又叫雙端隊列，即一種雙向開口的連續(xù)線性空間。

??為了兼顧雙端插入以及隨機訪問，deque 的底層是使用一個中控數(shù)組來管理一個個連續(xù)的空間，且第一個空間被開辟出來后是存放在中控數(shù)組的中央位置，之后不斷插入數(shù)據(jù)，若一塊連續(xù)空間已滿只需要再開一塊連續(xù)空間即可。也就是在中控數(shù)組中再增加一個指針。

??若是進行頭插，則需要開辟一段新空間，將新的值存于連續(xù)空間的尾部。

??得益于這種結構，即便是擴容所帶來的拷貝消耗也是極低的，實際上不會像 vector 那樣復雜的深拷貝，而只是對中控數(shù)組中的指針進行拷貝。同時? deque 也支持隨機訪問，只要直到每個連續(xù)空間的大小通過簡單的計算便可以實現(xiàn)隨機訪問。

??若 deque 有這么多的有點，那為什么它還沒有取代 vector 和 list 呢？這就不得不提到 deque 最為雞肋的地方了，中部的插入刪除操作相當復雜，若是直接在中部插入就要挪動當前空間的數(shù)據(jù)，更甚者還要牽扯到接下來的連續(xù)空間。不僅如此 deque 提供的優(yōu)點不如?vector 和 list 那樣極致，這也是為什么?deque 代替不了二者的原因。

??但若是有一種容器并不需要中間的插入刪除，只需要在兩端進行插入刪除呢？于是 deque 就成為了適合 stack 和 queue 實現(xiàn)的內部容器。

??好了，今天 stack、queue基本使用和模擬實現(xiàn)?的相關內容到這里就結束了，如果這篇文章對你有用的話還請留下你的三連加關注。文章來源地址http://www.zghlxwxcb.cn/news/detail-471361.html

到了這里，關于【STL】stack、queue基本使用和模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！