當前位置:網站首頁>《STL適配器》stack和queue

《STL適配器》stack和queue

2022-07-23 06:54:42李逢溪

一、本篇目的

1、介紹STL六大組件之一--適配器

2、用list和vector實現stack和queue

二、什麼是適配器?

適配器是一種設計模式(設計模式是一套被反複使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總
)該種模式是將一個類的接口轉換成客戶希望的另外一個接口
簡單來說,適配器其實就是我們寫代碼時的一個好的設計方式。比如我們要寫一個棧,我們可以直接用vector或者list做底層來實現。

三、實現stack

    template<class T, class Con = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_c.push_back(x);
		}
		void pop()
		{
			assert(!empty());
			_c.pop_back();
		}

		bool empty()
		{
			return _c.empty();
		}

		size_t size()
		{
			return _c.size();
		}

		const T& top()
		{
			return _c.back();
		}

	private:
		Con _c;
	};

四、實現隊列

    template<class T, class Con = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_c.push_back(x);
		}

		void pop()
		{
			_c.pop_front();
		}

		size_t size()
		{
			return _c.size();
		}

		bool empty()
		{
			return _c.empty();
		}

		const T& front()
		{
			return _c.front();
		}

		const T& back()
		{
			return _c.back();
		}
	private:
		Con _c;
	};

五、可以用vector做隊列的底層嗎?

void test1()
{
	queue<int, vector<int>> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	while (!s.empty())
	{
		cout << s.front() << endl;
		s.pop();
	}
}

 答:vector不能做queue的底層,因為queue需要pop_front(),而vector並沒有該接口,只有erase接口。

六、為什麼STL裏的stack和queue都是默認使用deque這樣的容器?

 

 這裏需要介紹以下deque,deque是double queue的縮寫,它通常被稱作雙端隊列,因為它在兩端的插入删除效率很高,而隊列和棧正需要的就是兩端插入删除效率高的容器,因此deque常做stack和queue的底層容器。關於deque的底層是如何設計與實現的,我會專門出一篇來闡述deque的設計與實現。

版權聲明
本文為[李逢溪]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/204/202207221913296938.html

隨機推薦