【数据结构】带你认识队列--Queue_队列的基本介绍

---

一、队列的概念

队列是一种先进先出（FIFO）的数据结构，类似于现实中排队的场景。在队列中，数据从队尾进入，从队首出去。队列的操作包括初始化、销毁、入队、出队、获取队首元素、获取队尾元素以及检查队列是否为空等。

这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后，如下图所示。再比如用键盘进行各种字母或数字的输入，到显示器上如记事本软件上的输出，其实就是队列的典型应用，假如你本来和女友聊天，想表达你是我的上帝，输入的是god,而屏幕上却显示dog 发了出去，这真是要气死人了。

1.1 队列的基本特性

• 队列是线性数据结构，只允许在一端插入（队尾）和另一端删除（队首）。
• 数据元素进队列的过程称为入队，出队列的过程称为出队。
• 队列是先进先出的数据结构。

1.2 队列的存储结构

队列的存储结构可以通过顺序队列和链队列两种方式实现。

• 顺序队列使用数组存储，
• 链队列使用链表存储

二、队列的结点设计与初始化

在链队列中，结点是队列的基本构建单元。一个队列包含头指针和尾指针，它们分别指向队列的头部和尾部。

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13

2.1 队列的初始化

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8

2.2 判断队列是否为空

判断队列是否为空是一个简单而重要的操作，它可以通过检查队列的头指针是否为空来实现。

bool QueueEmpty(Queue* pq)
{
    assert(pq); // 检查指针是否为空

    return pq->head == NULL && pq->tail == NULL; // 如果头尾节点都为空，队列为空
}
1
2
3
4
5
6

2.3 入队操作

入队操作将一个新的元素插入到队列的尾部。在入队操作中，需要判断队列是否为空，然后根据情况调整队列的头指针和尾指针。

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq); // 检查指针是否为空

    QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 分配新节点内存
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }

    newnode->data = x;  // 赋值新节点数据
    newnode->next = NULL; // 新节点的下一个节点指向空

    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode; // 如果尾节点为空，头尾节点都指向新节点
    }
    else
    {
        pq->tail->next = newnode; // 尾节点的下一个节点指向新节点
        pq->tail = newnode; // 尾节点指向新节点
    }

    pq->size++; // 队列大小加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

2.4 出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素，则需将rear指向头结点，如下图所示。

void QueuePop(Queue* pq)
{
    assert(pq); // 检查指针是否为空
    assert(!QueueEmpty(pq)); // 检查队列是否为空

    if (pq->head->next == NULL)
    {
        free(pq->head); // 释放头节点内存
        pq->head = pq->tail = NULL; // 头尾节点指向空
    }
    else
    {
        QNode* del = pq->head; // 保存头节点
        pq->head = pq->head->next; // 头节点指向下一个节点

        free(del); // 释放节点内存
    }

    pq->size--; // 队列大小减1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.5 打印队列元素（遍历）

遍历操作用于打印队列的所有元素，可以帮助调试和验证队列的操作是否正确。

void printQueue(Queue *q) {
    Node *current = q->front;
    while (current != NULL) {
        printf("%d\t", current->data);
        current = current->next;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8

2.6 队列的销毁

通过遍历队列，释放每个节点的内存，并将队列头尾指针置为空，队列大小置零，完成了销毁队列的操作。在释放内存时，没有必要将del指针置为空，因为它在下一次循环中会被重新赋值。

void QueueDestroy(Queue* pq)
{
    assert(pq); // 检查指针是否为空

    QNode* cur = pq->head;
    while (cur)
    {
        QNode* del = cur;
        cur = cur->next;

        free(del); // 释放节点内存
        //del = NULL;  // 此行代码可以省略，因为del在下一次循环中会被重新赋值
    }

    pq->head = pq->tail = NULL; // 头尾节点指向空
    pq->size = 0; // 队列大小为0
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.6 队头和队尾

// 返回队头元素
QDataType QueueFront(Queue* pq)
{
    assert(pq); // 检查指针是否为空
    assert(!QueueEmpty(pq)); // 检查队列是否为空

    return pq->head->data; // 返回头节点的数据
}

// 返回队尾元素
QDataType QueueBack(Queue* pq)
{
    assert(pq); // 检查指针是否为空
    assert(!QueueEmpty(pq)); // 检查队列是否为空

    return pq->tail->data; // 返回尾节点的数据
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.7 顺序队列的假溢出

顺序队列可能会发生假溢出的问题，即队列的物理空间没有满，但由于出队操作导致队列头指针偏移，无法继续入队。这时，可以通过重新整理队列的存储空间来解决。

void fakeOverflow(Queue *q) {
    if (!isEmpty(q)) {
        Node *temp = q->head;
        q->head = q->tail = NULL;
        while (temp != NULL) {
            enqueue(q, temp->data);
            Node *next = temp->next;
            free(temp);
            temp = next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

结语

通过以上介绍，我们了解了队列的基本概念和实现方法，并实现了队列的初始化、判断是否为空、入队、出队、遍历等基本操作。队列作为一种常见的数据结构，在计算机科学中有着广泛的应用，特别是在广度优先搜索、任务调度等场景。希望这篇文章能够帮助你更好地理解和使用队列。