C++中stack與queue的使用方法

本篇內(nèi)容介紹了“C++中stack與queue的使用方法”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

stack與queue模擬實現(xiàn)

在stl中，stack(棧)與queue(隊列)都是容器適配器。

什么是容器適配器呢？

適配器（adaptor）是標(biāo)準(zhǔn)庫中通用的概念，包括容器適配器、迭代器適配器和函數(shù)適配器。本質(zhì)上，適配器是使一事物的行為類似于另一事物的行為的一種機制。容器適配器讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實現(xiàn)。簡單來說其實就是利用現(xiàn)有的容器來適配出來的新容器。

stack

在標(biāo)準(zhǔn)庫中，stack默認使用的是deque容器來進行適配的。
當(dāng)然這里也可以適配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一樣，在標(biāo)準(zhǔn)庫中默認使用的是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是一種后進先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，因此只要具有push_back()和pop_back()操作的線性結(jié)構(gòu)，都可以作為stack的底層容器，比如vector和list都可以；

queue是先進先出的特殊線性數(shù)據(jù)結(jié)構(gòu)，只要具有push_back和pop_front操作的線性結(jié)構(gòu)，都可以作為queue的底層容器，比如list。

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

1.stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。

2.在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數(shù)據(jù))；queue中的元素增長時，deque不僅效率高，而且內(nèi)存使用率高。

但是deque有一個致命缺陷：不適合遍歷，特別是在遍歷或者排序時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導(dǎo)致效率低下。

“C++中stack與queue的使用方法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！