Skip to content

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_SIZErear = (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

创建

1
2
3
4
5
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 一直指着第一个元素前面一格,直接拿数据就不对了,所以需要先把队头指针先向后挪一个,指向真正的队头元素,再取数据。

判空

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

判满

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

打印队列

1
2
3
4
5
6
7
8
9
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

创建

1
2
3
4
5
6
Status Create(LinkStack* q)
{
    q->front = NULL;
    q->rear = NULL;
    return OK;
}
在创建的时候,将两个队头队尾两个指针置空

初始化

1
2
3
4
5
6
7
8
9
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;
}
出队的时候要考虑三种情况:

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

判空

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

清空链队

1
2
3
4
5
6
7
8
9
Status Clear(LinkQueue* q)
{
    if (isEmpty(q)) return OK;

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

销毁链队

1
2
3
4
5
6
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.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.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);
}