循環(huán)隊列的實現(xiàn)

   隊列的一個非常重要的特點就是：只允許在隊列的頭部進行刪除操作，只允許在隊列的尾部進行插入操作。

   所以，很明顯，隊列這種結構需要兩個指針，一個指針指向隊列的頭部，一個指針指向隊列的尾部。既然隊列這種結構也是用來存放數(shù)據(jù)的，當有一個數(shù)據(jù)存入隊列中時，指向尾部的指針就向后加1，當刪除一個元素時，頭指針就向后加1，由于我們定義當隊列為空時，指向頭部的指針和指向尾部的指針重合，所以，當刪除到剩余最后一個元素時，頭指針front和尾指針rear就重合了，這樣會和我們定義的隊列為空兩指針重合相矛盾。所以，我們要做的就是，將尾指針rear指向隊列尾部的下一個位置。這樣，問題就解決了。

   如果有數(shù)據(jù)插入，我們可以將rear+1，當數(shù)據(jù)不需要而要將其刪除時，我們將front+1,直到rear指向隊列尾部的下一個位置，已經(jīng)沒有位置可以放新的元素了，那么此時隊列真的已經(jīng)滿了嗎？當然沒有，因為刪除一個元素時，front++，所以，在front前面還有位置可以放元素，所以此時，這種虛假的隊列滿的情況，稱之為“假溢出”。

   那么如何解決這個假溢出的現(xiàn)象呢？當然有辦法，就是通過循環(huán)隊列，當rear指針指向最后一個位置時，就將它置為0，指向隊列頭部。那假設我們有了一個循環(huán)隊列，當rear向后自增，又從0開始接著向后自增，直到和front重合時，隊列滿。這樣一來，我們又帶來一個問題，我們怎么判斷rear==front到底是隊列為空還是隊列是滿的呢？解決的辦法就是空出一個單元，不存放任何數(shù)據(jù)，也就是當rear+1 == front時，就意味著滿隊列了。所以，判斷滿隊列的條件就是:

( reat + 1 ) % QueueSize == front;

此時，就認為是滿隊列狀態(tài)。

   那么我該如何計算隊列的長度呢？因為rear有可能比front大也有可能比front小，我該如何確定隊列的元素個數(shù)呢？第一種情況，rear > front。此時，只要將rear - front就可以計算出隊列的長度了。

由圖所示，圖中有2個元素，a3和a4。所以，我們要計算隊列長度，只需將rear-front，就可以得出結果了。第二種情況，rear < front。如圖所示：

當碰到這種出現(xiàn)假溢出形式的時候，我們該如何計算隊列的長度呢？很明顯，此時，隊列長度的計算分為兩段，一段是front之后的元素，一段是rear之前的元素，計算A3和A4這兩個元素，我們只需(QueueSize - front)這樣以來，就算出來了，此時QueueSize的值為5，那么(5 - 3 )的值為2，所以，第一段元素的長度為2，第二段元素長度，只需要(0 + rear ) 就可以了，也就是(0 + 2 ),此時值為2，所以，隊列真正的長度就為(2 + 2 = 4 ), 那么隊列的長度就計算出來了。

因為有兩種情況，所以，為了實現(xiàn)通用，就有一個標準的計算隊列長度的公式：

( rear - front + QueueSize ) % QueueSize

   接下來，就來定義一個循環(huán)隊列的結構：

typedef int QElemType;

typedef struct{

    QElemType data[MAXSIZE];
    int front;
    int  rear;
}SqQueue;

如果要初始化一個隊列，我們該如何做呢？

Status InitQueue ( SqQueue *Q ){

    Q->front = 0;
    Q->rear = 0;
    
    return OK;
}

求循環(huán)隊列的長度

int QueueLength ( SqQueue Q ){

    return ( Q.rear - Q.front + MAXSIZE ) % MAXSIZE;

}

循環(huán)隊列元素的插入

Status EnQueue ( SqQueue *Q, QElemType e ){

    if ( ( Q->rear + 1 ) % MAXSIZE == front )
        return ERROR;
    
    Q->data[Q->rear] = e;
    Q->rear = ( Q->rear + 1 ) % MAXSIZE;
    
    return OK; 

}

循環(huán)隊列元素的刪除

Status DeQueue ( SqQueue *Q, QElemType *e ){

    if ( Q->rear == Q->front )
        return ERROR;
        
    *e = Q->data[Q->front];
    Q->front = ( Q->front + 1 ) % MAXSIZE;
    
    return OK;

}