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

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

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

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

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

用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。是一個(gè)比較經(jīng)典的問(wèn)題。

看到這個(gè)問(wèn)題，我的第一個(gè)解題思路為：

定義兩個(gè)棧，s1,s2。s1作為入隊(duì)列棧，s2作為出隊(duì)列棧；

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

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

在這其中s1是一個(gè)存儲(chǔ)空間，s2是一個(gè)輔助空間。

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

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

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

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

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

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

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

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

您可能感興趣的文章: