C语言详解链式队列与循环队列的实现

链式队列的实现

链式队列是一种使用链表实现的队列。这种队列没有静态数组的限制，可以动态地添加或删除元素。

链式队列的定义

链式队列可以通过定义一个结构体来表示：

typedef struct node{
    int data;                   // 存放队列元素的数据
    struct node *next;          // 存放下一个元素的地址
}Node;                          // 队列元素的类型

typedef struct linked_queue{
    Node *front;                // 队头指针
    Node *rear;                 // 队尾指针
}LinkedQueue;                    // 队列类型

队列的初始化实现如下：

void InitQueue(LinkedQueue *q){
    q->front = q->rear = (Node*)malloc(sizeof(Node));
    q->front->next = NULL;
}

入队操作

当队列为空时，要插入的元素既是队头又是队尾。其他情况下，只需在队尾插入元素即可。

void EnQueue(LinkedQueue *q, int x){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

出队操作

当队列为空时，无法进行出队操作。

int DeQueue(LinkedQueue *q){
    if(q->front == q->rear)  return -1; // 队列为空
    Node *p = q->front->next;
    int x = p->data;
    q->front->next = p->next;
    if(q->rear == p)    q->rear = q->front;
    free(p);
    return x;
}

循环队列的实现

循环队列可以使用静态数组来实现，是一种较为常用的队列实现方式。队列的头尾相连成一个环，可以循环利用数组空间，提高队列的利用率。

循环队列的定义

循环队列也可以通过定义一个结构体来表示：

typedef struct circular_queue{
    int *data;      // 存放队列元素的数组
    int front;      // 队头指针
    int rear;       // 队尾指针
    int size;       // 队列容量
}CircularQueue;     // 队列类型

队列的初始化实现如下：

void InitQueue(CircularQueue *q, int size){
    q->data = (int*)malloc(size * sizeof(int));
    q->front = q->rear = 0;
    q->size = size;
}

入队操作

当队列为空时，无论第一个插入的元素是哪个，队头与队尾都指向该元素。在队列不满的情况下，队尾指针右移，将新元素插入当前队尾的下一个位置。

bool EnQueue(CircularQueue *q, int x){
    if((q->rear + 1) % q->size == q->front)   return false; // 队列满
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % q->size;
    return true;
}

出队操作

当队列为空时，无法进行出队操作。在队列不空的情况下，队头指针右移，返回当前队头元素。

bool DeQueue(CircularQueue *q, int *x){
    if(q->front == q->rear)   return false; // 队列空
    *x = q->data[q->front];
    q->front = (q->front + 1) % q->size;
    return true;
}

示例说明

链式队列示例

下面是一个使用链式队列计算阶乘的示例：

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

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

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

void InitQueue(LinkedQueue *q){
    q->front = q->rear = (Node*)malloc(sizeof(Node));
    q->front->next = NULL;
}

void EnQueue(LinkedQueue *q, int x){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

int DeQueue(LinkedQueue *q){
    if(q->front == q->rear)  return -1;
    Node *p = q->front->next;
    int x = p->data;
    q->front->next = p->next;
    if(q->rear == p)    q->rear = q->front;
    free(p);
    return x;
}

int Fac(int n){
    LinkedQueue q;
    InitQueue(&q);                  // 定义链式队列
    EnQueue(&q, 1);                 // 先将1入队
    int f = 1;
    while(n--){
        int x = DeQueue(&q);        // 出队
        f *= x;                     // 阶乘
        EnQueue(&q, x+1);           // 入队
    }
    return f;
}

int main(){
    int n = 5;
    int f = Fac(n);
    printf("The factorial of %d is %d.\n", n, f);
    return 0;
}

循环队列示例

下面是一个使用循环队列实现的简易银行大厅管理程序：

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

typedef struct circular_queue{
    int *data;
    int front;
    int rear;
    int size;
}CircularQueue;

void InitQueue(CircularQueue *q, int size){
    q->data = (int*)malloc(size * sizeof(int));
    q->front = q->rear = 0;
    q->size = size;
}

bool EnQueue(CircularQueue *q, int x){
    if((q->rear + 1) % q->size == q->front)   return false;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % q->size;
    return true;
}

bool DeQueue(CircularQueue *q, int *x){
    if(q->front == q->rear)   return false;
    *x = q->data[q->front];
    q->front = (q->front + 1) % q->size;
    return true;
}

int main(){
    CircularQueue q;
    int size = 5;
    InitQueue(&q, size);                // 初始化队列
    EnQueue(&q, 1);                     
    EnQueue(&q, 2);
    EnQueue(&q, 3);
    int x;
    DeQueue(&q, &x);                    // 办理业务1
    printf("办理业务1的顾客号码：%d\n", x);
    EnQueue(&q, 4);
    EnQueue(&q, 5);
    DeQueue(&q, &x);                    // 办理业务2
    printf("办理业务2的顾客号码：%d\n", x);
    EnQueue(&q, 6);
    EnQueue(&q, 7);
    while(DeQueue(&q, &x)){             // 查看当前队列中的客户
        printf("%d ", x);
    }
    printf("\n");
    return 0;
}

以上两个示例分别为链式队列和循环队列的应用，可以看到这两种队列的实现方式、操作和应用场景的不同，需要根据实际情况选择合适的队列实现方式。