一、文章来由
一道面试题,别说以前还真没好好想过,在未参考其他资料情况下自己想了两种,实现如下,如果另有高招,之后再补。
二、2种实现方式
分析:栈操作其实只有 push 和 pop 对栈内元素进行改变,我于是想从其一下手即可。
改变 push 操作:
比如输入,1 2 3 4 5,栈中结构应该是1在底,5在顶,但是队中元素是原顺序,如果要让push一个元素,让队列中的顺序反过来,就可以每推入一个元素,就用另一个队列中转把次序调整过来。
/*
*
* function: 用两个栈实现队列
*
* Date:2016-03-15
*
* Author: Bill Wang
*/
#include <iostream>
#include <queue>
using namespace std;
template <class T>
class whStack
{
public:
whStack(){}
~whStack(){}
void push(T t);
T pop();
private:
std::queue<T> QueueA;
std::queue<T> QueueB;
};
template<class T> void whStack<T>::push(T t) {
//将另一个队列作为中转站
//step1、将A队列所有元素推入B
while ( !QueueA.empty() ) {
T tmp = QueueA.front();
QueueA.pop();
QueueB.push(tmp);
}
//step2、推入新节点
QueueA.push(t);
//step3、将B队列回归A
while ( !QueueB.empty() ) {
T tmp = QueueB.front();
QueueB.pop();
QueueA.push(tmp);
}
}
//pop时直接弹出并返回T
template<class T> T whStack<T>::pop() {
T res = QueueA.front();
QueueA.pop();
return res;
}
int main()
{
whStack<int > s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
return 0;
}
这个输出:
5
4
3
但是这样相当于把另一个队列纯做中转,时间复杂度较高。
改变 pop 操作:
/*
*
* function: 用两个栈实现队列2
*
* Date:2016-03-15
*
* Author: Bill Wang
*/
#include <iostream>
#include <queue>
using namespace std;
template <class T>
class whStack
{
public:
whStack(){}
~whStack(){}
void push(T t);
T pop();
private:
std::queue<T> QueueA;
std::queue<T> QueueB;
};
template<class T> void whStack<T>::push(T t) {
//判断哪一个队列非空
if( !QueueA.empty() )
QueueA.push(t);
else
QueueB.push(t);
}
//pop时直接弹出并返回T
template<class T> T whStack<T>::pop() {
std::queue<T> &qa = QueueA.empty()? QueueB:QueueA;
std::queue<T> &qb = QueueA.empty()? QueueA:QueueB;
//将队尾最后一个元素留住,将其他元素入另一个队列
T tmp;
while (1) {
tmp = qa.front();
qa.pop();
if( qa.empty() )
break;
qb.push(tmp);
}
return tmp;
}
int main()
{
whStack<int > s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
cout<<s.pop()<<endl;
return 0;
}
同样输出:
5
4
3
三、复杂度分析
从源码可以看出,如果队列元素个数为n,他们的如果执行一对push和pop,都可以在线性时间 O(n),得出结果。
但是明显,第一种方法是将元素移进移出两次,一个队列始终为空,严格来说复杂度是 O(2n);第二种方法是两个队列轮流使用,省去一轮遍历,所以相较之下应该是 O(n),所以第二种更快一些。