队列的那些事儿（二）

不念不忘少年蓝@ 2022-05-26 00:19 151阅读 0赞

#### 前言 ####

我们前面说了队列的顺序实现，我们如果采用链表的实现方式当然是没什么问题的。但是如果我们采用数组的顺序实现，我们会发现一个问题。例如我们数组长度为10，我们入队列5个，然后出队列5个，接下来入队列就是从下表为5的开始进入队列，一直进入到9，那么我们就判断队列已经满了，但是实际上我们的0-4是空余的。因此我们想到可以采用循环队列的方式实现。

#### 循环队列 ####

###### 对于循环队列，我们主要有两种实现方式 ######

第一：采用一个count变量记录队列中目前有的元素个数，如果大于最大长度，则满了。  
第二：这种方法和第二种类似，我们通过判断头节点 = (尾结点 + 1) % 数组长度为队列满的条件，那么初始时头结点和尾节点相等。  
第二方法有一个特点就是我们的队列中始终有一个不能够存储元素  
下面主要对第一种和第二种用代码实现

##### 方法一 #####

#include<stdio.h>
    #include<stdlib.h>
    #define MAX 10
    // 定义队列结构体
    typedef struct queue {
        int data[MAX];
        int front;
        int rear;
        int count;
    }Queue;
    // 初始化
    void init(Queue *p) {
        p -> front = p -> rear = 0;
        p -> count = 0;
    }
    // 是否满
    int isFull(Queue *p) {
        return p -> count == MAX;
    }
    // 入队列
    void enQueue(Queue *p, int data) {
        if(isFull(p))
            printf("%d不能够入队列,队列已满\n", data);
        else {
            p -> data[(p -> rear++) % MAX] = data;
            p -> count++;
        }
    }
    // 是否为空
    int isEmpty(Queue *p) {
        return p -> count == 0;
    }
    // 出队列
    int deQueue(Queue *p) {
        p -> count--;
        return p -> data[(p -> front++) % MAX];
    }
    int main() {
        Queue s;
        init(&s);
        for(int i=0; i<6; i++)
            enQueue(&s, i);
        while(!isEmpty(&s))
            printf("%d ", deQueue(&s));
        printf("\n");
        for(int i=0; i<11; i++)
            enQueue(&s, i);
        while(!isEmpty(&s))
            printf("%d ", deQueue(&s));
        printf("\n");
        return 0;
    }

##### 方法二 #####

#include<stdio.h>
    #include<stdlib.h>
    #define MAX 11
    // 定义队列结构体
    typedef struct queue {
        int data[MAX];
        int front;
        int rear;
    }Queue;
    // 初始化
    void init(Queue *p) {
        p -> front = p -> rear = 0;
    }
    // 是否满
    int isFull(Queue *p) {
        return p -> front == (p -> rear + 1) % MAX;
    }
    // 入队列
    void enQueue(Queue *p, int data) {
        if(isFull(p))
            printf("%d不能够入队列,队列已满\n", data);
        else
            p -> data[(p -> rear++) % MAX] = data;
    }
    // 是否为空
    int isEmpty(Queue *p) {
        return p -> front == p -> rear;
    }
    // 出队列
    int deQueue(Queue *p) {
        return p -> data[(p -> front++) % MAX];
    }
    int main() {
        Queue s;
        init(&s);
        for(int i=0; i<6; i++)
            enQueue(&s, i);
        while(!isEmpty(&s))
            printf("%d ", deQueue(&s));
        printf("\n");
        for(int i=0; i<11; i++)
            enQueue(&s, i);
        while(!isEmpty(&s))
            printf("%d ", deQueue(&s));
        printf("\n");
        return 0;
    }