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; 
} 

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