面试题：两个栈实现一个队列

面试中，经常出现让你手写两个队列实现一个栈，或者两个栈实现一个队列的问题，很是头疼！

今天我们先探讨下：两个栈如何实现一个队列？

视频讲解：用两个栈实现一个队列（知乎视频）

两个栈实现一个队列

1、栈的特点

栈的特点是先进后出，进出元素都是在同一端（栈顶）。

1）入栈

2）出栈

2、队列的特点

队列的特点是先进先出，出入元素是在不同的两端（队头和队尾）。

1）入队

2）出队

3、两个栈实现队列

我们拥有两个栈，可以让其中一个栈作为队列的入口，负责插入新元素；另一个栈作为队列的出口，负责移除老的元素。

队列的主要操作无非有两个：入队和出队。

在模拟入队操作时，每一个新元素都被压入到栈A当中。

1）让元素1“入队”：

2）让元素2“入队”：

3）让元素3“入队”：

这时候，我们希望最先“入队”的元素1“出队”，需要怎么做呢？

让栈A中的所有元素按顺序出栈，再全部按照出栈顺序压入栈B。

这样一来，元素从栈A弹出并压入栈B的顺序是3,2,1，和当初进入栈A的顺序1，2，3是相反的：

1）让元素1“出队”，也就是让元素1从栈B弹出：

2）让元素2“出队”

如果这个时候又想做入队操作了呢？当有新元素入队时，重新把新元素压入栈A。

4）让元素4“入队”：

此时的出队操作仍然从栈B弹出元素。

3）让元素3“出队”

这个时候栈B已经空了，如果再想出队怎么办呢？

只要栈A还有元素（不为空），就像刚才一样，把栈A元素全部弹出并压入栈B。

4）让元素4“出队”

4、实现思路

1）使用两个栈A,B，其中假定栈A负责push操作，栈B负责pop操作。使用一个变量back_elem来存储最后添加的元素。

2）实现队列的push操作，每次进行添加操作，都会相应的对栈A进行添加元素，并对back_elem赋值

3）实现队列的pop操作，每次进行删除操作，因为栈B负责pop操作，

首先判断栈B（pop操作）是否为空？

a. 如果栈B为空，则判断栈A是否为空？（这很关键，是算法的核心）

如果栈A也为空，则输出错误信息，此时整个队列为空，即栈A和栈B都为空。

如果栈A不为空，则将栈A中的所有数据全部再次压栈存储到栈B中。

即 B.push(A.top()), A.pop(). 然后在对栈B执行，B.pop()操作，将队列的头元素删除

b. 如果B不为空，则直接对B执行 B.pop()操作。

例如：

首先，对栈A进行push操作，依次压入a,b,c，

然后，把栈A的全部元素压入栈B，

最后，对栈B实现pop操作，依次弹出a,b,c

4）实现队列的front()操作，方法如pop操作相同，只是在最后一步使用B.top()返回值。

5）实现队列的back()操作，因为我们变量back_elem保存着最后一个输入的数据，故直接将其返回。

6）实现队列的size()操作，和empty()操作，就是对A,B分别执行操作。

5、代码实现

1）C/C++代码实现

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
template<typename T>
class Queue {
private:
	stack<T>stackA;	//栈A
	stack<T>stackB;	//栈B
	T back_elem;	//用于存储新添加的元素
public:
	void push(T elem);	//将新元素压入队列（压入栈A）中
	void pop();			//将元素弹出队列（从栈B中弹出）
	T front();			//队首元素
	T back();			//队尾元素
	int size()const;    //队列长度
	bool empty()const;  //队列是否为空
};
 
/*
入队操作
实现队列的push操作， 每次进行添加操作，都会相应得对栈A进行添加元素。并对back_elem赋值
*/
template<typename T>
void Queue<T>::push(T elem)
{
	stackA.push(elem);//将元素压入队列
	back_elem = elem;	//存储新添加的元素
}
 
/*
出队操作
实现队列的pop操作，每次进行删除操作，因为栈B负责pop操作。
首先判断栈B是否为空？
a.如果栈B为空，则判断A是否为空？
		如果A也为空，则输出错误信息，此时队列为空。
		如果A不为空，则将栈A中的所有数据存储到B中。执B.push(A.top()), A.pop().然后在对栈B
			执行，B.pop()操作，将队列的头元素删除
b.如果栈B不为空， 则直接对栈B执行 B.pop()操作。
*/
template<typename T>
void Queue<T>::pop()
{
	//判断栈B是否为空？
	if (!stackB.empty())	//栈B不为空， 则直接对栈B执行 B.pop()操作。
	{
		stackB.pop();
	}
	else if (!stackA.empty())	//栈B为空，则判断栈A是否为空？栈A不为空,则将栈A中的所有数据
   //存储到B中。执B.push(A.top()), A.pop().然后在对栈B执行，B.pop()操作，将队列的头元素删除
	{
		stackB.push(stackA.top());
		stackA.pop();
	}
	else
	{
		std::cout << "error pop(),empty queue!" << std::endl;
	}
}
 
/*
队首元素
*/
template<typename T>
T Queue<T>::front()
{
	if (!stackB.empty())
	{
		return stackB.top();
	}
	else if (!stackA.empty())
	{
		while (!stackA.empty())
		{
			stackB.push(stackA.top());
			stackA.pop();
		}
		return stackB.top();
	}
	else
	{
		std::cout << "error front(),empty queue!" << std::endl;
	}
}
 
/*
队尾元素
*/
template<typename T>
T Queue<T>::back()
{
	if (!empty())
	{
		return back_elem;
	}
	else
	{
		std::cout << "error back(),empty queue!" << std::endl;
	}
}
 
