队列的那些事儿

墨蓝 2022-05-27 08:22 253阅读 0赞

#### 前言 ####

前面描述了堆栈是先进后入的方式，队列则是我们传统的先进先出方式，例如排队买票，如果先去的人肯定是先买到票，后去的人则是后买到票。我们实现的时候仍然采用数组和链表的形式分别实现

#### 数组实现 ####

#include<stdio.h>
    #include<stdlib.h>
    #define MAX 5
    // 定义队列结构体
    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 -> rear > MAX - 1;
    }
    // 入队列
    void enQueue(Queue *p, int data) {
        if(isFull(p))
            printf("%d不能够入队列,队列已满\n", data);
        else
            p -> data[p -> rear++] = data;
    }
    // 是否为空
    int isEmpty(Queue *p) {
        return p -> front == MAX;
    }
    // 出队列
    int deQueue(Queue *p) {
        return p -> data[p -> front++];
    }
    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");
        return 0;
    }

#### 链表实现 ####

#include<stdio.h>
    #include<stdlib.h>
    // 定义每个节点
    typedef struct node {
        int data;
        struct node *next;
    } Node;
    // 定义队列节点
    typedef struct queue {
        Node *front;
        Node *rear;
    } Queue;
    // 初始化
    void init(Queue *p) {
        p -> front = p -> rear = (Node *) malloc(sizeof(Node));
    }
    //入队列
    void enQueue(Queue *p, int data) {
        Node *newNode;
        newNode = (Node *) malloc(sizeof(Node));
        newNode -> data = data;
        p -> rear -> data = data;
        p -> rear -> next = newNode;
        p -> rear = newNode;
    }
    //出队列
    int deQueue(Queue *p) {
        Node *r;
        int data;
        r = p -> front;
        data = r -> data;
        p -> front = r -> next;
        free(r);
        return data;
    }
    // 判断是否为空
    int isEmpty(Queue *p) {
        return p -> front == p -> rear;
    }
    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");
        return 0;
    }