【c++】:“無敵的适配器來咯“棧和隊列模拟實現以及優先級隊列的模拟實現。

文章目錄

• 前言
• 一.棧和隊列的模拟實現
• 二.優先級隊列
• 總結

   

  ---

  前言

  棧的介紹和使用：

  1. stack是一種容器适配器，專門用在具有後進先出操作的上下文環境中，其删除隻能從容器的一端進行元素的插入與提取操作。 2. stack是作爲容器适配器被實現的，容器适配器即是對特定類封裝作爲其底層的容器，并提供一組特定的成員函數來訪問其元素，将特定類作爲其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。 3. stack的底層容器可以是任何标準的容器類模闆或者一些其他特定的容器類，這些容器類應該支持以下操作： empty：判空操作 back：獲取尾部元素操作 push_back：尾部插入元素操作 pop_back：尾部删除元素操作 4. 标準容器vector、deque、list均符合這些需求，默認情況下，如果沒有爲stack指定特定的底層容器，默認情況下使用deque。   隊列的介紹和使用： 1. 隊列是一種容器适配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。 2. 隊列作爲容器适配器實現，容器适配器即将特定容器類封裝作爲其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。 3. 底層容器可以是标準容器類模闆之一，也可以是其他專門設計的容器類。該底層容器應至少支持以下操作: empty：檢測隊列是否爲空 size：返回隊列中有效元素的個數 front：返回隊頭元素的引用 back：返回隊尾元素的引用 push_back：在隊列尾部入隊列 pop_front：在隊列頭部出隊列 4. 标準容器類deque和list滿足了這些要求。默認情況下，如果沒有爲queue實例化指定容器類，則使用标準容器deque。

  ---

   

  一、棧和隊列的模拟實現

  容器适配器：

  适配器是一種設計模式(設計模式是一套被反複使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)， 該種模式是将一個類的接口轉換成客戶希望的另外一個接口。

  前面我們說過stack和queue是一種容器适配器，同樣也是作爲容器适配器被實現的，所以我們可以直接使用一個公共的容器來當stack的适配器，适配器是用來轉換的，将已有的東西進行轉換，比如将vector當我們棧的容器實現棧的功能，我們先看一下庫中如何描述棧的：

  

   可以看到庫中是用的deque來當stack的容器，并且stack的接口非常簡單，所以我們現在就開始實現：

  #include 
  #include 
  using namespace std;
  namespace sxy
  {
  	template
  	class stack
  	{
  	public:
  		void push(const T& x)
  		{
  			_con.push_back(x);
  		}
  		void pop()
  		{
  			_con.pop_back();
  		}
  		T& top()
  		{
  			return _con.back();
  		}
  		const T& top() const
  		{
  			return _con.back();
  		}
  		size_t size() const
  		{
  			return _con.size();
  		}
  		bool empty() const
  		{
  			return _con.empty();
  		}
  	private:
  		Container _con;
  	};
  	void test3()
  	{
  		stack st;
  		st.push(1);
  		st.push(2);
  		st.push(3);
  		st.push(4);
  		while (!st.empty())
  		{
  			cout