stack,queue,priority_queue的模擬實作

stack的模擬實作

堆疊是一種先入后出的資料結構，主要具有以下介面

上面就是stack(堆疊)的主要功能了，而這次我們要利用自己寫的堆疊來實作這些結果

在上面的例子中我們利用系統提供的stack實作了對堆疊的push,pop,top,size,empty等介面，下面我們就要利用自己所寫的堆疊模擬實作這些功能，具體的功能我會在下面代碼中詳細解答

namespace hello
{
    //該種寫法為容器配接器的寫法:借助deque容器來實作對stack的模擬實作
        template<class T, class Container = deque<T>>
        class stack
        {
        public:
            stack()
            {
            }
			//直接借助deque的尾插實作對堆疊的插入
            void push(const T& x)
            {
                _c.push_back(x);
            }
            //直接進行尾刪
            void pop()
            {
                _c.pop_back();
            }
			//回傳最后一個元素
            T& top()
            {
                return _c.back();
            }
			//被const的stack的回傳
            const T& top()const
            {
                return _c.back();
            }
			//回傳堆疊的大小
            size_t size()const
            {
                return _c.size();
            }
			//判斷堆疊是否為空
            bool empty()const
            {
                return _c.empty();
            }
            
        private:
            Container _c;
        };
}

堆疊的實作主要是借助其它容器進行實作的，內容非常簡單，下面我們來看一下自己寫的堆疊的功能：

佇列的模擬實作

佇列是一種先入先出的資料結構，主要有以下介面：

這就是我們模擬實作的效果，它的實作和我們上面實作堆疊幾乎是一樣的，都是借助deque實作的

namespace hello
{
    //配接器模式
	template<class T, class Container=deque<T>>
	class queue
	{
	public:
		queue()
		{

		}
        //尾部插入資料
		void push(const T& x)
		{
			_con.push_back(x);
		}
		//洗掉隊頭資料
		void pop()
		{
			_con.pop_front();
		}
		//回傳隊尾資料
		T& back()
		{
			return _con.back();
		}
		//const修飾的queue，回傳隊尾元素
		const T& back()const
		{
			return _con.back();
		}
		//回傳隊頭元素
		T& front()
		{
			return _con.front();
		}
		const T& front()const
		{
			return _con.front();
		}
		//回傳隊伍中的元素個數
		size_t size()const
		{
			return _con.size();
		}
		//判斷queue是否為空
		bool empty()const
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}

priority_queue的模擬實作

優先級佇列是佇列的一種特殊情況，它入佇列順序隨意，出佇列順序按照資料的優先出佇列

它底層的資料結構是陣列，里面包含了一些堆的演算法

在模擬實作時不論建大堆還是小堆都是可以的

它包含于頭檔案,主要有以下介面：

在優先級佇列中有仿函式：less(降序排列),greater(升序排列)，默認的話是less降序排列

仿函式：

仿函式(functor)，就是使一個類的使用看上去像一個函式，其實作就是類中實作一個operator()，這個類就有了類似函式的行為，就是一個仿函式類了，

int main()
{
	std::priority_queue<int>q;
	//hello::priority_queue<int, vector<int>, hello::less<int> > q;
	q.push(5);
	q.push(6);
	q.push(1);
	q.push(3);
	q.push(4);
	q.push(10);
	q.push(-15);
	while (!q.empty())
	{
		cout << q.top() << endl;
		q.pop();
	}
	return 0;
}

如上所示，我們在系統默認提供的優先級佇列中添加一群無序的資料，在我們不指定排列方式的時候他會默認以降序的方式排列，要想以升序方式排列也很簡單，只需定義優先級佇列時加入排列方式即可

s t d : : p r i o r i t y q u e u e < i n t , v e c t o r < i n t > , s t d : : g r e a t e r < i n t > > q ; std::priority_queue<int,vector<int>,std::greater<int>>q; std::priorityq?ueue<int,vector<int>,std::greater<int>>q;

int main()
{
	std::priority_queue<int,vector<int>,std::greater<int>>q;
	//hello::priority_queue<int, vector<int>, hello::less<int> > q;
	q.push(5);
	q.push(6);
	q.push(1);
	q.push(3);
	q.push(4);
	q.push(10);
	q.push(-15);
	while (!q.empty())
	{
		cout << q.top() << endl;
		q.pop();
	}
	return 0;
}

如上圖所示，即為升序排列結果，下面就來模擬實作一下，重點內容我都注釋在代碼中了

namespace hello
{
	template<class T>
	class less//建大堆，逆序輸出
	{
	public:
		bool operator()(T& l, T& r)
		{
			return l < r;
		}
	};

	template<class T>
	class greater
	{
	public:
		bool operator()(T&l,T&r)
		{
			return l > r;
		}
	};

	template<class T,class Container =vector<T>,class Compare =less<T>>
	class priority_queue
	{
	public:
		//1.push
        //向上調整演算法
		void AdjustUp(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[child]>_con[parent])
				if(com(_con[parent],_con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T&val)
		{
            //首先push元素，然后利用向上調整演算法將其調整到合適的位置
			_con.push_back(val);
			//向上調整演算法
			AdjustUp(_con.size() - 1);
		}

		//2.pop
        //向下調整演算法：用來洗掉堆頂元素后將其調整到合適的位置
		void AdjustDown(size_t parent)
		{
			Compare com;
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child],_con[child+1]))
				{
					child++;
				}
				//if (_con[child] < _con[parent])
				if(com(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			//在堆的洗掉演算法中，首先交換堆頂和堆尾的資料，然后洗掉堆尾元素，最后使用向下調整演算法將其調整到合適的位置
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			//使用向下查找演算法將其調整到合適的位置
			AdjustDown(0);
		}

		//3.top：回傳堆頂元素
		T& top()
		{
			return _con[0];
		}

		//4.size：回傳大小
		size_t size()
		{
			return _con.size();
		}

		//5.empty：判斷是否為空
		bool empty()
		{
			return _con.empty();
		}


	private:
		Container _con;
	};
}

下面我們來看一下效果：

如上圖所示，我們利用自己模擬實作的priority_queue實作了其基本功能，下面再看一下升序排列吧：

好了，以上就是本片文章所有內容了，歡迎大家一鍵三聯，也歡迎大家斧正，感謝大家的支持