數(shù)據(jù)結(jié)構(gòu)（九）——隊列

一、隊列簡介

隊列是一種特殊的線性表，僅能在兩端進(jìn)行操作，隊頭可以進(jìn)行區(qū)數(shù)據(jù)操作，隊尾進(jìn)行插入數(shù)據(jù)操作。
隊列的特性是先進(jìn)先出。

隊列的操作包括創(chuàng)建隊列、銷毀隊列、入隊、出隊、清空隊列、獲取隊頭元素、獲取隊列的長度。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名申請、雅安服務(wù)器托管、營銷軟件、網(wǎng)站建設(shè)、敖漢網(wǎng)站維護(hù)、網(wǎng)站推廣。

二、隊列的實現(xiàn)

1、隊列的抽象類

 template <typename T>
  class Queue:public Object
  {
  public:
    virtual void add(const T& value) = 0;//進(jìn)隊列
    virtual void remove() = 0;//出隊列
    virtual T front()const = 0;//獲取隊頭元素
    virtual void clear() = 0;//清空隊列
    virtual int length()const = 0;//隊列長度
  };

2、隊列的順序存儲結(jié)構(gòu)實現(xiàn)

隊列可以使用順序存儲結(jié)構(gòu)的內(nèi)存空間實現(xiàn)，其內(nèi)存空間分布如下：

根據(jù)存儲空間的分配方式可以分為使用原生數(shù)組實現(xiàn)的靜態(tài)隊列和使用動態(tài)分配的堆空間實現(xiàn)的動態(tài)隊列。
靜態(tài)隊列的實現(xiàn)要點如下：
A、類模板實現(xiàn)
B、使用原生數(shù)組作為隊列的存儲空間
C、使用模板參數(shù)決定隊列的容量大小
靜態(tài)隊列的實現(xiàn)如下：

template <typename T, int N>
  class StaticQueue:public Queue<T>
  {
  protected:
    T m_space[N];//隊列存儲空間，N為模板參數(shù)
    int m_front;//隊頭標(biāo)識
    int m_rear;//隊尾標(biāo)識
    int m_length;//隊列長度
  public:
    StaticQueue()
    {
      m_front = 0;
      m_rear = 0;
      m_length = 0;
    }

    int capacity()const
    {
      return N;
    }

    void add(const T &value)//入隊
    {
      if(m_length < N)
      {
          m_space[m_rear] = value;
          m_rear = (m_rear + 1) % N;
          m_length++;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");
      }
    }

    void remove()//出隊
    {
      if(m_length > 0)
      {
          m_front = (m_front + 1) % N;
          m_length--;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }

    T front() const//取隊頭元素
    {
      if(m_length > 0)
      {
          return m_space[m_front];
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }
   void clear()//清空隊列
   {
     m_length = 0;
     m_front = 0;
     m_rear = 0;
   }

   int length() const
   {
     return m_length;
   }
   bool isEmpty()const
   {
     return (m_length == 0) && (m_front == m_rear);
   }

   bool isFull()const
   {
     return (m_length == N) && (m_front == m_rear);
   }
  };

靜態(tài)隊列的缺陷：
當(dāng)存儲的元素類型為類類型時，創(chuàng)建靜態(tài)隊列時會多次調(diào)用元素類型的類構(gòu)造函數(shù)，影響效率。

3、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)

隊列使用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的內(nèi)容空間分布如下：

鏈?zhǔn)疥犃械膶崿F(xiàn)要點：
A、類模板實現(xiàn)，繼承自抽象父類Queue
B、內(nèi)部使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)元素的存儲
C、只在鏈表的頭部和尾部進(jìn)行操作
鏈?zhǔn)疥犃械膶崿F(xiàn)：

 template <typename T>
  class LinkedQueue:public Queue<T>
  {
  protected:
    LinkedList<T> m_list;
  public:
    LinkedQueue()
    {
    }
    void add(const T& value)//入隊
    {
      m_list.insert(value);
    }

    void remove()//出隊
    {
      if(m_list.length() > 0)
         m_list.remove(0);
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");
      }
    }
    T front()const//獲取隊頭元素
    {
      if(m_list.length() > 0)
         return m_list.get(0);
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No elemnet...");
      }
    }

    void clear()//清空隊列
    {
      m_list.clear();
    }

    int length() const
    {
      return m_list.length();
    }
  };

