4-队列¶

队列是只允许在一端进行插入操作，在另一端进行删除操作的受限的线性表。

队列是一种 先进先出(FIFO) 的线性表，就像水管一样，从一头进去，从另一头出来

队列有两个指针，一个指向队头，只允许删除；一个指向队尾，只允许插入。

对于队列的操作有插入和删除，也称作入队和出队，不能从中间取。

顺序队：队列的每一个元素在一段连续的内存空间，用数组实现。
链队：队列的每一个元素不一定紧挨着，用链表实现。
循环队：队头连接着队尾。

队的主要操作包括：创建、初始化、入队、出队、判空、判满、清空队列。

循环队¶

顺序队是基于数组实现的，当入队一个元素的时候，队尾指针+1，当队尾指针=MAX_SIZE时队满；当出队一个元素的时候，队头指针+1，当队头指针=MAX_SIZE时，说明队空。

但是！！

当队头和队尾都 = MAX_SIZE 时，实际上队空，但是却无法入队新元素，这种现象称之为 假溢出。

所以为了解决这个问题，我们可以用 循环队列。

由空队入队两个元素，此时 fron == 0, rear == 2 入队4个元素，出队3个元素，此时 front == 3, rear == 6 入队2个元素，出队4个元素，此时 front == 7, rear == 0

队空条件：front == rear 队满条件：(rear + 1)%MAX_SIZE == front

要实现循环队列，最重要的是怎么做才能让队头队尾指针在一个周期中循环。

答案是 front = (front + 1) % MAX_SIZE、rear = (rear + 1) % MAX_SIZE。

假设 MAX_SIZE == 8, front == 1，(front + 1) % MAX_SIZE 等价于 2 % 8 == 2

所以这条表达式，可以让队头队尾指针在 0~MAX_SIZE-1 这个周期中循环，也就是在 0, 1, 2, ... MAX_SIZE-1 中循环。

要素¶

循环队列的两个状态

队空： q->rear == q->front

队满： (q->rear + 1) % MAX_SIZE == q->front

入队出队

q->rear = (q->rear + 1) % MAX_SIZE; 
q->data[q->rear] = x;

q->front = (q->front + 1) % MAX_SIZE;
X = q->data[q->front];

定义¶

// DataElement.h

#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define MAX_SIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int Bool;

typedef struct {
    int id;
    char* name;
} Element;

typedef struct {
    Element datas[MAX_SIZE];
    int front;
    int rear;
} SqQueue;

#endif // DATAELEMENT_H_INCLUDED

创建¶

Status Create(SqQueue* q)
{
    q->front = 0;
    q->rear = 0;
}

初始化¶

Status Init(SqQueue* q, Element* datas, int length)
{
    if (length > MAX_SIZE) {
        return ERROR;
    }

    if (!(q->front && q->rear))
        Create(q);

    for (int i = 0; i < length; i++) {
        EnQueue(q, datas[i]);
    }
}

入队 & 出队¶

入队出队

Status EnQueue(SqQueue* q, Element e)
{
    // 如果队满, 无法入队
    if (isFull(q))
        return ERROR;
    q->rear = (q->rear + 1) % MAX_SIZE; // 先把队尾移动一格
    q->datas[q->rear] = e; // 再把数据放进去

    return OK;
}

因为队尾指针 rear 一直指着最后一个元素，如果直接放数据会覆盖掉原本队尾的数据，所以需要先把队尾指针向后挪一格，再放数据。

Status DeQueue(SqQueue* q, Element* e)
{
    // 如果队空，无法出队
    if (isEmpty(q))
        return ERROR;

    q->front = (q->front + 1) % MAX_SIZE;
    *e = q->datas[q->front];
    return OK;
}

因为队头指针 front 一直指着第一个元素前面一格，直接拿数据就不对了，所以需要先把队头指针先向后挪一个，指向真正的队头元素，再取数据。

判空¶

