《STL適配器》stack和queue

一、本篇目的

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的設計與實現。