日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

1. .隊列的概念和實現(xiàn)

1.1.隊列的概念

隊列是一種特殊的線性表，僅能在線性表的兩端進行操作。

成都創(chuàng)新互聯(lián)公司成都網(wǎng)站建設(shè)按需網(wǎng)站制作，是成都網(wǎng)站建設(shè)公司,為紗窗提供網(wǎng)站建設(shè)服務(wù),有成熟的網(wǎng)站定制合作流程，提供網(wǎng)站定制設(shè)計服務(wù)：原型圖制作、網(wǎng)站創(chuàng)意設(shè)計、前端HTML5制作、后臺程序開發(fā)等。成都網(wǎng)站改版熱線：028-86922220

• -隊頭（front）取出數(shù)據(jù)元素的一端；
• -隊尾（rear）插入數(shù)據(jù)元素的一端。
  隊列的特性：
  
  隊列的常用操作：
  創(chuàng)建和銷毀；出隊和入隊；清空隊列；獲取隊首元素；獲取隊列長度
  
  隊列聲明（接口）：

  template < typename T >
  class Queue
  {
  public:
  virtual void enqueue(const T& e) = 0;
  virtual void dequeue() = 0;
  virtual T front() const = 0;
  virtual void clear() = 0;
  virtual int length() const = 0;
  };

  1.2.StaticQueu

  順序隊列的實現(xiàn)：
  
  設(shè)計要點：
  類模板，使用原生數(shù)組作為隊列 存儲空間，使用模板參數(shù)決定隊列的大容量；

  template < typename T, int N >
  class StaticQueue : public Queue
  {
  protected:
  T m_space[N];
  int m_front;
  int m_rear;
  int m_length;
  public:
  StaticQueue()
  void enqueue(const T& e)
  void dequeue()
  T front() const
  void clear()
  int length() const
  int capacity() const
  };

  注意事項:
  StaticQueue實現(xiàn)要點：（循環(huán)計數(shù)法） 提高隊列操作的效率（本質(zhì)上時循環(huán)隊列）
  關(guān)鍵操作：

• 入隊：m_rear = (m_rear + 1) % N;
• 出隊：m_front = (m_front + 1) % N;
  隊列狀態(tài)：
• 隊空：(m_length == 0) && (m_front == m_rear)

• 隊滿：(m_length == N) && (m_front == m_rear)
  StaticQueue最終實現(xiàn)：

  template < typename T, int N >
  class StaticQueue : public Queue
  {
  protected:
  T m_space[N];
  int m_front;
  int m_rear;
  int m_length;
  public:
  StaticQueue()   //O(1)
  {
      m_front = 0;
      m_rear = 0;
      m_length = 0;
  }
  
  void enqueue(const T& e)   //O(1)
  {
      if(m_length < N)
      {
          m_space[m_rear] = e;
          m_rear = (m_rear + 1) % N;
          m_length++;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "no space in current staticqueue...");
      }
  }
  
  void dequeue()   //O(1)
  {
      if(m_length > 0)
      {
          m_front = (m_front + 1) % N;
          m_length--;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "no element in current staticqueue...");
      }
  }
  
  T front() const   //O(1)
  {
      if(m_length > 0)
      {
          return m_space[m_front];
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "no element in current staticqueue...");
      }
  }
  
  void clear()   //O(1)
  {
      m_front = 0;
      m_rear = 0;
      m_length = 0;
  }
  
  int length() const   //O(1)
  {
      return  m_length;
  }
  
  int capacity() const   //O(1)
  {
      return N;
  }
  
  bool is_empty()   //O(1)
  {
      return (m_length == 0) && (m_front == m_rear);
  }
  
  bool is_full()   //O(1)
  {
      return (m_length == N) && (m_front == m_rear);
  }
  };

  2.鏈式隊列

  2.1.LinkQueue

  順序隊列的缺陷：當數(shù)據(jù)為類類型時，StaticQueue的對象在創(chuàng)建時，會多次調(diào)用元素類型的構(gòu)造函數(shù)，影響效率。所以我們采用鏈式存儲結(jié)構(gòu)來實現(xiàn)隊列。
  
  設(shè)計要點：
  1.類模板，繼承自抽象父類Queue;
  2.在內(nèi)部使用鏈式結(jié)構(gòu)實現(xiàn)元素的存儲
  3.只在鏈表的頭部和尾部進行操作。
  
  LinkQueue聲明：

  template 
  class LinkQueue : public Queue
  {
  protected:
  LinkList m_list;
  public:
  LinkQueue(){}
  void enqueue(const T& e)    //O(n)
  void dequeue()      //O(1)
  T front() const //O(1)
  void clear()        //O(n)
  int length() const  //O(1)
  };

  LinkQueue最終實現(xiàn)：

  template 
  class LinkQueue : public Queue
  {
  protected:
  LinkList m_list;
  public:
  LinkQueue(){}
  
  void enqueue(const T& e)    //O(n)
  {
      m_list.insert(e);
  }
  
  void dequeue()      //O(1)
  {
      if(m_list.length() > 0)
      {
          m_list.remove(0);
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "no elemet in current LinkQueue...");
      }
  }
  
  T front() const //O(1)
  {
      if(m_list.length() > 0)
      {
          return m_list.get(0);
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "no elemet in current LinkQueue...");
      }
  }
  
  void clear()        //O(n)
  {
     while (m_list.length() > 0)
      {
          m_list.remove(0);
      }
  }
  
  int length() const  //O(1)
  {
      return m_list.length();
  }
  };

  LinkQueue中，入隊操作由于只能操作隊列的尾部（鏈表的最后位置），要進行遍歷操作，所以時間復(fù)雜度為O(n)，可以使用雙向循環(huán)鏈表代替單鏈表來解決這個問題。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

當前標題：數(shù)據(jù)結(jié)構(gòu)(07)_隊列-創(chuàng)新互聯(lián)
分享地址：http://www.dlmjj.cn/article/dgpdoj.html