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

àì夳堔傛蜴生んèń 2022-09-26 01:57 183阅读 0赞

# 两个队列实现一个栈 #

在之前我曾经实现了两个栈实现一个队列的面试题，其实思路也很简单就是充分利用栈的特性-后进先出，将输入的数据先输入栈1，将该栈1再输出到栈2，最后将栈2的数据输出，利用这个交换的特性实现两个栈实现一个队列.

那仫如何利用两个队列实现一个栈呢？

## 思路分析篇： ##

其实思路类似之前的面试题-两个栈实现一个队列，也是通过交换的特性：

(1).先将要输入的数据类似 1->2->3->4->5输入到队列1中

(2).在Pop时则需要一点技巧了，因为是模拟实现栈，所以出栈的顺序为5->4->3->2->1.如果队列1不为空则将队列1的前n-1个数据尾插到队列2中，队列1中只剩下最后一个元素n-在上面这种情况下我们将 1 2 3 4从队列1中删除尾插到队列2中，队列1中只剩下5

(3).如果我们将队列1剩下的数据删除掉，则正好满足出栈顺序的第一个元素，此时队列1为空--如果此时再插入数据(6)，我们只能将该数据尾插到队列2中(保证出栈顺序不被改变);如果我们没有将队列1中的最后一个元素n删除掉，则此时插入数据则将该数据插入到队列1中，同样是为了满足出栈顺序.

(4).之前提到队列1为空，队列2为1->2->3->4->6，和刚才的想法类似，将队列2的前n-1个数据尾插到队列1中，队列2中只剩下最后一个元素n,将队列2中的最后一个数据Pop掉就是现在的栈顶元素啦!!!

...以后的步骤类似(4).

下图是我画的一个简单的实现过程:

![Center][]

## 代码实现篇： ##

//两个队列实现一个栈
    template<typename T>
    class StackBy2Queue
    {
    public:
    	void Push(const T& x)
    	{
    		if(_queue1.size() > 0)
    			//如果队列1不为空则将数据插入到队列1中
    			_queue1.push(x);
    		else if(_queue2.size() > 0)
    			//队列1为空队列2不为空插入到队列2中
    			_queue2.push(x);
    		else
    			_queue1.push(x);
    	}
    	void Pop()
    	{
    		assert(!_queue1.empty() || !_queue2.empty());
    		if(_queue2.empty())
    		{
    			//队列2为空时
    			while(_queue1.size() > 1)
    			{
    				//保留队列1原本的队尾元素
    				_queue2.push(_queue1.front());
    				_queue1.pop();
    			}
    			_queue1.pop();
    		}
    		else
    		{
    			//队列2不为空
    			while(_queue2.size() > 1)
    			{
    				//保留队列2的队尾元素
    				_queue1.push(_queue2.front());
    				_queue2.pop();
    			}
    			_queue2.pop();
    		}
    	}
    	T& Top()
    	{
    		if(_queue1.size() > 0)
    			return _queue1.back();
    		else
    			return _queue2.back();
    	}
    	bool Empty()
    	{
    		//两个队列都为空时才为空
    		return (_queue1.empty()) && (_queue2.empty());
    	}
    	size_t Size()
    	{
    		return _queue1.size()+_queue2.size();
    	}
    private:
    	queue<T> _queue1;
    	queue<T> _queue2;
    };

test.cpp

void testStackBy2Queue()
    {
    	StackBy2Queue<int> sq;
    	sq.Push(1);
    	sq.Push(2);
    	sq.Push(3);
    	sq.Push(4);
    	sq.Push(5);
    	cout<<sq.Top()<<endl;  //5
    	sq.Pop();
    	cout<<sq.Top()<<endl;  //4
    	sq.Push(6);
    	cout<<sq.Top()<<endl;  //6
    	cout<<sq.Size()<<endl;  //5
    	sq.Pop();
    	sq.Pop();
    	sq.Pop();
    	sq.Pop();
    	sq.Pop();
    }

这只是我个人的一点小小理解，如果有问题希望指出.

[Center]: /images/20220717/64400e7ee1ec479180e52aae2347b23d.png