Queue and CircularQueue in C++ ; )

Queue,就是佇列 (廢話),

Queue具有以下特性:

1. 具有FIFO性質
2. 插入與刪除在不同端

下圖為Queue之操作模式:

加入資料一律在尾端，取出資料一律在頭端，

則可達到上述兩種特性。


Queue的應用:

1. 正常的Queue

2. Priority Queue

   ->插入任意優先權的工作
   ->刪除最大或最小權值之工作

3. Double-ended Priority Queue

   ->插入隨意權值
   ->可刪除最大最小權值

4. OS中的排班法則、日常排隊、BFS (廣度優先)


而一般的Queue會有一些空間上的問題，

顯示Queue已滿，但是其實並沒有滿，

雖然有解，但是假如有n個資料就要搬動n次。


而 CircularQueue 可以解決此問題。

CircularQueue如下圖所示，長得很像甜甜圈。

特色:

插入與刪除計算複雜度為 big-O (1)

操作判斷與Queue相似

缺點:這種傳統的 CircularQueue 只可利用 n-1格。

下面為使用Array實作 CircularQueue  (某家公司在面試時考出來!)

初始化: Font 與 Rear 開始位置為 N-1

插入第一筆資料後

所以:

 接著加入b c d 後

再繼續加入則會顯示已滿!

會先做Front與Rear=(Rear+1)mod SIZE是否為同一格的檢查，

假如為同一格則Rear往後退一格(Rear=Rear-1)(先前進作檢查，已滿則後退)

而假如Front與Rear=(Rear+1)mod SIZE為同一格，而Front又為0時，

這時假如做(Rear=Rear-1)會發生 Real為-1，所以在這種狀況下

要指定位置為SIZE-1。

刪除資料:

Front已經變0了。(我現在才發現有些英文字打錯了.......反正看得懂就好對吧!)

接下來就自己根據程式碼追追看了喔。

ps. 讀取資料那邊會這樣設計是有原因的，

之前一直有錯誤，想了一會才改成現在的樣子!






=======CQ.h=======

#ifndef CQ_H
#define CQ_H
#include <iostream>

class CQ
{
private:
    int Font;
    int Rear;
public:
    CQ();
    ~CQ();
    void Add();
    void List();
    void Delete();
    char *Arr;
    int MAX;
};

#endif

=======CQ.cpp=======

#include "CQ.h"
using namespace std;
CQ::CQ(){
    cout<<"請輸入CircularQueue大小"<<endl;
    cin>>MAX;
    Font=MAX-1;
    Rear=MAX-1;
    Arr=new char[MAX];
}

CQ::~CQ(){
    delete []Arr;
}

void CQ::Add(){
    Rear=(Rear+1)%MAX;
    if(Rear==Font){
        if(Rear==0){
            Rear=MAX-1;
        }else{
            Rear=Rear-1;
        }
        cout<<"CircularQueue已滿!!"<<endl;
        
    }else{
        cout<<"請輸入資料"<<endl;
        cin>>Arr[Rear];
    }
}

void CQ::Delete(){
    if(Rear==Font){
        cout<<"CircularQueue為空!!"<<endl;
    }else{
        Font=(Font+1)%MAX;
        cout<<"刪除的資料為:"<<Arr[Font]<<endl;
    }
}

void CQ::List(){
    if(Rear==Font){
        cout<<"CircularQueue為空!!"<<endl;
    }else{
        cout<<"Font="<<Font<<endl;
        cout<<"Rear="<<Rear<<endl;
        for(int i=(Font+1)%MAX;i!=(Rear+1)%MAX;i=++i%MAX){
        cout<<"第"<<i<<"格資料為:"<<Arr[i]<<endl;
        }
    }
    
    
}

=======main=======

#include <iostream>
#include "CQ.h"

using namespace std;
int main()
{
    char option;
    CQ cq;
    while(1){
        cout<<"======"<<endl;
        cout<<"1.插入"<<endl;
        cout<<"2.刪除"<<endl;
        cout<<"3.顯示"<<endl;
        cout<<"4.結束"<<endl;
        while(cin.get(option)&&option=='\n');
        switch(option){
            case '1':cq.Add();
                break;
            case '2':cq.Delete();
                break;
            case '3':cq.List();
                break;
            case '4':cout<<"程式結束"<<endl;
                     system("PAUSE");
                return 0;
        }
    }
}

By Victor