C++stack與queue模拟實作

願煦風和日永遠衛護着可愛的你。

stack與queue模拟實作

• • stack
  • queue
  • 為什麼選擇deque作為stack和queue的底層預設容器

在stl中，stack(棧)與queue(隊列)都是容器擴充卡。

什麼是容器擴充卡呢？

擴充卡（adaptor）是标準庫中通用的概念，包括容器擴充卡、疊代器擴充卡和函數擴充卡。本質上，擴充卡是使一事物的行為類似于另一事物的行為的一種機制。容器擴充卡讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實作。簡單來說其實就是利用現有的容器來适配出來的新容器。

stack

在标準庫中，stack預設使用的是deque容器來進行适配的。

當然這裡也可以适配vector容器和list容器。

namespace ZJ
{
	//template<class T,class Container= ZJ::list<T>>
	//template<class T,class Container= ZJ::vector<T>>
	template<class T,class Container= ZJ::deque<T>>
	class stack
	{
	public:
		void pop()
		{
			m_stack.pop_back();
		}

		void push(const T&val)
		{
			m_stack.push_back(val);
		}

		size_t size()	const
		{
			return static_cast<size_t>(m_stack.size());
		}

		T& top()	
		{
			return m_stack.back();
		}

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

		bool empty()	const
		{
			return m_stack.empty();
		}
	private:
		Container m_stack;
	};
}

           

queue

與stack一樣，在标準庫中預設使用的是deque容器來進行适配的。

namespace ZJ
{
	template<class T,class Container=ZJ::deque<T>>
	class queue
	{
	public:
		void pop()
		{
			m_queue.pop_front();
		}

		void push(const T& val)
		{
			m_queue.push_back(val);
		}

		size_t size()	const
		{
			return static_cast<size_t>(m_queue.size());
		}

		T& back()
		{
			return m_queue.back();
		}

		const T& back() const
		{
			return m_queue.back();
		}

		T& front()
		{
			return m_queue.front();
		}

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

		bool empty()	const
		{
			return m_queue.empty();
		}
	private:
		Container m_queue;
	};
}
           

為什麼選擇deque作為stack和queue的底層預設容器

stack是一種後進先出的特殊線性資料結構，是以隻要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；

queue是先進先出的特殊線性資料結構，隻要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。

但是STL中對stack和queue預設選擇deque作為其底層容器，主要是因為：

1. stack和queue不需要周遊(是以stack和queue沒有疊代器)，隻需要在固定的一端或者兩端進行操作。

2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量資料)；queue中的元素增長時，deque不僅效率高，而且記憶體使用率高。

   但是deque有一個緻命缺陷：不适合周遊，特别是在周遊或者排序時，deque的疊代器要頻繁的去檢測其是否移動到某段小空間的邊界，導緻效率低下。

如果小夥伴還沒看懂可以在評論區留言，我會在評論區給你解答！

如有錯誤之處還請各位指出！！！

那本篇文章就到這裡啦，下次再見啦！