C語言隊列探究

一、隊列的基本概念

隊列是一種線性數據結構，它具有FIFO的特點，即先進先出。相比於棧，隊列需要維護兩個指針，一個指向隊頭，一個指向隊尾，隊頭指向隊列中第一個入隊的元素，隊尾指向隊列中的最後一個入隊的元素。隊尾和隊頭從隊列兩端對元素進行操作：

    typedef struct{
        int data[MAXSIZE];
        int front;
        int rear;
    }Queue;

其中MAXSIZE代表隊列中可以存放元素的最大數量，front和rear分別代表隊列的隊頭和隊尾，初始值均為0。

二、隊列的實現方式

1、順序隊列

順序隊列的實現方式是利用數組來存儲隊列中的元素，並利用兩個指針front和rear分別指向隊頭和隊尾的位置。隊列的入隊操作是在rear位置插入元素，出隊操作是在front位置取出元素。但是順序隊列也存在一些問題，如元素入隊後，front位置不會改變，所以出現了假溢出的情況，而這樣會浪費很大的空間。解決假溢出的方法是將元素移動到數組的前端，並將front和rear同時減小移動的元素個數。

    void Enqueue(Queue *q, int element){
        if(q->rear == MAXSIZE){
            printf("隊列已滿\n");
            return;
        }
        q->data[q->rear++] = element;
    }
    int Dequeue(Queue *q){
        if(q->front == q->rear){
            printf("隊列已空\n");
            return -1;
        }
        return q->data[q->front++];
    }

2、鏈式隊列

鏈式隊列的實現方式是利用指針來構建出隊列，而不是像順序隊列一樣用數組來存儲。鏈式隊列將隊列中的每個元素用一個結構體來表示，其中每個結構體中有一個指針指向下一個元素。其入隊和出隊操作就是在鏈表的末尾插入元素和在鏈表的頭部刪除元素。

    typedef struct node{
        int data;
        struct node *next;
    }Node;
     
    typedef struct{
        Node *front;
        Node *rear;
    }Queue;
     
     
    void Enqueue(Queue *q, int element){
        Node *newnode = (Node*)malloc(sizeof(Node));
        newnode->data = element;
        newnode->next = NULL;
        if(q->rear == NULL){
            q->front = q->rear = newnode;
        }
        else{
            q->rear->next = newnode;
            q->rear = newnode;
        }
    }
     
    int Dequeue(Queue *q){
        if(q->front == NULL){
            printf("隊列已空\n");
            return -1;
        }
        int data = q->front->data;
        Node *temp = q->front;
        q->front = q->front->next;
        free(temp);
        if(q->front == NULL){
            q->rear = NULL;
        }
        return data;
    }

三、隊列的應用場景

隊列可以用於多種場景，如操作系統進程調度中的進程隊列、計算機網路中的消息傳遞和緩存隊列等。下面以操作系統中的進程調度為例，解釋隊列在操作系統中的應用：

操作系統中，有多個進程在運行，需要通過調度程序來實現進程的切換和調度。為了保證進程按照一定規則進行調度，通常會把所有進程都加入到等待隊列中，調度程序從等待隊列中按照一定的優先順序和調度演算法來選擇下一個進程來運行。

    typedef struct{
        int pid;  //進程ID
        int priority;   //進程優先順序
        int burst_time; //進程運行時間
    }Process;
     
    Queue queue;
     
    int main(){
        int i;
        Process p[5] = {
            {1, 3, 24},
            {2, 1, 3},
            {3, 4, 4},
            {4, 2, 1},
            {5, 5, 8}
        };
        InitQueue(&queue);
        for(i=0; i 0){
                current.burst_time--;
                Enqueue(&queue, current);
            }
        }
        return 0;
    }

四、隊列的總結

隊列是解決問題的一種有效數據結構，在多種應用場景下都有廣泛的應用。從隊列的基本概念出發，探究了隊列的兩種實現方式，順序隊列和鏈式隊列。最後以操作系統中的進程調度為例，進一步闡述了隊列的應用場景。了解了隊列的概念和應用，我們可以更加深入地理解C語言這門編程語言。