题目描述： 使用两个栈实现一个队列

数据结构： 栈

• 思 路： 队列的特点是先进先出，所以两个栈，Stack1主要负责入栈，也就是队列中的元素，

  Stack2负责出栈，也就是出队列中的元素。
  

1. 对于进队列：

   1》如果Stack1为空，则直接进栈，相当于进队列;
   2》如果Stack1不为空，则入队列元素也是直接入栈;
     入队列其实是元素的直接Push,主要是要满足先进的先出即可。
   

1. 对于出队列：

   1》如果Stack2为空，则将Stack1中的元素全部倒入Stack2中（stack1的元素全部pop
   到stack2中），如果Stack2不为空，则直接出栈，相当于出队列;
   

• 问题小结： 对于Stack1到Stack2的倒入，每执行一次push都可以Pop到stack2中，但是思考到算法的效率，所以描述如上。

  template
  class Stack
  {
  public:

  Stack()
      :_array(NULL)
      , _size(0)
      , _capacity(0)
  {}
  Stack(const Stack<T>& s)
  {
      _array = new T[s._size];
      //memcpy(_array, array, sizeof(T)*s._size);
      for (size_t i = 0; i < s._size; ++i)
      {
          _array[i] = s._array[i];
      }
      _size = s._size;
      _capacity = s._size;
  }
  
  ~Stack()
  {
      if (_array)
      {
          delete[] _array;
      }
  }
  

  public:

  void Push(const T& x)      // Push an element in stack;
  {
      _CheckCapacity();
      _array[_size++] = x;
  }
  T& Pop()             // Pop an element out of stack;
  {
      if (_array)
      {
          return _array[--_size];
      }
      else
      {
          delete[] _array;
          _array = NULL;
      }
  }
  void Print()
  {
      if (_array)
      {
          cout << "依照进顺序:";
          for (size_t i = 0; i < _size; ++i)
          {
              cout << " " << _array[i];
          }
      }
  }
  
  size_t Size()
  {
      return _size;
  }
  
  size_t Capacity()
  {
      return _capacity;
  }
  
  bool Empty()
  {
      return _size == 0;
  }
  

  protected:

  void _CheckCapacity()
  {
      if (_size >= _capacity)
      {
          _capacity = _capacity * 2 + 3;
          T* tmp = new T[_capacity];
          if (_array)
          {
              for (size_t i = 0; i < _size; ++i)
              {
                  tmp[i] = _array[i];
              }
              delete[] _array;
          }
          _array = tmp;
      }
  }
  

  private:

  T* _array;
  size_t _size;
  size_t _capacity;
  

  };

  template
  class Queue
  {
  public:

  Queue()      //不能省
  {}
  Queue(const Stack<T>& S1,const Stack<int>& S2)
      :s1(S1)
      , s2(S2)
  {}
  ~Queue()
  {}
  

  public:

  void Inqueue(const T& x)
  {
      s1.Push(x);
      ////1m 2k; 1k 2k
      //if (s2.Empty())
      //{
      //    s1.Push(x);
      //}
      ////1kong 2 man
      ////1,2 man
      //if (!s2.Empty())
      //{
      //    for (size_t i = 0; i < s2.Size(); ++i)
      //    {
      //        s1.Push(s2.Pop());
      //    }
      //    s1.Push(x);
      //}
  }
  T& Outqueue()
  {
      if (s1.Empty() && s2.Empty())
      {
          cout << "没有元素" << endl;
      }
      if (!s2.Empty())
      {
          return s2.Pop();
      }
      if (s2.Empty())
      {
          for (size_t i = s1.Size() - 1 ; i >= 1; --i)
          {
              s2.Push(s1.Pop());
          }
          return s1.Pop();
      }    
  }
  void Print()
  {
      s1.Print();
      s2.Print();
      cout << endl;
  }
  

  private:

  Stack<T> s1;
  Stack<T> s2;
  

  };

  //测试用例
  void test1()
  {

  Queue<int> q;
  q.Inqueue(1);
  q.Inqueue(2);
  q.Inqueue(3);
  q.Inqueue(4);
  q.Inqueue(5);
  q.Inqueue(6);
  q.Print();
  
  cout << q.Outqueue() << endl;
  cout << q.Outqueue() << endl;
  cout << q.Outqueue() << endl;
  q.Inqueue(7);
  q.Inqueue(8);
  q.Inqueue(9);
  q.Print();
  q.Inqueue(10);
  q.Print();
  cout << q.Outqueue() << endl;
  q.Print();
  

  }

  void test2()
  {

  Queue<string> q;
  q.Inqueue("x1");
  q.Inqueue("x2");
  q.Inqueue("x333333333333333333333333333");
  q.Inqueue("x4");
  q.Inqueue("x5");
  q.Inqueue("x7");
  q.Inqueue("x8");
  q.Inqueue("x9");
  q.Inqueue("x10");
  q.Inqueue("x11");
  q.Print();
  

  }