求索阁

双栈队列的原理是用两个栈结构模拟一个队列, 一个栈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() != 1)
  {
    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()) == 0) ? true : false;
}