C语言队列探究

发布时间：2023-05-23

一、队列的基本概念

队列是一种线性数据结构，它具有FIFO的特点，即先进先出。相比于栈，队列需要维护两个指针，一个指向队头，一个指向队尾，队头指向队列中第一个入队的元素，队尾指向队列中的最后一个入队的元素。队尾和队头从队列两端对元素进行操作：

typedef struct{
    int data[MAXSIZE];
    int front;
    int rear;
}Queue;

其中MAXSIZE代表队列中可以存放元素的最大数量，front和rear分别代表队列的队头和队尾，初始值均为0。

二、队列的实现方式

  1. 顺序队列 顺序队列的实现方式是利用数组来存储队列中的元素，并利用两个指针front和rear分别指向队头和队尾的位置。队列的入队操作是在rear位置插入元素，出队操作是在front位置取出元素。但是顺序队列也存在一些问题，如元素入队后，front位置不会改变，所以出现了假溢出的情况，而这样会浪费很大的空间。解决假溢出的方法是将元素移动到数组的前端，并将front和rear同时减小移动的元素个数。
void Enqueue(Queue *q, int element){
    if(q->rear == MAXSIZE){
        printf("队列已满\n");
        return;
    }
    q->data[q->rear++] = element;
}
int Dequeue(Queue *q){
    if(q->front == q->rear){
        printf("队列已空\n");
        return -1;
    }
    return q->data[q->front++];
}
  1. 链式队列 链式队列的实现方式是利用指针来构建出队列，而不是像顺序队列一样用数组来存储。链式队列将队列中的每个元素用一个结构体来表示，其中每个结构体中有一个指针指向下一个元素。其入队和出队操作就是在链表的末尾插入元素和在链表的头部删除元素。
typedef struct node{
    int data;
    struct node *next;
}Node;
typedef struct{
    Node *front;
    Node *rear;
}Queue;
void Enqueue(Queue *q, int element){
    Node *newnode = (Node*)malloc(sizeof(Node));
    newnode->data = element;
    newnode->next = NULL;
    if(q->rear == NULL){
        q->front = q->rear = newnode;
    }
    else{
        q->rear->next = newnode;
        q->rear = newnode;
    }
}
int Dequeue(Queue *q){
    if(q->front == NULL){
        printf("队列已空\n");
        return -1;
    }
    int data = q->front->data;
    Node *temp = q->front;
    q->front = q->front->next;
    free(temp);
    if(q->front == NULL){
        q->rear = NULL;
    }
    return data;
}

三、队列的应用场景

队列可以用于多种场景，如操作系统进程调度中的进程队列、计算机网络中的消息传递和缓存队列等。下面以操作系统中的进程调度为例，解释队列在操作系统中的应用： 操作系统中，有多个进程在运行，需要通过调度程序来实现进程的切换和调度。为了保证进程按照一定规则进行调度，通常会把所有进程都加入到等待队列中，调度程序从等待队列中按照一定的优先级和调度算法来选择下一个进程来运行。

typedef struct{
    int pid;  //进程ID
    int priority;   //进程优先级
    int burst_time; //进程运行时间
}Process;
Queue queue;
int main(){
    int i;
    Process p[5] = {
        {1, 3, 24},
        {2, 1, 3},
        {3, 4, 4},
        {4, 2, 1},
        {5, 5, 8}
    };
    InitQueue(&queue);
    for(i=0; i<5; i++){
        Enqueue(&queue, p[i]);
    }
    // 进程调度，并输出每个进程最终运行的时间
    Process current;
    while((current = Dequeue(&queue))!=NULL){
        printf("Process %d is running, left runtime = %d\n", current.pid, current.burst_time);
        if(current.burst_time > 0){
            current.burst_time--;
            Enqueue(&queue, current);
        }
    }
    return 0;
}

四、队列的总结

队列是解决问题的一种有效数据结构，在多种应用场景下都有广泛的应用。从队列的基本概念出发，探究了队列的两种实现方式，顺序队列和链式队列。最后以操作系统中的进程调度为例，进一步阐述了队列的应用场景。了解了队列的概念和应用，我们可以更加深入地理解C语言这门编程语言。

推荐文章