剑指offer - 两个队列实现一个栈
题目
两个队列实现一个栈
思路1
两个队列queue1, queue2。不管是插入还是弹出，保证总有一个队列为空。
- 入栈操作：总是往有数据的列队插入，默认两个列队空，插入
queue1 - 出栈操作：从非空列队中删除数据并插入空列队，一直到非空列队剩下一个元素，该元素就是出栈的元素
分析：
1.png
如图所示，先往栈内压入一个元素a。由于两个队列现在都是空的，可以选择把a插入两个队列的任意一个。
不妨把a插入queue1。接下来继续往栈内压入b、c两个元素，把它们也都插入queue1。这个时候queue1包含3个元素a、b、c，其中a位于队列的头部、c位于队列的尾部
现在考虑从栈内弹出一个元素，根据栈的后入先出原则，最后被压入栈的c应该先弹出。由于c位于queue1的尾部，而每次只能从队列的头部删除元素，因此可以先从queue1中因此删除a、b并插入queue2，再从queue1中删除c。这就相当于从栈中弹出元素c了。可以使用同样的方法从栈内弹出元素b。
接下来再考虑往栈内压入一个元素d。此时queue1已经有一个元素，就把d插入queue1的尾部，如果再从栈内弹出一个元素，同样先从头删除queue1的元素并插入queue2，直到queue1遇到d再直接把它删除
算法实现
- 定义栈
template<typename T>
class QueueStack
{
public:
void push(const T& data);
T pop();
int size();
QueueStack()
{
count = 0;
}
private:
queue<T> q1;
queue<T> q2;
int count;
};
- Push操作
// 进栈
template<typename T>
void QueueStack<T>::push(const T& data)
{
if (q1.size()==0 && q2.size() ==0) // 默认情况下都为空，插入q1
{
q1.push(data);
}
else if (q1.size()>0) // q1非空插入q1
{
q1.push(data);
}
else if(q2.size()>0) // q2非空插入q2
{
q2.push(data);
}
++count; // 元素加1
}
- Pop操作
// 出栈
template<typename T>
T QueueStack<T>::pop()
{
if (q1.size()==0 && q2.size() ==0) // 列队为空，抛出异常
{
logic_error ex("stack is empty");
throw exception(ex);
}
T element;
if (q2.size() == 0) // q2为空
{
while(q1.size() != 1) // 遍历q1，将元素添加到q2，只留一个元素
{
q2.push(q1.front());
q1.pop();
}
element = q1.front(); // 即最后一个入列队的元素出栈
q1.pop(); // 删除元素
}
else
{
while(q2.size() != 1) // q2不为空，并且个数不止一个
{
q1.push(q2.front());
q2.pop();
}
element = q2.front();
q2.pop();
}
--count; // 元素减1
return element;
}
- 栈大小
template<typename T>
int QueueStack<T>::size()
{
return count;
}
简单使用
void test() {
QueueStack<string> stack;
stack.push("a");
stack.push("b");
stack.push("c");
cout<<"current size: "<<stack.size()<<endl; // 3
cout<<stack.pop()<<endl; // c
cout<<"current size: "<<stack.size()<<endl; // 2
cout<<stack.pop()<<endl; // b
stack.push("d");
cout<<"current size: "<<stack.size()<<endl; // 2
cout<<stack.pop()<<endl; // d
}
思路2
两个队列queue1, queue2。不管是插入还是弹出，保证总有一个队列为空。
-
队列入栈：将元素插入空队列，同时将非空队列的元素依次插入到空队列。此时之前的非空队列变为空队列，空队列变为非空队列。
-
队列出栈：将非空队列的队首弹出即可。
分析：
执行下述操作：先将1、2、3入栈，接着3出栈，然后4入栈。两个队列元素的变化情况如下：
1、 初始情况下：queue1 , queue2都为空，先将1压入queue1。此时queue1为非空，queue2为空。
2、元素2入栈 ，因为queue2为空所以压入。之前queue1非空，将1弹出压入queue2。此时queue1为空 queue2为2 、1。
3、元素3入栈 ，queue1为空所以压入。之前queue2非空，将2、1依次弹出压入queue1。此时queue2为空 ，queue1为3、2、1。
4、元素3出栈 queue1非空 3出栈。queue1为2 1 queue2为空。
5、元素4入栈 queue2为空所以压入。之前queue1非空，将2、1依次弹出压入queue2。此时queue1为空 queue2为4、2、1。
说白了就是将插入的数据直接排好序，后插入的数据在列队的头部，先插入的数据在列队尾部
算法实现
- 定义栈
#include <iostream>
#include <queue>
#include <exception>
using namespace std;
class QueueStack {
public:
void push(int x);
void pop();
int top();
bool empty();
unsigned long size();
private:
queue<int> q1;
queue<int> q2;
};
- Push操作
// 保证每个时刻都有一个队列为空队列
void QueueStack:: push(int x) {
if (q1.empty()) // 列队1为空
{
q1.push(x); // 向列队1插入元素
while (!q2.empty()) // 队列2不为空
{
q1.push(q2.front()); // 获取队列2的首元素添加到队列1
q2.pop(); // 去除队列首元素
}
}
else // 列队1不为空
{
q2.push(x); // 将元素t入队列2
while (!q1.empty()) // 同理在队列1不为空的情况下，将队列1的元素添加到队列2
{
q2.push(q1.front());
q1.pop();
}
}
}
- Pop操作
// 从栈顶去除元素
void QueueStack:: pop() {
if (empty()) { // 为空抛出异常
logic_error ex("stack is empty");
throw exception(ex);
}
if (q1.empty()) {
q2.pop();
}
else
{
q1.pop();
}
}
- Top操作
// 获取顶部元素
int QueueStack:: top() {
if (empty()) {
logic_error ex("stack is empty");
throw exception(ex);
}
if (q1.empty()) {
return q2.front();
}
else
{
return q1.front();
}
}
- Empty、栈数量操作
// 是否为空
bool QueueStack:: empty() {
return q1.empty() && q2.empty();
}
// 个数
unsigned long QueueStack:: size() {
return q1.size() + q2.size();
}
简单使用
void test() {
QueueStack stack;
stack.push(1);
stack.push(2);
stack.push(3);
cout<<"current size: "<<stack.size()<<endl; // 3
cout<<stack.top()<<endl; // 3
stack.pop(); // 去除元素3
cout<<"current size: "<<stack.size()<<endl; // 2
cout<<stack.top()<<endl; // 2
stack.pop(); // 去除元素2
stack.pop(); // 去除元素1
cout<<"is empty: "<<stack.empty()<<endl; // 1
}
参考
《剑指offer》
利用两个队列实现一个栈(C++版)
