c语言实现顺序队列和链队列

在C语言中，实现顺序队列和链队列主要涉及数据结构的知识。

**顺序队列（Array Queue）**:
顺序队列通常使用数组作为底层存储，它通过两个指针，一个指向队头（front），一个指向队尾（rear），来进行插入和删除操作。当队尾满时，需要创建一个新的更大的数组；当队头为空时，表示队列为空。以下是基本操作的伪代码：

typedef struct {
    int capacity;
    int size;
    int* array;
} Queue;

// 初始化空队列
Queue init_queue(int capacity) {
    Queue q = {capacity, 0, (int*)malloc(capacity * sizeof(int))};
    return q;
}

// 入队
void enqueue(Queue* q, int value) {
    if (q->size == q->capacity) {
        // 队满，扩大容量
        q->array = realloc(q->array, 2 * q->capacity);
    }
    q->array[q->size++] = value;
}

// 出队
int dequeue(Queue* q) {
    if (q->size == 0) {
        // 队空，返回错误
        return -1;
    }
    int value = q->array[0];
    q->array[0] = q->array[--q->size]; // 移动元素到队首
    return value;
}

**链队列（Linked List Queue）**:
链队列使用节点（Node）结构，每个节点包含数据和指向下一个节点的指针。队头和队尾分别指向第一个节点和最后一个节点。插入和删除操作更为高效，因为无需移动大量元素。以下是链队列的基本实现：

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

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

// 初始化空链队列
Queue init_linked_queue() {
    Queue q = {NULL, NULL};
    return q;
}

// 入队
void enqueue(Queue* q, int value) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = q->rear;
    q->rear = newNode;
    if (q->front == NULL) {
        q->front = newNode;
    }
}

// 出队
int dequeue(Queue* q) {
    if (q->front == NULL) {
        // 队空，返回错误
        return -1;
    }
    int value = q->front->data;
    Node* temp = q->front;
    q->front = q->front->next;
    free(temp); // 释放已删除节点
    return value;
}