/*
队列长度
*/
template<typename T>
int Queue<T>::size() const
{
	return stackA.size() + stackB.size();
}
 
/*
队列是否为空
*/
template<typename T>
bool Queue<T>::empty() const {
	return stackA.empty() && stackB.empty();
}
 
int main()
{
	Queue<int>queue;
	//入队操作
	queue.push(1);
	queue.push(2);
	queue.push(3);
	queue.push(4);
	cout << "Four times push() After:" << endl;
	//队首元素
	cout << "The queue front:" << queue.front() << endl;
	//队尾元素
	cout << "The queue back:" << queue.back() << endl;
	//队列size
	cout << "The queue size:" << queue.size() << endl;
	//出队操作
	queue.pop();
	queue.pop();
	queue.pop();
	queue.pop();
	cout << "----------------------------" << endl;
	cout << "Four times pop() After:" << endl;
	//队首元素
	cout << "The queue front:" << queue.front() << endl;
	//队尾元素
	cout << "The queue back:" << queue.back() << endl;
	//队列size
	cout << "The queue size:" << queue.size() << endl;
 
	//system("pause");
	return 0;
}

运行结果：

Four times push() After:
The queue front:1
The queue back:4
The queue size:4
----------------------------
Four times pop() After:
error front(),empty queue!
The queue front:260750304
error back(),empty queue!
The queue back:260750304
The queue size:0
请按任意键继续. . .

2）C/C++代码实现

队列的队头位于栈2的栈顶

只要栈2不空，那就返回栈2的栈顶元素

如果栈2为空，那就把栈1中的所有元素全部压入栈2中，再取栈顶

#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;
template<class T>
class Queue
{
	public:
		// 入队列
		void push(const T&data){
			stack1.push(data);
		}

		// 出队列
		T&Pop()
		{
			T head;
			//如果两个栈都是空栈，此时说明队列是空的
			if (stack1.empty() && stack2.empty())
				cout << "this queue is empty" << endl;
			//如果栈2中有元素，那出队列就出栈2中的
			if (!stack2.empty()){
				head = stack2.top();
				stack2.pop();
			}
			//此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元
			//素入栈到栈2中,注意一定要是栈1中的所有元素都入栈到栈2中
			else{
				while (stack1.size() > 0){
					stack2.push(stack1.top());
					stack1.pop();
				}
				head = stack2.top();
				stack2.pop();
			}
			return head;
		}

		// 获取队头元素，此时队头位于栈2的栈顶
		T&Front()
		{
			assert(!stack1.empty() || !stack2.empty());
			if (stack2.empty()){
				while (!stack1.empty()){
					stack2.push(stack1.top());		// top()
					stack1.pop();					// pop()
				}
			}
			return stack2.top();
		}
		
	private:
		stack<T> stack1;
		stack<T> stack2;
};

// 测试数据
void TestQueue()
{
	Queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	cout <<"队头为:>  "<< q.Pop() << endl;
	cout << "队头为:>  " << q.Pop() << endl;
}

// 主函数
int main()
{
	TestQueue();
	system("pause");
	return 0;
}

3）Java 代码实现

算法分析：

栈结构的特点是先进后出，队列结构的特点是先进先出。

对于一个无序整数序列，使用两个栈，经过进栈->出栈->进栈->出栈两次栈操作，刚好可以得到原始无序整数序列，如下图所示。

解题思路：

初始化两个栈StackPush和StackPop，前者仅负责入栈操作，后者仅负责出栈操作。

需要注意，元素从StackPush压入StackPop中存在两个条件：

a. StackPop非空时，禁止压入元素，防止元素顺序先进先出混乱

b. 必须一次性全部压入，否则一旦积压，最终的出栈顺序将被打乱。

代码实现：

/*
 * DESC:
 * A class implements a queue using two stacks
*/ 

public class StackQueue {
    private Stack<Integer> stackPush;
    private Stack<INteger> stackPop;
    public StackQueue() {
        this.stackPush = new Stack<Integer>();
        this.stackPop = new Stack<Integer>();
    }

    private void pushToStackPop() {
        if (this.stackPop.IsEmpty()) {
            while (!this.stackPush.IsEmpty())
                this.stackPop.push(this.stackPush.pop());
        }
    }

    // Add element to queue.
    // When adding elelment to StackPush, need to judge whether it's necessary to add it to stackPop simultaneously
    public void add( int element) {
        this.stackPush.push(element);
        pushToStackPop();
    }

    // Remove a element from queue
    public int poll() {
        if (this.StackPush.IsEmpty() && this.StackPop.IsEmpty())
            throw new RuntimeException('Queue is empty.');
        pushToStackPop();
        return this.stackPop.pop();
    }

    // Get the header element of queue
    public int peek() {
        if (this.StackPush.IsEmpty() && this.StackPop.IsEmpty())
            throw new RuntimeException('Queue is empty.');
        pushToStackPop();
        return this.stackPop.peek();    
    }
}

6、时间复杂度

入队操作的时间复杂度显然是O(1)。

出队操作，如果涉及到栈A和栈B的元素迁移，时间复杂度是O(n)，如果不用元素迁移，时间复杂度是O(1)。

总结

两个栈实现一个队列，实际上是用到了 "负负得正"、"敌人的敌人就是朋友"、"否定之否定就是肯定"的哲学思想

两个栈实现一个列队，核心的关键算法是：栈A入队，栈B出队，当栈B为空时一次性把栈A元素全部压入栈B

本文参考：两个栈实现一个队列（CSDN）

参考推荐：

八大排序算法图文讲解

LeetCode 622. 设计循环队列

LeetCode 19. 删除链表的倒数第 N 个结点

LeetCode 543. 二叉树的直径 (任意两结点最长距离)