C++如何實(shí)現(xiàn)循環(huán)順序隊(duì)列

這篇文章主要介紹了C++如何實(shí)現(xiàn)循環(huán)順序隊(duì)列，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

數(shù)據(jù)結(jié)構(gòu)–用C++實(shí)現(xiàn)循環(huán)順序隊(duì)列

• 隊(duì)列的操作特性：先進(jìn)先出

• 隊(duì)列中元素具有相同類(lèi)型

• 相鄰元素具有前驅(qū)和后繼關(guān)系

• 設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指針，以改進(jìn)出隊(duì)的時(shí)間性能
  

約定：隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素

為了解決假溢出，我們將存儲(chǔ)隊(duì)列的數(shù)組頭尾相接，從而產(chǎn)生了循環(huán)隊(duì)列。

如何判斷循環(huán)隊(duì)列隊(duì)空？

隊(duì)空：front=rear

如何盤(pán)對(duì)循環(huán)隊(duì)列堆滿(mǎn)？

隊(duì)滿(mǎn)：front=rear

那么問(wèn)題就來(lái)了，隊(duì)空和隊(duì)滿(mǎn)的判斷條件相同，為了避免隊(duì)滿(mǎn)時(shí)產(chǎn)生隊(duì)空的判斷或者相反，我們需要修改隊(duì)滿(mǎn)條件使得隊(duì)空和堆滿(mǎn)的判定條件分開(kāi)。
方法：浪費(fèi)一個(gè)元素空間，隊(duì)滿(mǎn)時(shí)數(shù)組只有一個(gè)空閑單元。隊(duì)滿(mǎn)條件：(rear+1)%QueueSize==front

下面是實(shí)現(xiàn)代碼：

文件CirQueue.h

#ifndef CirQueue_byNim
#define CirQueue_byNim

#include<iostream>
using namespace std;

const int QueueSize=100;  //循環(huán)隊(duì)列的最大存儲(chǔ)空間 
template <class T>
class CirQueue
{
  private:
    T *data;  //存儲(chǔ)數(shù)據(jù)的數(shù)組 
    int front,rear; //隊(duì)頭隊(duì)尾指針 
  public:
    CirQueue()
    {
      data=new T[QueueSize];
      front=rear=0;
    }
    ~CirQueue()
    {
      delete []data;
      front=rear=0;
    }
    void EnQueue(T e)
    {
      if((rear+1)%QueueSize==front)  //隊(duì)滿(mǎn)條件 
        throw "上溢";
      rear=(rear+1)%QueueSize;
      data[rear]=e;
    }
    T DeQueue()
    {
      if(rear==front)//隊(duì)空條件 
        throw "下溢";
      front=(front+1)%QueueSize;
      return data[front];
    }
    T GetQueue()
    {
      if(rear==front)//隊(duì)空條件 
        throw "下溢";
      return data[(front+1)%QueueSize];
    }
    bool empty()
    {
      if(front==rear) //隊(duì)空條件：front==rear 
        return true;
      return false;
    }
};

#endif

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“C++如何實(shí)現(xiàn)循環(huán)順序隊(duì)列”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!