C利用语言实现数据结构之队列

C语言实现队列的完整攻略

什么是队列

队列是一种线性数据结构，它有两个端点：队头和队尾。新的元素插入到队尾，每次从队头取出一个元素。这就类似于人们排队买票，新的买票者排在队尾，每当售票员完成一笔交易，队列头的买票者出队。

基本操作

队列主要有以下3个基本操作：

• 入队（enqueue）：将一个元素添加到队列的尾部
• 出队（dequeue）：从队列的头部移除一个元素
• 队列是否为空（isEmpty）：判断队列是否为空

实现队列

我们可以利用C语言的数组来实现队列。首先定义一个结构体，包含队列元素、队头、队尾以及队列最大容量：

#define MAX_SIZE 10
typedef struct {
    int data[MAX_SIZE]; // 存放元素的数组
    int front; // 队头索引
    int rear; // 队尾索引
    int size; // 队列当前大小
}queue;

然后，我们可以依照上面的基本操作实现队列：

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

// 判断队列是否为空
bool isEmpty(const queue* q) {
    return q->size == 0;
}

// 判断队列是否已满
bool isFull(const queue* q) {
    return q->size == MAX_SIZE;
}

// 入队
bool enqueue(queue* q, int element) {
    if(isFull(q)) {
        return false;
    }
    q->data[q->rear] = element;
    q->rear = (q->rear+1)%MAX_SIZE; // 循环队列，如果超出队列最大容量则从头开始
    q->size++;
    return true;
}

// 出队
bool dequeue(queue* q) {
    if(isEmpty(q)) {
        return false;
    }
    q->front = (q->front+1)%MAX_SIZE;
    q->size--;
    return true;
}

// 获取队头元素
int front(const queue* q) {
    if(isEmpty(q)) {
        return 0;
    }
    return q->data[q->front];
}

示例

示例一：实现队列的基本操作

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

#define MAX_SIZE 10
typedef struct {
    int data[MAX_SIZE]; // 存放元素的数组
    int front; // 队头索引
    int rear; // 队尾索引
    int size; // 队列当前大小
}queue;

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

// 判断队列是否为空
bool isEmpty(const queue* q) {
    return q->size == 0;
}

// 判断队列是否已满
bool isFull(const queue* q) {
    return q->size == MAX_SIZE;
}

// 入队
bool enqueue(queue* q, int element) {
    if(isFull(q)) {
        return false;
    }
    q->data[q->rear] = element;
    q->rear = (q->rear+1)%MAX_SIZE; // 循环队列，如果超出队列最大容量则从头开始
    q->size++;
    return true;
}

// 出队
bool dequeue(queue* q) {
    if(isEmpty(q)) {
        return false;
    }
    q->front = (q->front+1)%MAX_SIZE;
    q->size--;
    return true;
}

// 获取队头元素
int front(const queue* q) {
    if(isEmpty(q)) {
        return 0;
    }
    return q->data[q->front];
}

int main() {
    queue q;
    init(&q);
    printf("队列是否为空：%d\n", isEmpty(&q)); // 1，队列为空
    enqueue(&q, 1);
    enqueue(&q, 2);
    printf("队列是否为空：%d\n", isEmpty(&q)); // 0，队列不为空
    printf("队列的大小：%d\n", q.size); // 2
    printf("队头元素：%d\n", front(&q)); // 1
    dequeue(&q);
    printf("队头元素：%d\n", front(&q)); // 2
    printf("队列的大小：%d\n", q.size); // 1
    printf("队列是否为空：%d\n", isEmpty(&q)); // 0，队列不为空
    dequeue(&q);
    printf("队列是否为空：%d\n", isEmpty(&q)); // 1，队列为空
    return 0;
}

示例二：使用队列完成约瑟夫环（n个人围成一个环，从第1个人开始报数，报到m的人出圈，直到所有人出圈）

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
}queue;

int main() {
    int n,m;
    printf("请输入n和m的值：");
    scanf("%d%d", &n, &m);
    queue q;
    q.front = 0;
    q.rear = 0;
    q.size = 0;
    for(int i=1; i<=n; i++) {
        enqueue(&q,i);
    }
    int count = 0;
    while(!isEmpty(&q)) {
        int x = front(&q);
        dequeue(&q);
        count++;
        if(count == m) {
            printf("%d ", x);
            count = 0;
        }
        else {
            enqueue(&q,x);
        }
    }
    return 0;
}

注意：在示例二中，我们使用了单独的enqueue和dequeue函数来实现队列操作。这是因为该示例中没有采用完整的队列结构体，而仅仅是利用数组存储队列元素。