C语言数据结构之队列的定义与实现

C语言数据结构之队列的定义与实现

什么是队列

队列是一种特殊的线性数据结构，它只允许在队列的头部进行删除操作，在队列的尾部进行插入操作，这种操作方式被成为“先进先出”或“FIFO(first in first out)”。

队列的实现方式

队列可以通过数组和链表两种方式进行实现。

1. 数组实现

数组实现队列时，可以定义一个存放元素的数组，同时需要记录队列的头部和尾部。队列头的位置表示下一次从队列中取出元素的位置，而队列尾的位置表示下一次插入元素的位置，代码实现如下：

#define MAX_QUEUE_SIZE 100     // 定义队列最大长度
typedef struct {
    int queue[MAX_QUEUE_SIZE];  // 存放元素的数组
    int front;                  // 队列头部位置
    int rear;                   // 队列尾部位置
} ArrayQueue;

// 初始化队列
void initQueue(ArrayQueue* queue) {
    queue->front = queue->rear = 0;
}

// 入队列
void enqueue(ArrayQueue* queue, int element) {
    if ((queue->rear + 1) % MAX_QUEUE_SIZE == queue->front) {
        printf("队列已满，无法插入元素");
        return;
    }
    queue->queue[queue->rear] = element;
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
}

// 出队列
int dequeue(ArrayQueue* queue) {
    if (queue->front == queue->rear) {
        printf("队列为空，无法取出元素");
        return -1;
    }
    int element = queue->queue[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    return element;
}

上述代码中，队列的最大长度是100，当队列满时需要进行数据搬移，代码中通过取模操作实现了循环队列的功能。

2. 链表实现

链表实现队列时，可以定义一个单链表，用链表的头结点表示队列的头部，而链表的尾结点表示队列的尾部，代码实现如下：

typedef struct LinkedNode {
    int data;                      // 链表节点存放的元素
    struct LinkedNode* next;       // 指向下一个节点的指针
} LinkedNode;

typedef struct {
    LinkedNode* front;        // 队列头部
    LinkedNode* rear;         // 队列尾部
} LinkQueue;

// 初始化队列
void initQueue(LinkQueue* queue) {
    queue->front = queue->rear = NULL;
}

// 入队列
void enqueue(LinkQueue* queue, int element) {
    LinkedNode* node = (LinkedNode*)malloc(sizeof(LinkedNode));
    node->data = element;
    node->next = NULL;
    if (queue->rear == NULL) {
        queue->front = queue->rear = node;
    } else {
        queue->rear->next = node;
        queue->rear = node;
    }
}

// 出队列
int dequeue(LinkQueue* queue) {
    if (queue->front == NULL) {
        printf("队列为空，无法取出元素");
        return -1;
    }
    LinkedNode* node = queue->front;
    int element = node->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(node);
    return element;
}

队列的应用

队列的应用场景非常广泛，例如：

1. 广度优先搜索算法

广度优先搜索算法就需要借助一个队列，将遍历的节点依次入队列，然后按照队列的顺序出队列，实现图的遍历。

void BFS(LinkedList* graph, int start) {
    Queue queue;
    int isVisited[MAX_VERTEX_NUM] = {0};
    insertQueue(&queue, start);
    isVisited[start] = 1;
    while (!isQueueEmpty(&queue)) {
        int current = deleteQueue(&queue);
        printf("%d ", current);
        LinkedListNode* node = graph->adjList[current].firstNode;
        while (node != NULL) {
            int vertex = node->vertex;
            if (!isVisited[vertex]) {
                insertQueue(&queue, vertex);
                isVisited[vertex] = 1;
            }
            node = node->next;
        }
    }
}

2. 操作系统中的进程调度

在操作系统中，进程调度通常是使用队列来实现的，将需要执行的进程按照优先级放入对应的队列中，然后按照队列的顺序依次调度执行。

// 定义进程
typedef struct {
    int pid;            // 进程ID
    int priority;       // 进程优先级
    int burst_time;     // 进程执行时间
} Process;

// 定义队列
typedef struct {
    Process* p[MAX_QUEUE_SIZE];
    int front;
    int rear;
} ProcessQueue;

// 入队列
void enqueueProcess(ProcessQueue* queue, Process* p) {
    if ((queue->rear + 1) % MAX_QUEUE_SIZE == queue->front) {
        printf("队列已满，无法插入进程");
        return;
    }
    queue->p[queue->rear] = p;
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
}

// 出队列
Process* dequeueProcess(ProcessQueue* queue) {
    if (queue->front == queue->rear) {
        printf("队列为空，无法取出进程");
        return NULL;
    }
    Process* p = queue->p[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    return p;
}