C++ 数据结构实现两个栈实现一个队列

C++ 数据结构实现两个栈实现一个队列

栈为后进先出，队列为先进先出

    用两个栈实现一个队列。是一个比较经典的问题。

看到这个问题，我的第一个解题思路为：

          定义两个栈，s1,s2。s1作为入队列栈，s2作为出队列栈；

                入队列：每次入队列的时候，将数值压入s1栈中；

                出队列：出队列时，将s1中的所有数据，压进s2栈中，然后删除s2的栈顶数据，然后再将s2中的剩余数据压入s1中。

在这其中s1是一个存储空间，s2是一个辅助空间。

   进一步想一下上述办法，在出队列时，每一次都要将s1倒进s2，然后删除s2栈顶后又将s2的数据倒入s1;有另一个思路可以减少倒的次数；

    入队列时：将数据压进s1;

    出队列时：判断如果s2为空，那么将s1中的数据，压进s2中，然后删除s2栈顶，如果s2不为空那么再删除s2的栈顶即可；

并且还可以优化，优化如下：

           出队列时，判断如果s2为空，那么将s1中n-1个数据，压进s2中，然后删除s1中的栈顶，如果s2不为空那么直接删除s2的栈顶即可；

优化版的c++实现如下：

#include<iostream>
using namespace std;
#include<stack>
//栈 后进先出 队列 先进先出
template<class T>
class Queue
{
public:

  /*T Pop_back()
  {
    if (s2.size() <= 0)
    {
      while(s1.size() > 0)
      {
        T& temp = s1.top();
        s1.pop();
        s2.push(temp);
      }
    }
    if (s2.size() == 0)
      throw new exception("queue is empty ");

    T tep = s2.top();
    s2.pop();
    return tep;
  }*/

  T Pop_back() //比上面少一次出栈
  {
    if (s2.size() <= 0)
    {
      while (s1.size() > 1)
      {
        T& temp = s1.top();
        s1.pop();
        s2.push(temp);
      }
      T tep = s1.top();
      s1.pop();
      return tep;
    }
    else{
      T tep = s2.top();
      s2.pop();
      return tep;
    }
  }

    void Push_back(const T& value)
  {
    s1.push(value);
  }

    bool Empty()
    {
      return (s1.empty() && s2.empty());
    }

protected:
  stack<T> s1;
  stack<T> s2;
};

void TextQueue()
{
  Queue<int> q1;
  q1.Push_back(1);
  q1.Push_back(2);
  q1.Push_back(3);
  q1.Push_back(4);

  cout << q1.Pop_back() << endl;
  cout << q1.Pop_back() << endl;
  cout << q1.Pop_back() << endl;
  cout << q1.Pop_back() << endl;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

原文链接：http://blog.csdn.net/he_shuai20/article/details/62892260