C語言實現使用靜態數組實現循環隊列的操作

C語言實現使用靜態數組實現循環隊列的操作

隊列是一種先進先出的的數據結構，我們同樣可以使用數組、鏈表等來實現。我們可以在隊列的尾部進行插入元素，在隊列的頭部取出元素。普通的隊列由於空間利用率不高，所以我們一般都用循環隊列。循環隊列中最重要的的兩個操作就是判斷是否為空和是否已滿。當head==tail時，表示隊列為空。當(tail+1)%MAX_SIZE == head，表示隊列已滿。

我判斷隊滿的方法：犧牲一個單元來區分對空和隊滿，入隊時少用一個隊列單元，相當於浪費一個存儲空間。“隊頭指針的隊尾指針的下一位置作為隊滿的標志”。代碼上傳至：https://github.com/chenyufeng1991/Queue_Array 。

（1）進隊列

//進隊列
void EnQueue(int value){

    //要先判斷隊列是否已滿
    if ((tail + 1) % QUEUE_SIZE == head) {
        printf("隊列已滿，無法從隊尾插入元素\n");
    }else{

        queue[tail] = value;
        tail = (tail + 1) % QUEUE_SIZE;
    }
}

//出隊列
int DeQueue(){

    int temp;
    if (tail == head) {
        printf("隊列為空，元素無法出隊列\n");
    }else{

        temp = queue[head];
        head = (head + 1) % QUEUE_SIZE;
    }

    printf("%d\n",temp);
    return temp;
}

//判斷隊列是否為空
int IsEmpty(){
    if (head == tail) {
        printf("隊列為空\n");
        return 1;
    }

    printf("隊列不為空\n");
    return 0;
}

//判斷隊列是否已滿
/**
 *  我這裡判斷隊滿的的方法：
 犧牲一個單元來區分隊空和隊滿，入隊時少用一個隊列單元。如果數組的大小為Size,那麼實際只能存放(Size-1)個元素。（這是比較常用的判滿的方式）
 *
 */
int IsFull(){

    if ((tail + 1) % QUEUE_SIZE == head) {
        printf("隊列已滿\n");
        return 1;
    }

    printf("隊列未滿\n");
    return 0;
}

//打印出隊列元素
void PrintQueue(){

    for (int i = head; i < tail; i++) {
        printf("%d ",queue[i]);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {

    EnQueue(4);EnQueue(1);EnQueue(2);EnQueue(9);EnQueue(8);
    PrintQueue();

    DeQueue();DeQueue();
    PrintQueue();
    
    return 0;
}