Bool isEmpty(SqQueue* q)
{
    return q->front == q->rear;
}

判满¶

Bool isFull(SqQueue* q)
{
    return q->front == (q->rear + 1) % MAX_SIZE;
}

打印队列¶

void Print(SqQueue* q)
{
    if (isEmpty(q))
        printf("队列为空！");

    for (int i = q->front + 1; i < q->rear + 1; i++) {
        printf("%d \t %s \n", q->datas[i].id, q->datas[i].name);
    }
}

测试数据¶

// main.c

#include "SqQueue.c"
#define len(X) sizeof(X) / sizeof(X[0])

Element datas[] = {
    { 1, "Iron Man" },
    { 2, "Thor" },
    { 3, "Captain" },
    { 4, "Green Man" }
};

void main()
{
    SqQueue q;
    Create(&q);
    Init(&q, datas, len(datas));
    printf("After Init(): \n");
    Print(&q);

    printf("\n-------------------------------------\n");

    Element el = { 5, "Big Man" };
    EnQueue(&q, el);
    printf("After EnQueue(): \n");
    Print(&q);

    printf("\n-------------------------------------\n");

    DeQueue(&q, &el);
    printf("After DeQueue(): \n");
    printf("%d \t %s", el.id, el.name);
}

链队¶

链队相比循环队则简单多了，入队就是链表的插入，出队就是链表的删除，队空就是队头指针和队尾指针都为 NULL ，没有队满。

定义¶

// DataElement.h

#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define OK 1
#define ERROR 0

typedef int Status;

typedef struct {
    int id;
    char* name;
} Element;

typedef struct Node {
    Element data;
    struct Node* next;
} Node;

// 定义链队结构体
typedef struct {
    Node* front;
    Node* rear;
} LinkQueue;

#endif // DATAELEMENT_H_INCLUDED

创建¶

Status Create(LinkStack* q)
{
    q->front = NULL;
    q->rear = NULL;
    return OK;
}

在创建的时候，将两个队头队尾两个指针置空

初始化¶

Status Init(LinkQueue* q, Element* datas, int length)
{
    if (!isEmpty(q)) Create(q);

    for (int i = 0; i < length; i++) {
        EnQueue(q, datas[i]);
    }
    return OK;
}

入队¶

Status EnQueue(LinkQueue* q, Element e)
{
    Node* new = (Node*)malloc(sizeof(Node));
    new->data = e;
    new->next = NULL;

    if (isEmpty(q)) {   // 如果队列为空，除了让队尾指向新结点，让队头也指向新结点
        q->front = q->rear = new;
        return OK;
    } else {    // 如果队列不为空，让旧的队尾元素指向新结点，队尾指针指向新结点
        q->rear->next = new;
        q->rear = new;
        return OK;
    }
    return ERROR;
}

入队就是让原本的队尾指向新的结点，这一步是让新结点加入链表；

然后让队尾指针也指向新的结点，这一步是对队尾指针的更新。

如果队列为空时，队头指针和队尾指针一起指向新结点。

出队¶

Element DeQueue(LinkQueue* q, )
{
    Element e;
    if (isEmpty(q)) return e;

    if (q->front == q->rear) {  // 链队中只有一个元素时，出队后队空，所以需要恢复队头和队尾指针为空
        e = q->rear->data;
        free(q->rear);
        q->front = q->rear = NULL;
        return e;
    }

    // 链队中不止一个元素时
    // 1. 取元素
    e = q->front->data;
    // 2. 改链
    Node* de = q->front;
    q->front = de->next;
    // 3. 释放空间
    free(de);
    de = NULL;
    return e;
}

出队的时候要考虑三种情况：

队空，则返回一个空元素;
只有一个元素，出队后队头指针和队尾指针都要置空;
不止一个元素，则取元素、改链、释放空间，最后返回元素。

判空¶

bool isEmpty(LinkQueue* q)
{
    return q->front == NULL && q->rear == NULL;
}

清空链队¶

Status Clear(LinkQueue* q)
{
    if (isEmpty(q)) return OK;

    while (q->front) {
        DeQueue(q);
    }
    return OK;
}

销毁链队¶

Status Destory(LinkQueue* q)
{
    Clear(q);
    free(q);
    return OK;
}

打印链队¶

void Print(LinkQueue* q)
{
    if (isEmpty(q)) {
        printf("队列为空！");
        return;
    }

    Node* curr = q->front;
    while (curr) {
        printf("%d \t %s \n", curr->data.id, curr->data.name);
        curr = curr->next;
    }
}

完整代码¶

顺序队、循环队¶

DataElement.hSqQueue.hSqQueue.cmain.c

// DataElement.h
#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define MAX_SIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int Bool;

typedef struct {
    int id;
    char* name;
} Element;

typedef struct {
    Element datas[MAX_SIZE];
    int front;
    int rear;
} SqQueue;

#endif // DATAELEMENT_H_INCLUDED

// SqQueue.h
#ifndef DQQUEUE_H_INCLUDED
#define DQQUEUE_H_INCLUDED
#include "DataElement.h"

Status Create(SqQueue* q);

Status Init(SqQueue* q, Element* datas, int length);

Status EnQueue(SqQueue* q, Element e);

Status DeQueue(SqQueue* q, Element* e);

Bool isEmpty(SqQueue* q);

Bool isFull(SqQueue* q);

void Print(SqQueue* q);

#endif // DQQUEUE_H_INCLUDED

// SqQueue.c
#include "SqQueue.h"
#include <stdio.h>
#include <stdlib.h>

Status Create(SqQueue* q)
{
    q->front = 0;
    q->rear = 0;
}

Status Init(SqQueue* q, Element* datas, int length)
{
    if (length > MAX_SIZE) {
        return ERROR;
    }

    if (!(q->front && q->rear))
        Create(q);

    for (int i = 0; i < length; i++) {
        EnQueue(q, datas[i]);
    }
}

Status EnQueue(SqQueue* q, Element e)
{
    // 如果队满, 无法入队
    if (isFull(q))
        return ERROR;
    q->rear = (q->rear + 1) % MAX_SIZE; // 先把队尾移动一格
    q->datas[q->rear] = e; // 再把数据放进去

    return OK;
}

Status DeQueue(SqQueue* q, Element* e)
{
    // 如果队空，无法出队
    if (isEmpty(q))
        return ERROR;

    q->front = (q->front + 1) % MAX_SIZE;
    *e = q->datas[q->front];
    return OK;
}

Bool isEmpty(SqQueue* q)
{
    return q->front == q->rear;
}

Bool isFull(SqQueue* q)
{
    return q->front == (q->rear + 1) % MAX_SIZE;
}

void Print(SqQueue* q)
{
    if (isEmpty(q))
        printf("队列为空！");

    for (int i = q->front + 1; i < q->rear + 1; i++) {
        printf("%d \t %s \n", q->datas[i].id, q->datas[i].name);
    }
}

// main.c
#include "SqQueue.c"
#define len(X) sizeof(X) / sizeof(X[0])

Element datas[] = {
    { 1, "Iron Man" },
    { 2, "Thor" },
    { 3, "Captain" },
    { 4, "Green Man" }
};

void main()
{
    SqQueue q;
    Create(&q);
    Init(&q, datas, len(datas));
    printf("After Init(): \n");
    Print(&q);

    printf("\n-------------------------------------\n");

    Element el = { 5, "Big Man" };
    EnQueue(&q, el);
    printf("After EnQueue(): \n");
    Print(&q);

    printf("\n-------------------------------------\n");

    DeQueue(&q, &el);
    printf("After DeQueue(): \n");
    printf("%d \t %s", el.id, el.name);
}

链队¶

