循環隊列-順序存儲-c語言實作

/*
    循環隊列-線性表-順序結構 
*/ 
#include<stdio.h>

#define OK 1;
#define ERROR 0;
#define MAXSIZE 20
typedef int QElemType;
typedef int Status;

//順序存儲結構
typedef struct {
    QElemType data[MAXSIZE];
    int front;  //頭指針 
    int rear;   //尾指針 
}sqQueue; 

//初始化隊列 front = rear 則隊列為null 
Status initQueue(sqQueue *q){
    q->front = ;
    q->rear = ;
    printf("隊列初始化成功 \n");
    return OK;
}

//求隊列的長度
Status queueLength(sqQueue q){
    return (q.rear - q.front + MAXSIZE) % MAXSIZE;
} 

//插入隊列 , 如果隊列沒有滿,插入元素e到q的隊尾元素
Status enQueue(sqQueue *s, QElemType e){
    //判斷隊列是否滿
    if((s->rear + ) % MAXSIZE == s->front){
        printf("隊列已經滿了無法插入 \n");
        return ERROR;
    } 
    s->data[s->rear] = e;
    s->rear = (s->rear + ) % MAXSIZE;  //隊尾指針後移 
    return OK;
} 

//出隊 删除隊頭元素 用e傳回删除的元素值
Status DeQueue(sqQueue *s, QElemType *e){
    //判斷隊列是否為null
    if(s->rear == s->front){
        printf("隊列為null 無法進行出隊 \n") ;
        return ERROR; 
    } 
    *e = s->data[s->front]; //儲存資料
    s->front = (s->front + ) % MAXSIZE;    // 隊頭指針後移
    return OK; 
} 

//周遊隊列
void queueTraverse(sqQueue q){
    //判斷隊列是否為null
    if(q.rear == q.front){
        printf("隊列為null 無法進行輸出 \n");
    } else{
        int i, length;
        length = queueLength(q);
        for(i = ; i < length; i++){
            printf("%d ", q.data[q.front]);
            q.front = (q.front + ) % MAXSIZE;
        }
        printf("\n");
    }
} 

int main(void){
    sqQueue q;
    QElemType e; 
    initQueue(&q);
    printf("\n 1.初始化隊列 \n 2.周遊隊列 \n 3.入隊 \n 4.出隊 \n 0.退出\n");
    int option = , value;
    while(option){
        scanf("%d",&option);
        switch(option){
            case :
                initQueue(&q);
                break;
            case :
                queueTraverse(q);
                break;
            case :
                printf("請輸入要入隊的資料\n");
                scanf("%d",&e);
                enQueue(&q, e); 
                queueTraverse(q);
                break;
            case :
                value = DeQueue(&q, &e);
                if(value){
                    printf("出隊的元素是:%d\n",e);
                } 
                break;
            case :
                return OK;
        }
    }   
    return OK;
} 
           

隊列: 先進先出型資料結構

循環隊列計算隊列長度: (rear - front + QueueSize) % QueueSize

隊列滿的條件是: (rear + 1) % QueueSize == front [ 需要數組保留一個元素空間 ]

隊列空的條件是: front = rear

順序存儲的優點和缺點:

• 時間上,入隊和出隊的操作都是常數,即O(1)
• 事先需要申請好空間,使用期間不釋放.
• 必須有一個固定的長度,也就有了存儲元素個數和空間浪費的問題

如果能确定隊列長度的最大值情況下, 建議使用循環隊列, 如果無法确定隊列的長度時, 用鍊隊列比較好.