隊列和迴圈隊列的實現

隊列

定義：隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端（head）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

按照隊列的定義，結合記憶體地址的理解，初始化隊列的時候，準備head和rear指針分別指向頭和尾。Push操作，只需要改變rear指針；PopLeft操作只需要改變head。由於是線性表結構，所以在封裝GetSize的時候，不能簡單的用rear-head，因為每次申請的結點都是記憶體中隨機的區域，正因如此，這種隊列鏈（線性表實現）更具有靈活性。

代碼實現

#include<iostream>
using namespace std;
typedef int DataType;

struct Queue{
    DataType data;
    Queue *next;
};

void InitQueue(Queue *&head,Queue *&rear){
    head = new Queue;
    head->next = NULL;
    rear = head;
}

void Push(Queue *&rear,DataType data){
    Queue *q = new Queue;
    q->data = data;
    q->next = NULL;
    rear->next = q;
    rear = q;
}
void PopLeft(Queue *&head,DataType &data){ //data 是彈出的數據 
    if(!head->next) //判斷是否是空的隊列 
        return ;
    else{
        Queue *q = head->next;  //保存No 1的隊列結點 
        delete head;
        head = q;
        data = q->data;
    }
}
int GetSize(Queue *head){
    if(!head->next) //head->next是NULL的時候，隊列為空 
        return 0;
    else{ //迭代計算長度 
        int length= 0;
        Queue *tem = head->next ;
        while(tem){
            ++length;
            tem = tem->next;
        }
        return length;
    }
}
void DeleteQueue(Queue *&head){
    Queue *p = head; //當前要刪除的結點 
    Queue *q = p->next;
    while(q){
        delete p;
        p = q;
        q = p->next;
    }
    delete p;
}

int main(){
    Queue *head=NULL,*rear = NULL;
    DataType data ;     //用來保存彈出的元素 
    
    InitQueue(head,rear);
    
    Push(rear,-1);
    Push(rear,-2);
    Push(rear,100);
    Push(rear,-100);
    
    cout<<"長度是："<<GetSize(head)<<endl;
    
    PopLeft(head,data);
    cout<<"彈出元素："<<data<<endl;
    PopLeft(head,data);
    cout<<"彈出元素："<<data<<endl;
    
    DeleteQueue(head);
    //cout<<"長度是："<<GetSize(head)<<endl; 無法執行，說明DeleQueue成功 
    return 0;
}

迴圈隊列

定義：為充分利用向量空間，剋服"假溢出"現象的方法是：將向量空間想象為一個首尾相接的圓環，並稱這種向量為迴圈向量。存儲在其中的隊列稱為迴圈隊列（Circular Queue）。

雖然可以剋服假溢出，但是迴圈隊列長度有限，並且記憶體中不可能有類似迴圈的物理結構。我們需要用邏輯來實現這種迴圈隊列。

如果採用一段連續地址進行實現，可以使用數組，實現簡單，不做實現；這裡是採用使用的連續指針進行實現。

需要準備base_front指針來記錄最初的頭位置。需要count和size分別存放隊列大小和隊列中的數據個數。迴圈的邏輯實現就是：在特定條件下，front 和 rear 都要重新指向save_front ，形成一個環。

#include<iostream>
using namespace std;

const int SIZE = 3; //預設隊列大小 
template <class T>  //為了適應各種數據類型，使用類模板 
class CirQueue {
    private:
        T *front;
        T *rear;
        T *save_front;
        int size;
        int count ; //記錄有多少個元素 
    public:
        CirQueue(){
            count = 0;
            size = SIZE;
            front = new T [size];
            save_front = rear  = front;
        }
        CirQueue(int s){
            count = 0;
            size = s;
            front = new T [size];
            save_front = rear = front;
        }
        int GetSize(){
            return size;
        }
        void Push(T data){
            if(count==size)
                return ; //隊列已滿 
            *rear = data;
            ++count;
            if (count==size)//只剩最後一個位置 
                rear = save_front; //完成邏輯上的迴圈 
            else
                ++rear; 
        }
        void PopLeft(T &data){
            if(!count) //如果沒有元素
                return;
            --count;
            data = *front;
            if(front-save_front==size-1)
                front = save_front;
            else
                ++front;
        }
        void Delete(){
            delete [] save_front;
            cout<<"刪除成功"<<endl;
        }
};
int main(){
    CirQueue <int> tem;
    int data;
    for(int i=0;i<4;++i)
        tem.Push(i+1); //1 2 3
    for(int i=0;i<tem.GetSize();++i){
        tem.PopLeft(data);
        cout<<data<<endl;
    }
    tem.Delete();
    return 0;
}

歡迎進一步交流本博文相關內容：

博客園地址 : http://www.cnblogs.com/AsuraDong/

CSDN地址 : http://blog.csdn.net/asuradong

也可以致信進行交流 : [email protected]

歡迎轉載 , 但請指明出處  :  )