C 語言隊列實現：循環隊列 ADT 完整代碼與測試

編輯：關於C語言

隊列 ADT 設計

採用循環隊列，結構體包含：動態數組指針、容量、隊頭索引、隊尾索引、當前大小。支持創建、銷毀、入隊、出隊、獲取隊頭、判空/判滿、獲取大小。

頭文件 `queue.h`

#ifndef _QUEUE_H
#define _QUEUE_H

typedef int ElementType;

typedef struct QueueRecord *Queue;

Queue CreateQueue(int maxElements);
void DisposeQueue(Queue Q);
int IsEmpty(Queue Q);
int IsFull(Queue Q);
void MakeEmpty(Queue Q);
void Enqueue(ElementType X, Queue Q);
ElementType Front(Queue Q);
void Dequeue(Queue Q);
ElementType FrontAndDequeue(Queue Q);
int Size(Queue Q);

#endif

實現 `queue.c`

#include "queue.h"
#include <stdlib.h>
#include <stdio.h>

#define MIN_QUEUE_SIZE 5

struct QueueRecord {
    int capacity;
    int front;
    int rear;
    int size;
    ElementType *array;
};

Queue CreateQueue(int maxElements) {
    if (maxElements < MIN_QUEUE_SIZE) {
        fprintf(stderr, "Queue size too small\n");
        return NULL;
    }
    Queue Q = malloc(sizeof(struct QueueRecord));
    if (!Q) { perror("malloc QueueRecord"); return NULL; }

    Q->array = malloc(sizeof(ElementType) * maxElements);
    if (!Q->array) { perror("malloc array"); free(Q); return NULL; }

    Q->capacity = maxElements;
    MakeEmpty(Q);
    return Q;
}

void DisposeQueue(Queue Q) {
    if (Q) {
        free(Q->array);
        free(Q);
    }
}

int IsEmpty(Queue Q) { return Q->size == 0; }
int IsFull(Queue Q)  { return Q->size == Q->capacity; }

void MakeEmpty(Queue Q) {
    Q->size = 0;
    Q->front = 0;
    Q->rear = 0;
}

static int Succ(int value, Queue Q) {
    if (++value == Q->capacity) value = 0;
    return value;
}

void Enqueue(ElementType X, Queue Q) {
    if (IsFull(Q)) {
        fprintf(stderr, "Full queue\n");
        return;
    }
    Q->size++;
    Q->rear = Succ(Q->rear, Q);
    Q->array[Q->rear] = X;
}

ElementType Front(Queue Q) {
    if (IsEmpty(Q)) {
        fprintf(stderr, "Empty queue\n");
        return 0;
    }
    return Q->array[Q->front];
}

void Dequeue(Queue Q) {
    if (IsEmpty(Q)) {
        fprintf(stderr, "Empty queue\n");
        return;
    }
    Q->size--;
    Q->front = Succ(Q->front, Q);
}

ElementType FrontAndDequeue(Queue Q) {
    ElementType X = Front(Q);
    Dequeue(Q);
    return X;
}

int Size(Queue Q) { return Q->size; }

測試程序 `test_queue.c`

#include "queue.h"
#include <stdio.h>

int main() {
    Queue Q = CreateQueue(10);
    for (int i = 0; i < 5; i++) Enqueue(i, Q);
    printf("Size: %d\n", Size(Q)); // 5

    while (!IsEmpty(Q)) {
        printf("%d ", FrontAndDequeue(Q));
    }
    printf("\n");

    DisposeQueue(Q);
    return 0;
}