双栈队列的原理是用两个栈结构模拟一个队列, 一个栈A模拟队尾, 入队的元素全部压入此栈, 另一个栈B模拟队首, 出队时将栈A的元素弹入栈B, 将栈B的栈顶元素弹出
此结构类似汉诺塔, 非常经典, 这里附上C++代码简单实现, 有问题欢迎指出
#include <stack> template <typename T>
class CStkQueue
{
public:
T queuePop(); //出队列
void queuePush(T value); //入队列
size_t queueSize(); //队列长度
bool queueEmpty(); //队列判空 private:
std::stack<T> std_stack_push; //入栈,模拟队尾
std::stack<T> std_stack_pop; //出栈,模拟队首
}; template <typename T>
T CStkQueue<T>::queuePop()
{
T temp; //返回值 //如果出栈不为空,直接将出栈的栈顶元素弹出
if (!std_stack_pop.empty())
{
temp = std_stack_pop.top();
std_stack_pop.pop();
return temp;
} //将入栈元素弹出并压进出栈至仅剩一个元素
while (std_stack_push.size() != )
{
std_stack_pop.push(std_stack_push.top());
std_stack_push.pop();
} //将入栈仅有的一个元素作为返回值弹出
temp = std_stack_push.top();
std_stack_push.pop();
return temp;
} template <typename T>
void CStkQueue<T>::queuePush(T value)
{
//如果出栈不为空,先将出栈元素弹回入栈
while (!std_stack_pop.empty())
{
std_stack_push.push(std_stack_pop.top());
std_stack_pop.pop();
} //元素压栈
std_stack_push.push(value);
} template <typename T>
size_t CStkQueue<T>::queueSize()
{
return (std_stack_push.size() + std_stack_pop.size());
} template <typename T>
bool CStkQueue<T>::queueEmpty()
{
return ((std_stack_push.size() + std_stack_pop.size()) == ) ? true : false;
}
下面做个简单的测试
结果如下