栈&队列面试题之之两个栈实现一个队列

本是古典何须时尚 2022-09-25 13:21 128阅读 0赞

# 使用两个栈实现一个队列 #

剖析：

我们知道栈是后进先出的一种数据结构，而队列是先进先出的一种数据结构，如何用两个栈来模拟队列这种数据结构呢？利用栈的特性-后进的先出，我们先将数据压入栈1中，在Pop时我们可以将栈1的数据压入栈2中，再将栈2的数据出栈，这就满足了队列的先进后出的特性了.

在Front和Back的实现中.Front返回的是栈2的栈顶元素，Back返回的是栈1的栈顶元素，但是要考虑栈1，栈2是否为空的情况,详细实现见代码部分.

栈2就相当于一个暂存器,而解决这种问题要把握清楚的就是栈和队列的特性.

下图是我从网上搜的一个gif图，我觉得很详细的描述两个栈实现队列的这种情况:

![Center][]

代码实现如下：

template<typename T>
    class QueueBy2Stack
    {
    public:
    	void Push(const T& x)
    	{
    		_stack1.push(x);
    	}
    	void Pop()
    	{
    		assert(!_stack1.empty() || !_stack2.empty());
    		if(_stack2.empty())
    		{
    			//栈2为空栈
    			while(_stack1.size() > 0)
    			{
    				T& tmp=_stack1.top();
    				_stack1.pop();
    				_stack2.push(tmp);
    			}
    		}
    		_stack2.pop();
    	}
    	T& Front()
    	{
    		assert(!_stack1.empty() || !_stack2.empty());
    		if(_stack2.empty())
    		{
    			while(_stack1.size() > 0)
    			{
    				T& tmp=_stack1.top();
    				_stack1.pop();
    				_stack2.push(tmp);
    			}
    		}
    		return _stack2.top();
    	}
    	T& Back()
    	{
    		//此时栈1为空栈
    		assert(!_stack1.empty() || !_stack2.empty());
    		if(_stack1.empty())
    		{
    			while(_stack2.size() > 0)
    			{
    				T& tmp=_stack2.top();
    				_stack2.pop();
    				_stack1.push(tmp);
    			}
    		}
    		return _stack1.top();
    	}
    	bool Empty()
    	{
    		return (_stack1.empty()) && (_stack2.empty());
    	}
    private:
    	stack<T> _stack1;
    	stack<T> _stack2;
    };

test.cpp

void testQueueBy2Stack()
    {
    	QueueBy2Stack<int> qs;
    	qs.Push(1);
    	qs.Push(2);
    	qs.Push(3);
    	qs.Push(4);
    	qs.Push(5);
    	cout<<qs.Front()<<endl;  //1
    	cout<<qs.Back()<<endl;   //5
    	qs.Pop();
    	qs.Pop();
    	cout<<qs.Front()<<endl;  //3
    	cout<<qs.Back()<<endl;   //5
    	qs.Pop();
    	qs.Pop();
    	qs.Pop();
    }

...

[Center]: /images/20220717/130fcd2cdff7496dadf107e45acb377a.png