数据结构之队列

发表于 | 更新于: | 分类于 |
字数统计: 3,245 | 阅读时长 ≈ 15

什么是队列(queue)

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，在具体应用中通常用链表或者数组来实现。
和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。
因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）
点击这里查看博客对应的完整代码

非循环队列（普通队列）

非循环队列是最简单的队列，使用动态数组/数组实现，大小是固定的，虽然使用数组作为队列的存储结构，但是在队列中只操作头尾节点，所以插入（入队）和查找（出队）都很快。
非循环队列的缺点是可能会出现”假溢出”的情况。
下面是一个非循环队列的实现。

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
#define MAX_QSIZE 5 // 最大队列长度
// 队列的数据类型
typedef int Q_Data;
// 队列的存储结构
struct Queue {
    Q_Data Array[MAX_QSIZE]; // 阵列空间大小
    int front; // 队头
    int rear; // 队尾
    int length; // 队列长度
};

// 构造一个空队列Q
Queue* Q_Init() {
    Queue *Q = (Queue*)malloc(sizeof(Queue));
    if (!Q){
        // 存储分配失败
        exit(OVERFLOW);
    }
    //初始化
    Q->front = Q->rear = Q->length = 0;
    return Q;
}
// 将Q清为空队列
void Q_Clear(Queue *Q) {
    //清除头尾下标和长度
    Q->front = Q->rear = Q->length = 0;
}
// 入列
Q_Data Q_Put(Queue *Q, Q_Data x) {
    //如果当前元素数量等于最大数量 返回 -1
    if (Q->rear == MAX_QSIZE)
        return -1;
    Q->Array[Q->rear] = x;
    Q->rear++;
    //length + 1
    Q->length++;
    return 1;
}
// 出列
Q_Data Q_Poll(Queue *Q,Q_Data &e) {
    //如果当前元素数量等于最大数量 返回 -1
    if (Q->front == MAX_QSIZE)
        return -1;
    e = Q->Array[Q->front];
    Q->front++;
    // 移出后減少1
    Q->length--;
    return 1;
}

循环队列

循环队列可以更简单防止”假溢出”的发生，但队列大小是固定的，使用动态数组/数组实现，相对单链队列来说，插入（入队）和查找（出队）都很快。
这里说的循环是逻辑上的循环，体现在入队（put）出队（poll）的操作上面，比如长度是10，队列的头尾指针会始终在0 ～ 9之间循环，也就永远不会出现溢出的情况，因此称为循环队列。
循环队列中的循环是以舍弃队列中一个元素空间来达成的，也就是循环队列最大能存储maxSize - 1个元素，比如最大长度是10，那么只能保存9个元素到队列中。
下面是一个循环队列的实现。

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
// 队列的顺序存储结构(循环队列)
#define MAX_QSIZE 6 // 最大队列长度+1
// 队列的数据类型
typedef int Q_Data;
typedef struct {
    Q_Data *data; // 初始化的动态分配存储空间
    int front; // 头指针，若队列不空，指向队列头元素
    int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;

// 构造一个空队列Q
SqQueue* Q_Init() {
    SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue));
    // 存储分配失败
    if (!Q){
        exit(OVERFLOW);
    }
    Q->data = (Q_Data *)malloc(MAX_QSIZE * sizeof(Q_Data));
    // 存储分配失败
    if (!Q->data){
        exit(OVERFLOW);
    }
    Q->front = Q->rear = 0;
    return Q;
}
// 销毁队列Q，Q不再存在
void Q_Destroy(SqQueue *Q) {
    if (Q->data)
        free(Q->data);
    Q->data = NULL;
    Q->front = Q->rear = 0;
    free(Q);
}
// 将Q清为空队列
void Q_Clear(SqQueue *Q) {
    Q->front = Q->rear = 0;
}
// 若队列Q为空队列，则返回1；否则返回-1
Q_Data Q_Empty(SqQueue Q) {
    if (Q.front == Q.rear) // 队列空的标志
        return 1;
    else
        return -1;
}
// 返回Q的元素个数，即队列的长度
Q_Data Q_Length(SqQueue Q) {
    return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
}
// 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
Q_Data Q_GetHead(SqQueue Q, Q_Data &e) {
    if (Q.front == Q.rear) // 队列空
        return -1;
    e = Q.data[Q.front];
    return 1;
}
// 打印队列中的内容
void Q_Print(SqQueue Q) {
    Q_Data p = Q.front % MAX_QSIZE;
    while (Q.rear != p) {
        cout << Q.data[p] << endl;
        p = (p + 1) % MAX_QSIZE;
    }
}
// 插入元素e为Q的新的队尾元素
Q_Data Q_Put(SqQueue *Q, Q_Data e) {
    if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满
        return -1;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_QSIZE;
    return 1;
}
// 若队列不空，则删除Q的队头元素，用e返回其值，并返回1；否则返回-1
Q_Data Q_Poll(SqQueue *Q, Q_Data &e) {
    if (Q->front == Q->rear) // 队列空
        return -1;
    e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_QSIZE;
    return 1;
}

单链队列

单链队列使用链表作为基本数据结构，所以不存在”假溢出”的问题，队列长度也没有限制。
但插入和读取的时间代价较高，虽然使用链表实现，但链表的优势（O(1)任意节点插入）在队列中被抹去了，因为链表不允许操纵除头尾节点以外的节点，每次插入都需右移指针。
下面是一个单链队列的实现。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// 队列的数据类型
typedef int Q_Data;
// 定义单链队列的存储结构
typedef struct QNode {
    Q_Data data;
    QNode *next;
}QNode,*QNodePtr;

typedef struct LinkQueue{
    //队头 队尾 指针
    QNodePtr front,rear;
}LinkQueue;

// 构造一个空队列Q
LinkQueue* Q_Init() {
    //申请内存
    LinkQueue* Q = (LinkQueue*)malloc(sizeof(LinkQueue));
    //如果 Q 为 NULL 说明 内存申请失败，结束程序
    if (!Q)
        exit(OVERFLOW);
    //初始化头尾节点 指向相同地址
    Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode));
    //如果 Q->front 为 NULL 说明 内存申请失败，结束程序
    if (!Q->front)
        exit(OVERFLOW);
    Q->front->next = NULL;
    return Q;
}
// 销毁队列Q(无论空否均可)
void Q_Destroy(LinkQueue *Q) {
    while (Q->front) {
        //将队尾指向队头下一个节点的地址（第1个节点）
        Q->rear = Q->front->next;
        //回收队头
        free(Q->front);
        //将队头指向队尾（相当于第1个节点变成了队头，然后依次第2个第3个、、、
        //直到没有下一个节点，也就是 Q->front == NULL 的时候）
        Q->front = Q->rear;
    }
    free(Q);
}
// 将Q清为空队列
void Q_Clear(LinkQueue *Q) {
    QNodePtr p, q;
    //将队尾指向队头点的地址
    Q->rear = Q->front;
    //取出第1个节点
    p = Q->front->next;
    //回收第1个节点
    Q->front->next = NULL;
    while (p) {
        //将 q 指向 p（第1个节点）
        q = p;
        //将 p 指向 第2个节点
        p = p->next;
        //回收第2个节点
        free(q);
    }
}
// 若Q为空队列，则返回-1，否则返回1
Q_Data Q_Empty(LinkQueue Q) {
    if (Q.front->next == NULL)
        return 1;
    else
        return -1;
}
// 求队列的长度
Q_Data Q_Length(LinkQueue Q) {
    Q_Data i = 0;
    QNodePtr p;
    p = Q.front;
    //遍历队列中的节点，直到队尾等于队头
    while (Q.rear != p) {
        i++;
        p = p->next;
    }
    return i;
}
// 打印队列中的内容
void Q_Print(LinkQueue Q) {
    Q_Data i = 0;
    QNodePtr p;
    p = Q.front;
    while (Q.rear != p) {
        i++;
        cout << p->next->data << endl;
        p = p->next;
    }
}
// 若队列不空，则用e返回Q的队头元素，并返回1，否则返回-1
Q_Data Q_GetHead(LinkQueue Q, Q_Data &e) {
    QNodePtr p;
    if (Q.front == Q.rear)
        return -1;
    p = Q.front->next;
    e = p->data;
    return 1;
}
// 插入元素e为Q的新的队尾元素
void Q_Put(LinkQueue *Q, Q_Data e) {
    QNodePtr p = (QNodePtr)malloc(sizeof(QNode));
    if (!p) // 存储分配失败
        exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    //FIFO，将新节点追加到尾节点后面
    Q->rear->next = p;
    //将新的节点变成尾节点
    Q->rear = p;
}
// 若队列不空，删除Q的队头元素，用e返回其值，并返回1，否则返回-1
Q_Data Q_Poll(LinkQueue *Q,Q_Data &e) {
    QNodePtr p;
    if (Q->front == Q->rear)
        return -1;
    //取出头节点
    p = Q->front->next;
    //取出头节点的数据
    e = p->data;
    cout << e << endl;
    Q->front->next = p->next;
    if (Q->rear == p)
        Q->rear = Q->front;
    free(p);
    cout << e << endl;
    return 1;
}

什么是假溢出

假溢出就是系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为”假溢出”。
假设我们有一个非循环队列Q，队头指针为Q->front,队尾指针为Q->rear,长度为m，队列中元素在向量中的下标从0到m-1。
入队Q->rear++，出队Q->front++，现在入队m个元素到队列中，此时Q->front == 0，Q->rear == m，
现在出队m个元素，此时 Q->front == Q->rear == m，现在队列中已经没有元素，但此时再做入队操作时，就发生了”假溢出”。
下面举个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
cout << "初始化非循环队列" << endl;
Queue *Q = Q_Init();
//此时 Q->front == 0,Q->rear == 0;

cout << "插入数据（put）" << endl;
Q_Put(Q, 111);
Q_Put(Q, 222);
Q_Put(Q, 333);
Q_Put(Q, 444);
Q_Put(Q, 555);
//此时 Q->front == 0,Q->rear == 5;

cout << "取出并删除元素（poll）" << endl;
Q_Data head_data;
Q_Poll(Q,head_data);
Q_Poll(Q,head_data);
Q_Poll(Q,head_data);
Q_Poll(Q,head_data);
Q_Poll(Q,head_data);
//此时 Q->front == 5,Q->rear == 5;队列中没有数据

cout << "插入数据（put）" << endl;
Q_Put(Q, 666);
//此时 Q->front == 5,Q->rear == 5; 没有变化，Q_Put() 会返回 -1，也就是插入失败，这就发生了 "假溢出"

怎么解决假溢出

  1. 将队列看成首尾相连即循环队列

    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
    // 循环队列中有两种方法可以判断队空或队满
    // 1.“牺牲一个单元”，Q->front == Q->rear 时为队空，(Q->rear + 1) % MAX_QSIZE == Q->front 时为队满。
    // 2.“设标记”，如设标记tag，若出队时发生Q->front==Q->rear为队空，tag == 1；若入队时发生Q->front == Q->rear为队满，tag == 2。
    // 一般来说都是使用第1种方法，下面解析一下第一种方法。

    cout << "初始化循环队列" << endl;
    SqQueue *Q = Q_Init();
    //此时 Q->front == 0,Q->rear == 0;

    cout << "插入数据（put）" << endl;
    //入队时 Q->rear = (Q->rear + 1) % MAX_QSIZE
    Q_Data front_data;
    Q_Put(Q,111);
    Q_Put(Q,222);
    Q_Put(Q,333);
    Q_Put(Q,444);
    Q_Put(Q,555);
    //此时 Q->front == 0,Q->rear == 5;

    cout << "取出并删除元素（poll）" << endl;
    //出队时 Q->front = (Q->front + 1) % MAX_QSIZE
    Q_Data head_data;
    Q_Poll(Q,head_data);
    Q_Poll(Q,head_data);
    Q_Poll(Q,head_data);
    Q_Poll(Q,head_data);
    Q_Poll(Q,head_data);
    //此时 Q->front == 5,Q->rear == 5;队列中没有数据

    cout << "插入数据（put）" << endl;
    //入队时 Q->rear = (Q->rear + 1) % MAX_QSIZE
    Q_Put(Q,666);
    Q_Put(Q,777);
    Q_Put(Q,888);
    //此时 Q->front == 5,Q->rear == 2;队列三个元素

  2. 出队时将队列所有元素向前“平移”1位

    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
    cout << "初始化非循环队列" << endl;
    Queue *Q = Q_Init();
    //此时 Q->front == 0,Q->rear == 0;

    cout << "插入数据（put）" << endl;
    Q_Put(Q, 111);
    Q_Put(Q, 222);
    Q_Put(Q, 333);
    Q_Put(Q, 444);
    Q_Put(Q, 555);
    //此时 Q->front == 0,Q->rear == 5;

    //将非循环队列出列方法更改为如下
    // 出列 解决"假溢出"
    Q_Data Q_Poll_New(Queue *Q,Q_Data &e) {
        //如果当前元素数量等于最大数量 返回 -1
        if (Q->front == 0 || Q->front == MAX_QSIZE)
            return -1;
        e = Q->Array[Q->front];
        int x = MAX_QSIZE;
        while(x != 0){
            Q->Array[x-1] = Q->Array[x];
            x--;
        }
        Q->rear--;
        // 移出后減少1
        Q->length--;
        return 1;
    }

    cout << "取出并删除元素（poll）" << endl;
    //调用新出列方法
    Q_Data head_data;
    Q_Poll_New(Q,head_data);
    Q_Poll_New(Q,head_data);
    Q_Poll_New(Q,head_data);
    Q_Poll_New(Q,head_data);
    Q_Poll_New(Q,head_data);
    //此时 Q->front == 0,Q->rear == 0;队列中没有数据

    cout << "插入数据（put）" << endl;
    Q_Put(Q, 666);
    //此时 Q->front == 0,Q->rear == 1;队列中1个元素

总结

  • 非循环队列是最简单的队列，动态数组/数组实现，队列大小是固定，插入（入队）和查找（出队）快，可能会出现”假溢出”的情况。
  • 动态数组/数组实现，队列大小是固定，插入（入队）和查找（出队）快，不会出现”假溢出”。
  • 单链队列使用链表实现，不存在”假溢出”的问题，队列长度没有限制，插入和读取的时间代价较高。
Choice wechat
关注公众号，获取文章更新通知。
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！