博客

C语言用指针支持队列

  • Post category:C

C语言可以利用指针来实现队列的数据结构。队列是一种先进先出（FIFO）的数据结构，它的基本操作有入队（Enqueue）和出队（Dequeue）。

队列的定义

结构体定义：

typedef struct {
    int* arr;   // 队列存储空间
    int front;  // 头指针
    int rear;   // 尾指针
    int size;   // 队列长度
} Queue;

队列的初始化

初始化一个队列需要确定队列的最大长度，即队列可容纳的元素个数，以及队列中数据类型的大小。

void init_queue(Queue* q, int size) {
    q->front = 0;
    q->rear = -1;
    q->size = size;
    q->arr = (int*)malloc(size * sizeof(int));
}

入队操作

入队操作需要将元素插入队列尾部，并更新尾指针。

int enqueue(Queue* q, int data) {
    if (q->rear >= q->size - 1) {
        printf("Queue is full.\n");
        return -1;
    }

    q->arr[++q->rear] = data;
    return 0;
}

出队操作

出队操作需要删除队列头部元素，并更新头指针。

int dequeue(Queue* q, int* data) {
    if (q->front > q->rear) {
        printf("Queue is empty.\n");
        return -1;
    }

    *data = q->arr[q->front++];
    return 0;
}

队列的使用示例

示例1：使用队列实现打印杨辉三角

#include <stdio.h>

int main() {
    Queue queue;
    int size = 10;
    init_queue(&queue, size);

    enqueue(&queue, 1);
    for (int i = 0; i < size; i++) {
        int data, last = 0;
        for (int j = 0; j <= i; j++) {
            dequeue(&queue, &data);
            printf("%d ", data);
            enqueue(&queue, data + last);
            last = data;
        }
        printf("\n");
    }

    free(queue.arr);
    return 0;
}

示例2：使用队列实现逆序输出

#include <stdio.h>

int main() {
    Queue queue;
    int size = 5;
    init_queue(&queue, size);

    for (int i = 0; i < size; i++) {
        int data;
        scanf("%d", &data);
        enqueue(&queue, data);
    }

    for (int i = 0; i < size; i++) {
        int data;
        dequeue(&queue, &data);
        printf("%d ", data);
    }

    free(queue.arr);
    return 0;
}

以上是使用指针实现队列的方法，通过这种方法能够更加有效的避免了数据内存空间的浪费，同时这也是一种非常常见的数据存储方式，实用性较高。

Tags: