[数据结构]队列的C语言简单实现

╰+攻爆jí腚メ 2022-06-05 04:22 288阅读 0赞

Github:([https://github.com/FlameCharmander/DataStructure][https_github.com_FlameCharmander_DataStructure])  
队列是一种先进先出的数据结构。应用非常广，比如树的层序遍历需要它，图的广度优先搜索需要它，还有消息队列等。  
那如果你看了我之前的文章《栈的简单实现》，用那套思路来实现队列，你会发现可行，但是会造成数组的严重浪费（出队之后的那部分数组，不再使用）。  
因此我们比较常用来实现顺序队列话是用循环队列。所以本文也采用循环队列的方式来实现队列。

#include <stdio.h>
    #include <stdlib.h>
    
    #define ElemType char
    #define MAXSIZE 100
    #define BOOL int
    #define FALSE 0
    #define TRUE  1
    
    typedef struct{
        ElemType data[MAXSIZE];
        int front, rear;
    }Queue;
    
    void InitQueue(Queue *queue);   //初始化队列
    BOOL IsEmpty(Queue *queue); //判断是否为空
    void EnQueue(Queue *queue, ElemType x); //入队
    void DeQueue(Queue *queue, ElemType *x);    //出队
    
    int main()
    {
        Queue q;
        InitQueue(&q);
        ElemType e;
        printf("%d\n", IsEmpty(&q));
        EnQueue(&q, 'a');
        EnQueue(&q, 'b');
        DeQueue(&q, &e);
        printf("%c\n", e);
        printf("%d\n", IsEmpty(&q));
        DeQueue(&q, &e);
        printf("%c\n", e);
        printf("%d\n", IsEmpty(&q));
        return 0;
    }
    
    void InitQueue(Queue *queue){
        queue->front = 0;
        queue->rear = 0;
    }
    
    void EnQueue(Queue *queue, ElemType e){
        queue->data[queue->rear] = e;
        queue->rear = (queue->rear + 1) % MAXSIZE;
    }
    
    void DeQueue(Queue *queue, ElemType *e){
        *e = queue->data[queue->front];
        queue->front = (queue->front + 1) % MAXSIZE;
    }
    
    BOOL IsEmpty(Queue *queue){
        if (queue->front == queue->rear) {
            return TRUE;
        } else {
            return FALSE;
        }
    }

这里我建议你们新开一个窗口，把代码和下面的部分进行一行一行阅读。  
Line 1~2 导入头文件。  
Line 4 队列元素的类型。  
Line 5 定义队列的数组大小。  
Line 6~8 由于C语言没有布尔型，我们用整型代替布尔型。  
Line 10~13 队列的数据结构，包括一个数组（存放元素），队头队尾（初始值应该都为0）。  
Line 15~18 今天主要实现的4个操作，InitQueue是初始化，IsEmpty是判断是否为空，EnQueue是入栈，DeQueue是出栈。  
Line 20~35 main函数，主要对队列进行初始化，入队，出队，判断是否为空的操作进行测试。  
Line 37~40 队列的初始化操作，将队列的队头指针和队尾指针初始化为0。这里就不说为什么参数(Queue \*queue)是用指针的。如果你有兴趣，看上我的上一篇博客《栈的简单实现》。反正大体意思就是我们要想修改队列结构体的元素，就必须用指针。  
Line 42~45 队列的入队操作，更新队尾指针。由于是循环队列，所以队尾指针需要进行求模操作：queue->rear = (queue->rear + 1) % MAXSIZE，如果不太懂这个公式，我建议你先去看看理论部分，这里不做过多的赘述。这里的队列传入的参数也用了指针，原因如上。  
Line 47~50 队列的出队操作，更新队头指针。队头指针的更新公式为：queue->front = (queue->front + 1) % MAXSIZE。这里的队列传入的参数也用了指针，原因如上。  
Line 52~58 队列的判断为空操作。循环队列比较常用是牺牲一个单元，然后判断为空的条件就为queue->front == queue->rear。

[https_github.com_FlameCharmander_DataStructure]: https://github.com/FlameCharmander/DataStructure