C語言數據結構之隊列怎么定義與實現

C語言數據結構之隊列怎么定義與實現

1. 隊列的基本概念

隊列（Queue）是一種先進先出（FIFO, First In First Out）的線性數據結構。它只允許在表的一端進行插入操作，而在另一端進行刪除操作。隊列的這種特性使得它在很多場景中非常有用，比如任務調度、緩沖區管理等。

1.1 隊列的特點

• 先進先出：最先進入隊列的元素最先被移除。
• 操作受限：只能在隊尾插入元素，在隊頭刪除元素。
• 動態性：隊列的大小可以動態變化，通常不需要預先定義大小。

1.2 隊列的基本操作

• 入隊（Enqueue）：在隊列的尾部插入一個元素。
• 出隊（Dequeue）：從隊列的頭部刪除一個元素。
• 獲取隊頭元素（Front）：獲取隊列頭部的元素，但不刪除它。
• 獲取隊尾元素（Rear）：獲取隊列尾部的元素，但不刪除它。
• 判斷隊列是否為空（IsEmpty）：判斷隊列是否為空。
• 獲取隊列的大?。⊿ize）：獲取隊列中元素的個數。

2. 隊列的實現方式

隊列可以通過多種方式實現，常見的有數組實現和鏈表實現。下面我們將分別介紹這兩種實現方式。

2.1 數組實現隊列

數組實現隊列的方式相對簡單，但存在一個潛在的問題：當隊列的頭部元素被刪除后，數組的前部空間將無法被利用，導致空間浪費。為了解決這個問題，通常使用循環隊列的方式來實現。

2.1.1 循環隊列的定義

循環隊列是一種特殊的隊列，它通過將數組的首尾相連，形成一個環形結構。這樣，當隊列的頭部元素被刪除后，數組的前部空間可以被重新利用。

2.1.2 循環隊列的實現

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} CircularQueue;

// 初始化隊列
void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判斷隊列是否為空
bool isEmpty(CircularQueue *q) {
    return q->front == q->rear;
}

// 判斷隊列是否已滿
bool isFull(CircularQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入隊操作
bool enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return false;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

// 出隊操作
bool dequeue(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}

// 獲取隊頭元素
bool front(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->data[q->front];
    return true;
}

// 獲取隊尾元素
bool rear(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->data[(q->rear - 1 + MAX_SIZE) % MAX_SIZE];
    return true;
}

// 獲取隊列的大小
int size(CircularQueue *q) {
    return (q->rear - q->front + MAX_SIZE) % MAX_SIZE;
}

int main() {
    CircularQueue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    int value;
    front(&q, &value);
    printf("Front element: %d\n", value);

    rear(&q, &value);
    printf("Rear element: %d\n", value);

    printf("Queue size: %d\n", size(&q));

    dequeue(&q, &value);
    printf("Dequeued element: %d\n", value);

    front(&q, &value);
    printf("Front element: %d\n", value);

    printf("Queue size: %d\n", size(&q));

    return 0;
}

2.2 鏈表實現隊列

鏈表實現隊列的方式更加靈活，不需要預先定義隊列的大小，且不會出現空間浪費的問題。

2.2.1 鏈表隊列的定義

鏈表隊列通過鏈表節點來存儲數據，每個節點包含數據和指向下一個節點的指針。隊列的頭部指向鏈表的第一個節點，尾部指向鏈表的最后一個節點。

2.2.2 鏈表隊列的實現

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
} LinkedQueue;

// 初始化隊列
void initQueue(LinkedQueue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// 判斷隊列是否為空
bool isEmpty(LinkedQueue *q) {
    return q->front == NULL;
}

// 入隊操作
void enqueue(LinkedQueue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出隊操作
bool dequeue(LinkedQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }

    Node *temp = q->front;
    *value = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return true;
}

// 獲取隊頭元素
bool front(LinkedQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->front->data;
    return true;
}

// 獲取隊尾元素
bool rear(LinkedQueue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return false;
    }
    *value = q->rear->data;
    return true;
}

// 獲取隊列的大小
int size(LinkedQueue *q) {
    int count = 0;
    Node *current = q->front;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

int main() {
    LinkedQueue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    int value;
    front(&q, &value);
    printf("Front element: %d\n", value);

    rear(&q, &value);
    printf("Rear element: %d\n", value);

    printf("Queue size: %d\n", size(&q));

    dequeue(&q, &value);
    printf("Dequeued element: %d\n", value);

    front(&q, &value);
    printf("Front element: %d\n", value);

    printf("Queue size: %d\n", size(&q));

    return 0;
}

3. 隊列的應用場景

隊列在計算機科學中有廣泛的應用，以下是一些常見的應用場景：

3.1 任務調度

在操作系統中，任務調度通常使用隊列來實現。任務按照到達的順序進入隊列，調度器從隊列的頭部取出任務進行執行。

3.2 緩沖區管理

在網絡通信中，數據包的傳輸通常使用隊列作為緩沖區。數據包按照到達的順序進入隊列，接收端從隊列的頭部取出數據包進行處理。

3.3 廣度優先搜索（BFS）

在圖論中，廣度優先搜索算法使用隊列來存儲待訪問的節點。算法從起始節點開始，依次訪問其鄰接節點，并將這些節點加入隊列中，直到隊列為空。

3.4 打印隊列

在打印機管理中，打印任務通常使用隊列來管理。打印任務按照提交的順序進入隊列，打印機從隊列的頭部取出任務進行打印。

4. 總結

隊列是一種非常重要的數據結構，具有先進先出的特性。它可以通過數組或鏈表來實現，每種實現方式都有其優缺點。數組實現的隊列簡單高效，但存在空間浪費的問題；鏈表實現的隊列靈活且不會浪費空間，但需要額外的內存來存儲指針。

在實際應用中，隊列被廣泛用于任務調度、緩沖區管理、廣度優先搜索等場景。掌握隊列的定義與實現，對于理解和應用這些場景至關重要。

通過本文的學習，你應該已經掌握了如何在C語言中定義和實現隊列，并了解了隊列的基本操作和應用場景。希望這些知識能夠幫助你在編程實踐中更好地使用隊列這一數據結構。