大話資料結構 －－ 循環隊列

//
//  main.cpp
//  循環隊列
//
//  Created by Maggie on 18/8/21.
//  Copyright © 2018年 Maggie. All rights reserved.
//

#include <iostream>
using namespace std;

#define MAXSIZE 100

typedef int QElemType;

// 循環隊列的順序存儲結構
typedef struct
{
    QElemType data[MAXSIZE];
    // 頭指針，指向隊列首元素
    int front;
    // 尾指針，若隊列不為空，指向隊列尾元素的下一個位置
    int rear;
}SqQueue;

// 初始化一個空隊列Q
void InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
}

// 傳回隊列長度
int QueueLength(SqQueue Q){
    //rear-front &MAXSIZE-front+rear
    return (Q.rear-Q.front+MAXSIZE) % MAXSIZE;
}

// 若隊列未滿，則插入元素e為Q新的隊尾元素
int EnQueue(SqQueue *Q, QElemType e){
    // 隊列滿的判斷
    if((Q->rear+1)%MAXSIZE==Q->front)
        return MAXSIZE;
    // 将元素e賦給隊尾
    Q->data[Q->rear]=e;
    //注意，不是Q->rear++
    Q->rear=(Q->rear+1) %MAXSIZE;
    // 若到最後則轉到數組頭部
    return Q->rear;
}

// 若隊列不空，則删除Q中隊頭元素，用e傳回其值。
int DeQueue(SqQueue *Q){
    // 隊列空的判斷
    if(Q->rear==Q->front)
        return -1;
    //将隊頭元素指派給e
    int e=Q->data[Q->front];
    //font指針向後移一位置
    Q->front=(Q->front+1) % MAXSIZE;
    // 若到最後則轉到數組頭部
    return e;
}


int main(void){
    SqQueue Q;
    InitQueue(&Q);
    int a= EnQueue(&Q, 1);
    int b=EnQueue(&Q, 2);
    int c=EnQueue(&Q, 3);
    int l1=QueueLength(Q);
    int d=DeQueue(&Q);
    int l2=QueueLength(Q);
    cout<<a<<endl;
    cout<<b<<endl;
    cout<<c<<endl;
    cout<<l1<<endl;
    cout<<d<<endl;
    cout<<l2<<endl;
    return 0;
}
           

1、循環隊列是為了解決順序結構隊列的假溢出問題，鍊隊列無需考慮；

2、當隊列空時，條件就是front=rear，當隊列滿時，我們修改其條件，保留一個元素空間。也就是說，隊列滿時，數組中還有一個空閑單元；由于rear可能比front大，也可能比front小，是以盡管它們隻相差一個位置時就是滿的情況，但也可能是相差整整一圈。是以若隊列的最大尺寸為QueueSize，那麼隊列滿的條件是(rear+1)%QueueSize==front（取模“%”的目的就是為了整合rear與front大小為一個問題）；

3、當rear>front時，隊列的長度為rear-front。但當rear<front時，隊列長度分為兩段，一段是QueueSize-front，另一段是0+rear，加在一起，隊列長度為rear-front+QueueSize。是以通用的計算隊列長度公式為：

(rear-front+QueueSize)%QueueSize