首页 > 代码库 > 使用两个队列实现一个栈
使用两个队列实现一个栈
先普及小知识：
STL 中栈的使用方法(stack) 基本操作：
push(x) 将x加入栈中，即入栈操作
pop() 出栈操作(删除栈顶)，只是出栈，没有返回值
top() 返回第一个元素(栈顶元素)
size() 返回栈中的元素个数
empty() 当栈为空时，返回 true
STL 中队列的使用(queue)
基本操作：
push(x) 将x压入队列的末端
pop() 弹出队列的第一个元素(队顶元素)，注意此函数并不返回任何值
front() 返回第一个元素(队顶元素)
back() 返回最后被压入的元素(队尾元素)
empty() 当队列为空时，返回true
size() 返回队列的长度
这个栈的声明如下：
template<typenameT>
classStack_by_queue
{
public:
Stack_by_queue(){};
~Stack_by_queue(){};
voidappend_tail(constT& node);
T delete_head();
voidShow_Stack(void);//从栈顶依次向栈低显示输出数据
protected:
private:
queue<T> queue1;
queue<T> queue2;
};分析：栈的特性是先进后出，举一个序列1,2,3,4来说，我们试着往一个queue1里面push进去，这时候queue1的队头是1，队尾是4，这时候要实现delete_head的话，对应的栈应该删除4，对于queue1的队尾，前面的1,2,3，都是不需要的。实现dalete_head解决方法就是，依次弹出1,2,3并且压入queue2中，queue1里面只保存4，这时候要delete_head的话，对queue1进行pop操作就行了，然后queue1为空（注意这个状态）,然后我要继续delete_head,这个时候也是按照上面的思路，将queue2的1,2依次弹出，压入queue1里面，知道剩下最后一个队尾元素3，将它pop掉就行了！这时候的状态是queue1不为空，queue2为空。实现append_tail的话也容易。注意上面的删除头以后的两种状态其实可以可以归结为一种，那就是其中一个queue为空，另一个可以为空（这个时候模拟的stack就是空），或者不为空，append_tail来说，只需往非空的queue里面添到队尾就行了，若是都为空，随便选一个即可。
#include <queue>
#include <iostream>
usingnamespace std;
template<typenameT>
classStack_by_queue
{
public:
Stack_by_queue(){};
~Stack_by_queue(){};
voidappend_tail(constT& node);
T delete_head();
voidShow_Stack(void);
private:
queue<T> queue1;
queue<T> queue2;
};
template<typenameT>
voidStack_by_queue<T>::Show_Stack(void)
{
queue<T> Q1(queue1);
queue<T> Q2(queue2);
T tmp;
cout<<"\n this is Show_Stack!从栈顶到栈底显示数据\n";
while(!Q1.empty() || !Q2.empty())
{
if(Q1.empty() && !Q2.empty())
{
//2->1
if(Q2.size() < 1)
{
return;
}
while(Q2.size() != 1)
{
tmp = Q2.front();
Q2.pop();
Q1.push(tmp);
}
cout<<Q2.front()<<" ";
Q2.pop();
}
if(!Q1.empty() && Q2.empty())
{
//1->2
if(Q1.size() < 1)
{
return;
}
while(Q1.size() != 1)
{
tmp = Q1.front();
Q1.pop();
Q2.push(tmp);
}
cout<<Q1.front()<<" ";
Q1.pop();
}
}
}
//保证在所有的过程中，至少队列有一个是空的
template<typenameT>
T Stack_by_queue<T>::delete_head()
{
T tmp;
if(queue1.empty() && !queue2.empty())
{
//2->1
if(queue2.size() < 1)
{
return-1;
}
while(queue2.size() != 1)
{
tmp = queue2.front();
queue2.pop();
queue1.push(tmp);
}
tmp = queue2.front();
queue2.pop();
returntmp;
}
if(!queue1.empty() && queue2.empty())
{
//1->2
T tmp;
if(queue1.size() < 1)
{
return-1;
}
while(queue1.size() != 1)
{
tmp = queue1.front();
queue1.pop();
queue2.push(tmp);
}
tmp = queue1.front();
queue1.pop();
returntmp;
}
else
return-1;
}
template<typenameT>
voidStack_by_queue<T>::append_tail(constT& node )
{
//保证有一队列为空，若全为空，则队空,任选一个队列就行
if(queue1.empty() && !queue2.empty())
queue2.push(node);
if(!queue1.empty() && queue2.empty())
queue1.push(node);
if(queue1.empty() && queue2.empty())
queue1.push(node);
else
return;
}
int main()
{
Stack_by_queue<char> my_stack;
my_stack.append_tail('a');
my_stack.append_tail('b');
my_stack.append_tail('c');
my_stack.Show_Stack();
my_stack.delete_head();
my_stack.delete_head();
my_stack.Show_Stack();
my_stack.append_tail('d');
my_stack.append_tail('e');
my_stack.Show_Stack();
my_stack.delete_head();
my_stack.Show_Stack();
my_stack.append_tail('f');
my_stack.Show_Stack();
}
/**************************
运行结果：
this is Show_Stack!从栈顶到栈底显示数据
c b a
this is Show_Stack!从栈顶到栈底显示数据
a
this is Show_Stack!从栈顶到栈底显示数据
e d a
this is Show_Stack!从栈顶到栈底显示数据
d a
this is Show_Stack!从栈顶到栈底显示数据
f d a
***************************/