三、棧和隊列的相互實現(xiàn)

1、棧實現(xiàn)隊列

用棧實現(xiàn)隊列，用棧的后進(jìn)先出的特性實現(xiàn)隊列的先進(jìn)先出的特性。
用棧實現(xiàn)隊列需要使用兩個棧，解決方案如下：

新元素入隊時，將元素壓入stack_in棧，

template <typename T>
class StackToQueue:public Queue<T>
{
protected:
  mutable LinkedStack<T> m_stack_in;
  mutable LinkedStack<T> m_stack_out;
public:
  void add(const T& value)//入隊
  {
    m_stack_in.push(value);
  }
  void remove()//出隊
  {
    //出棧為空，則將入棧的所有元素壓入出棧并彈出入棧的元素
    if(m_stack_out.size() == 0)
    {
       while(m_stack_in.size() > 0)
        {
            m_stack_out.push(m_stack_in.top());
            m_stack_in.pop();//彈出入棧的元素
        }
    }
    //出棧不為空，將出棧棧頂元素彈出
    if(m_stack_out.size() > 0)
    {
        m_stack_out.pop();
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }
  T front() const
  {
    if(m_stack_out.size() == 0)
    {
       while(m_stack_in.size() > 0)
        {
            m_stack_out.push(m_stack_in.top());
            m_stack_in.pop();
        }
    }
    //彈出出棧棧頂元素
    if(m_stack_out.size() > 0)
    {
        return m_stack_out.top();
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  void clear()
  {
     m_stack_in.clear();
     m_stack_out.clear();
  }

  int length()const
  {
     return m_stack_in.size() + m_stack_out.size();
  }
};

2、隊列實現(xiàn)棧

用隊列實現(xiàn)棧，用隊列的先進(jìn)先出的特性實現(xiàn)棧的后進(jìn)先出的特性。
用隊列實現(xiàn)棧需要使用兩個隊列，解決方案如下：

template <typename T>
class QueueToStack:public Stack<T>
{
protected:
  LinkedQueue<T> m_queue1;
  LinkedQueue<T> m_queue2;
  LinkedQueue<T>* m_pIn;//入隊列
  LinkedQueue<T>* m_pOut;//出隊列
  //將入隊列前n-1個元素移動到出隊列
  void move()const
  {
    int n = m_pIn->length() - 1;
    for(int i = 0; i < n; i++)
    {
        m_pOut->add(m_pIn->front());
        m_pIn->remove();//從入隊列出隊
    }
  }
  //交換
  void swap()
  {
    LinkedQueue<T>* temp = NULL;
    temp = m_pIn;
    m_pIn = m_pOut;
    m_pOut = temp;
  }
public:
  QueueToStack()
  {
    m_pIn = &m_queue1;
    m_pOut = &m_queue2;
  }
  //壓棧
  void push(const T& value)
  {
    m_pIn->add(value);//將元素入隊列
  }
  void pop()//出棧
  {
    if(m_pIn->length() > 0)
    {
        move();//移動前n-1個元素
        m_pIn->remove();//將入隊列的最后一個元素出隊
        swap();//交換
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  void clear()
  {
    m_queue1.clear();
    m_queue2.clear();
  }

  T top() const
  {
    if(m_pIn->length() > 0)
    {
        move();//移動
        return m_pIn->front();
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  int size()const
  {
    return m_queue1.length() + m_queue2.length();
  }
};

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

當(dāng)前名稱：數(shù)據(jù)結(jié)構(gòu)（九）——隊列-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://vcdvsql.cn/article16/csihgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、網(wǎng)站營銷、移動網(wǎng)站建設(shè)、搜索引擎優(yōu)化、企業(yè)建站、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)