C++如何實現(xiàn)兩個棧和一個隊列

這篇文章給大家分享的是有關(guān)C++如何實現(xiàn)兩個棧和一個隊列的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

C++ 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)兩個棧實現(xiàn)一個隊列

棧為后進先出，隊列為先進先出

    用兩個棧實現(xiàn)一個隊列。是一個比較經(jīng)典的問題。

看到這個問題，我的第一個解題思路為：

          定義兩個棧，s1,s2。s1作為入隊列棧，s2作為出隊列棧；

                入隊列：每次入隊列的時候，將數(shù)值壓入s1棧中；

                出隊列：出隊列時，將s1中的所有數(shù)據(jù)，壓進s2棧中，然后刪除s2的棧頂數(shù)據(jù)，然后再將s2中的剩余數(shù)據(jù)壓入s1中。

在這其中s1是一個存儲空間，s2是一個輔助空間。

   進一步想一下上述辦法，在出隊列時，每一次都要將s1倒進s2，然后刪除s2棧頂后又將s2的數(shù)據(jù)倒入s1;有另一個思路可以減少倒的次數(shù)；

    入隊列時：將數(shù)據(jù)壓進s1;

    出隊列時：判斷如果s2為空，那么將s1中的數(shù)據(jù)，壓進s2中，然后刪除s2棧頂，如果s2不為空那么再刪除s2的棧頂即可；

并且還可以優(yōu)化，優(yōu)化如下：

           出隊列時，判斷如果s2為空，那么將s1中n-1個數(shù)據(jù)，壓進s2中，然后刪除s1中的棧頂，如果s2不為空那么直接刪除s2的棧頂即可；

優(yōu)化版的c++實現(xiàn)如下：

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

感謝各位的閱讀！關(guān)于“C++如何實現(xiàn)兩個棧和一個隊列”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！