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

更新時間：2017年03月18日 08:40:11 投稿：lqh

這篇文章主要介紹了詳解C++ 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)兩個棧實現(xiàn)一個隊列的相關(guān)資料,需要的朋友可以參考下

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

棧為后進(jìn)先出，隊列為先進(jìn)先出

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

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

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

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

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

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

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

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

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

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

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

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

#include<iostream> 
using namespace std; 
#include<stack> 
//棧 后進(jìn)先出 隊列 先進(jìn)先出 
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; 
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: