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_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

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

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

定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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;
}

初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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]);
    }
}

入队 & 出队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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 一直指着最后一个元素，如果直接放数据会覆盖掉原本队尾的数据，所以需要先把队尾指针向后挪一格，再放数据。

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

测试数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 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 ，没有队满。

定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 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;
}

入队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}
入队就是让原本的队尾指向新的结点，这一步是让新结点加入链表；

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

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

出队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}

打印链队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

完整代码

顺序队、循环队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 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
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 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);
}

链队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
// 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 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);
}