两个 stack 容器实现 queue 容器

Stack 容器的特性是先进后出，Queue 容器的特性是先进先出。我们这里可以使用两个 Stack 容器来实现 Queue 容器，一个 Stack 用于存储数据，当需要弹出队头元素时，就将第一个 Stack 容器中的元素弹出并压入到第二个 Stack 容器中，并弹出栈顶元素即可得到队头元素。这里需要注意的是，第一个栈容器中元素压入第二个栈容器的前提条件是，第二个栈容器必须是空的。

#include <iostream>
#include <stack>
using namespace std;


template<class T>
class MyQueue
{
public:
	void push(const T &val)
	{
		m_stack_push.push(val);
		back_val = &m_stack_push.top();
	}

	void pop()
	{
		// 如果两个栈都为空，则返回
		if (m_stack_pop.empty() && m_stack_push.empty())
		{
			return;
		}

		// 如果 pop 栈为空，则将 push 栈元素压入到 pop 栈中
		move(m_stack_push, m_stack_pop);

		m_stack_pop.pop();
	}

	T& front()
	{
		move(m_stack_push, m_stack_pop);
		return m_stack_pop.top();
	}

	T& back()
	{
		move(m_stack_pop, m_stack_push);
		return m_stack_push.top();
	}

	size_t size()
	{
		return m_stack_pop.size() + m_stack_push.size();
	}

	bool empty()
	{
		return m_stack_pop.empty() && m_stack_push.empty();
	}

private:
	// 将一个栈中的元素弹出压入到另一个栈容器中
	// 注意: 目标栈容器如果不为空，则不进行压栈操作
	void move(stack<T> &src, stack<T> &dst)
	{
		if (!dst.empty())
		{
			return;
		}

		while (!src.empty())
		{
			dst.push(src.top());
			src.pop();
		}
	}

private:
	stack<T> m_stack_push;
	stack<T> m_stack_pop;
	T* back_val{nullptr};
};

void test()
{
	MyQueue<int> queue;
	queue.push(10);
	queue.push(20);
	queue.push(30);
	queue.push(40);

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

int main()
{
	test();
	return 0;
}

程序运行结果：