DataElement.hLinkQueue.hLinkQueue.cmain.c

// DataElement.h
#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define OK 1
#define ERROR 0

typedef int Status;

typedef struct {
    int id;
    char* name;
} Element;

typedef struct Node {
    Element data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} LinkQueue;

#endif // DATAELEMENT_H_INCLUDED

// LinkQueue.h
#ifndef LINKQUEUE_H_INCLUDED
#define LINKQUEUE_H_INCLUDED
#include <stdbool.h>
#include "DataElement.h"

Status Create(LinkQueue* q);

Status InitLinkQ(LinkQueue* q, Element* datas, int length);

Status EnQueue(LinkQueue* q, Element e);

Element DeQueue(LinkQueue* q);

Status Clear(LinkQueue* q);

Status Destory(LinkQueue* q);

bool isEmpty(LinkQueue* q);

void Print(LinkQueue* q);

#endif // LINKQUEUE_H_INCLUDED

// LinkQueue.c

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

Status Create(LinkQueue* q)
{
    q->front = NULL;
    q->rear = NULL;
    return OK;
}

Status InitLinkQ(LinkQueue* q, Element* datas, int length)
{
    if (!isEmpty(q)) {
        Create(q);
    }

    for (int i = 0; i < length; i++) {
        EnQueue(q, datas[i]);
    }
    return OK;
}

Status EnQueue(LinkQueue* q, Element e)
{
    Node* new = (Node*)malloc(sizeof(Node));
    new->data = e;
    new->next = NULL;

    // 如果队空，让队头也指向新结点
    if (isEmpty(q)) {
        q->front = q->rear = new;
        return OK;
    } else {
        // 队尾元素 指向新结点
        q->rear->next = new;
        // 队尾指针 指向新结点
        q->rear = new;
        return OK;
    }
    return ERROR;
}

Element DeQueue(LinkQueue* q)
{
    Element e;
    if (isEmpty(q))
        return e;
    // 如果队中只有一个元素
    if (q->front == q->rear) {
        e = q->front->data;
        free(q->front);
        q->front = q->rear = NULL;
        return e;
    }

    // 1. 改链
    Node* de = q->front;
    q->front = de->next;
    // 2. 取元素
    e = de->data;
    // 3. 释放空间
    free(de);
    de = NULL;
    return e;
}

bool isEmpty(LinkQueue* q)
{
    return q->front == NULL && q->rear == NULL;
}

Status Clear(LinkQueue* q)
{
    if (isEmpty(q)) {
        return OK;
    }
    while (q->front) {
        DeQueue(q);
    }
    return OK;
}

Status Destory(LinkQueue* q)
{
    Clear(q);
    free(q);
    return OK;
}

void Print(LinkQueue* q)
{
    if (isEmpty(q)) {
        printf("队列为空！");
        return;
    }

    Node* curr = q->front;
    while (curr) {
        printf("%d \t %s \n", curr->data.id, curr->data.name);
        curr = curr->next;
    }
}

// main.c

#include "LinkQueue.c"
#define len(X) sizeof(X) / sizeof(X[0])

Element datas[] = {
    { 1, "Iron Man" },
    { 2, "Thor" },
    { 3, "Captain" },
    { 4, "Green Man" }
};

void main()
{
    LinkQueue q;
    Create(&q);
    InitLinkQ(&q, datas, len(datas));
    Print(&q);

    printf("\n-------------------------------------\n");

    Element e = { 5, "Spider Man" };
    EnQueue(&q, e);
    Print(&q);

    printf("\n-------------------------------------\n");

    Element de = DeQueue(&q);
    printf("Element deleted: %d \t %s \n", de.id, de.name);
    printf("\n-------------------------------------\n");
    Print(&q);

    printf("\n-------------------------------------\n");
    Clear(&q);
    Print(&q);

    printf("\n-------------------------------------\n");
    // Destory(&q);
    // Print(&q);
}