C++：stack 和 queue 的使用和模拟实现

时间：2024-10-30 08:00:57

使用

要注意，stack 和 queue 没有迭代器。

stack

void teststack()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);

	cout << st.size() << endl;

	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}

queue

void testqueue()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);

	cout << q.size() << endl;

	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
}

模拟实现

由于C++ 模板的存在，stack 和 queue 的实现就不必再重新编写代码，可以直接复用 vector 和 list ，从而实现 stack 和 queue 。也就是说， stack 和 queue 只是利用其他容器进行包装得到的。

这种将一个类的接口转换成另外一个接口的设计模式成为适配器模式。

stack

namespace Friend
{
	template<class T, class Container = vector<T>>
	class stack
	{
	public:
		// 构造函数、拷贝构造、赋值重载、析构函数不用写
		// 其会调用 Container 的构造、析构等

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

		void pop()
		{
			con.pop_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 teststack()
	{
		stack<int> st;
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);
		st.push(5);

		cout << st.size() << endl;

		while (!st.empty())
		{
			cout << st.top() << " ";
			st.pop();
		}
		cout << endl;
	}
}

queue

namespace Friend
{
	template<class T, class Container = list<T>>
	class queue
	{
	public:
		// 构造函数、拷贝构造、赋值重载、析构函数不用写
		// 其会调用 Container 的构造、析构等

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

		void pop()
		{
			con.pop_front();
		}

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

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

		size_t size() const
		{
			return con.size();
		}

		bool empty() const
		{
			return con.empty();
		}

	private:
		Container con;
	};

	void testqueue()
	{
		queue<int> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		q.push(5);

		cout << q.size() << endl;

		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

deque

但在 STL 中，stack 和 queue 的实现利用的不是 vector 和 list ，而是 deque 。

deque，又称为双端队列，是一种双开口的 "连续" 空间的数据结构，其可以在头尾两端 进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。

但其也存在致命的缺点，由于其结构的特殊性，其 insert 和 erase 以及遍历等操作十分耗时，效率低下。因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list ，deque 的应用并不多，其中一个就是 STL 用其作为 stack 和 queue 的底层数据结构。

但其作为 stack 和 queue 的底层数据结构，是十分完美的，其完美避开了 deque 的缺点。

        1.  stack 和 queue 不需要遍历 ( 因此stack和queue没有迭代器 ) ，只需要在固定的一端或者两端进行操作。

        2.  在 stack 中元素增长时，deque 比 vector 的效率高 ( 扩容时不需要搬移大量数据 )；queue中的元素增长时，deque 不仅效率高，而且内存使用率高。

因此，STL 实现 stack 和 queue 为：

相关文章