C 语言队列和应用详情

什么是队列

队列是一种数据结构，可以用来存储一组按顺序排列的元素。队列的特点就是先进先出，即First In First Out，缩写为 FIFO。也就是说，最先插入队列的元素会最先被取出，最后插入队列的元素则会最后被取出。常见的生活中队列应用包括的排队取号，排队坐火车，排队打饭等等。

C 语言实现队列

在 C 语言中，我们可以通过数组来实现队列。首先定义队列结构体，包含队列的属性以及队列的值：

#define QUEUE_SIZE 100
typedef struct{
    int data[QUEUE_SIZE];   // 存放队列元素的数组
    int head;    // 队头指针
    int tail;    // 队尾指针
}Queue;

其中，data 数组是存储队列元素的数组，head 是队头指针，tail 是队尾指针。队列的初始化，队尾、队头的添加和删除操作等函数的实现如下：

// 初始化队列
void InitQueue(Queue *Q)
{
    Q->head = 0;
    Q->tail = 0;
}

// 判断队列是否为空
int QueueEmpty(Queue Q)
{
    return Q.head == Q.tail;
}

// 判断队列是否已满
int QueueFull(Queue Q)
{
    return (Q.tail + 1) % QUEUE_SIZE == Q.head;
}

// 从队尾插入元素
int EnQueue(Queue *Q, int x)
{
    if (QueueFull(*Q))    // 队列已满，插入失败
        return 0;
    Q->data[Q->tail] = x;
    Q->tail = (Q->tail + 1) % QUEUE_SIZE;
    return 1;
}

// 从队头删除元素
int DeQueue(Queue *Q, int *x)
{
    if (QueueEmpty(*Q))    // 队列为空，删除失败
        return 0;
    *x = Q->data[Q->head];
    Q->head = (Q->head + 1) % QUEUE_SIZE;
    return 1;
}

队列的应用

单词倒序

我们可以用队列来实现对单词倒序的功能。对于一段文本，我们可以将其按照空格和其他标点符号进行分割，然后将每个单词插入到队列中。最后从队列中取出单词并拼接起来就能得到倒序后的文本。

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

#define WORD_SIZE 50   // 定义单词的最大长度
#define QUEUE_SIZE 100   // 定义队列的大小

typedef struct{
    char data[WORD_SIZE];
    int length;   // 单词的实际长度
}Word;

typedef struct{
    Word data[QUEUE_SIZE];
    int head;
    int tail;
}Queue;

// 初始化队列
void InitQueue(Queue *Q)
{
    Q->head = 0;
    Q->tail = 0;
}

// 判断队列是否为空
int QueueEmpty(Queue Q)
{
    return Q.head == Q.tail;
}

// 判断队列是否已满
int QueueFull(Queue Q)
{
    return (Q.tail + 1) % QUEUE_SIZE == Q.head;
}

// 从队尾插入元素
int EnQueue(Queue *Q, char *x)
{
    if (QueueFull(*Q))    // 队列已满，插入失败
        return 0;
    Word new_word;
    new_word.length = strlen(x);
    strcpy(new_word.data, x);
    Q->data[Q->tail] = new_word;
    Q->tail = (Q->tail + 1) % QUEUE_SIZE;
    return 1;
}

// 从队头删除元素
int DeQueue(Queue *Q, Word *x)
{
    if (QueueEmpty(*Q))    // 队列为空，删除失败
        return 0;
    *x = Q->data[Q->head];
    Q->head = (Q->head + 1) % QUEUE_SIZE;
    return 1;
}

int main()
{
    char str[] = "hello, how are you today?";
    char *tok = strtok(str, " ,?!");
    Queue Q;
    InitQueue(&Q);
    while (tok != NULL)
    {
        EnQueue(&Q, tok);
        tok = strtok(NULL, " ,?!");
    }
    while (!QueueEmpty(Q))
    {
        Word w;
        DeQueue(&Q, &w);
        for (int i = w.length - 1; i >= 0; i--)
            printf("%c", w.data[i]);
        printf(" ");
    }
    printf("\n");
    return 0;
}

模拟进程调度

我们可以用队列来实现模拟进程调度。进程调度是指操作系统为了合理利用 CPU 资源，动态地将进程从就绪态调度到运行态，从而实现进程并发执行的过程。你可以将每个进程看成队列的元素，优先级高的进程先插入队列，调度的过程就是从队头取出将要执行的进程。

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

#define QUEUE_SIZE 100

typedef struct{
    int id;
    int priority;   // 进程优先级
    int remain_time;   // 剩余运行时间
}Process;

typedef struct{
    Process data[QUEUE_SIZE];   // 存放进程的数组
    int head;   // 队头指针
    int tail;   // 队尾指针
}Queue;

// 初始化队列
void InitQueue(Queue *Q)
{
    Q->head = 0;
    Q->tail = 0;
}

// 判断队列是否为空
int QueueEmpty(Queue Q)
{
    return Q.head == Q.tail;
}

// 判断队列是否已满
int QueueFull(Queue Q)
{
    return (Q.tail + 1) % QUEUE_SIZE == Q.head;
}

// 从队尾插入元素
int EnQueue(Queue *Q, Process p)
{
    if (QueueFull(*Q))    // 队列已满，插入失败
        return 0;
    Q->data[Q->tail] = p;
    Q->tail = (Q->tail + 1) % QUEUE_SIZE;
    return 1;
}

// 从队头删除元素
int DeQueue(Queue *Q, Process *p)
{
    if (QueueEmpty(*Q))    // 队列为空，删除失败
        return 0;
    *p = Q->data[Q->head];
    Q->head = (Q->head + 1) % QUEUE_SIZE;
    return 1;
}

int main()
{
    int n = 5;   // 进程数量
    Process P[n];   // 进程数组
    Queue Q;
    InitQueue(&Q);
    // 进程的初始化
    for (int i = 0; i < n; i++)
    {
        P[i].id = i;
        P[i].priority = rand() % 10;
        P[i].remain_time = rand() % 10 + 1;
        EnQueue(&Q, P[i]);
    }
    // 进行进程调度
    int time = 0;   // 系统运行的时间
    while (!QueueEmpty(Q))
    {
        printf("time = %d\n", time);
        Process p;
        DeQueue(&Q, &p);
        p.remain_time--;
        if (p.remain_time > 0)
        {
            EnQueue(&Q, p);
            printf("process%d is running （priority=%d, remain_time=%d）\n", p.id, p.priority, p.remain_time);
        }
        else
        {
            printf("process%d finished\n", p.id);
        }
        time++;
    }
    return 0;
}

以上就是 C 语言队列和应用的完整攻略，希望能帮助到大家。