队列的模拟实现

队列的模拟实现

前言

​ 在程序设计中，数据结构是不可或缺的基础，而STL（Standard Template Library）作为C++中的重要组成部分，提供了丰富的数据结构和算法。本篇博客将带领大家一起深入探讨如何用C语言模拟实现STL中队列的所有功能。

一、队列的基本原理

1）队列的定义

队列是一种先进先出（FIFO）的数据结构，类似于现实生活中排队的场景。在队列中，新元素被添加到队尾，而只有队首的元素才能被移除。

2）队列的特性

队列的主要特性包括入队、出队、判空、获取大小、获取队首和队尾元素等操作。这些操作构成了队列的基本功能，我们将通过C语言实现这些功能，并详细解析代码。

3）队列的应用场景

队列在计算机科学中有着广泛的应用，例如任务调度、缓冲区管理、广度优先搜索等。深入了解队列的基本原理有助于我们更好地应用它解决实际问题。

二、模拟实现STL中队列的功能

对照STL中 queue 的特性实现各个功能函数：

1）设计数据结构

​ 我们将使用两个结构体 QNode 和 Queue ，来构建队列。QNode表示队列中的节点，而Queue则是队列本身，包含队首、队尾指针以及队列大小。

​ 首先声明该队列由单链表实现，由于需要首尾同时低时间复杂度操作，所以在避免双向循环链表的空间浪费前提下选择了单链表实现，同时为了首尾以O(1)操作特别添加了指向队列（单链表）首尾的指针。

typedef int QNodeType;

typedef struct QNode
{
   
	QNodeType val;
	struct QNode* next;
}QNode;

typedef struct Queue
{
   
	QNode* front;
	QNode* tail;
	size_t size;
}Queue;

2）初始化队列（QueueInit）

在 QueueInit 函数中，我们将队首、队尾指针初始化为NULL，队列大小初始化为0。

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

	q->front = NULL;
	q->tail = NULL;
	q->size = 0;
}

3）入队操作（QueuePush）

QueuePush 函数负责将新元素入队。我们通过动态分配内存创建一个新节点，根据队列是否为空选择更新队首或队尾指针，并增加队列大小。

void QueuePush(Queue* q, QNodeType x)
{
   
	assert(q);

	QNode* node = (QNode*)malloc(sizeof(Queue));
	if (!node) {
    perror("QueuePush::malloc"); return; }

	node->next = NULL;
	node->val = x;

	if (q->size == 0)
	{
   
		q->front = q->tail = node;
	}
	else
	{
   
		q->tail->next = node;
		q->tail = q->tail->next;
	}
	q->size++;
}

4）出队操作（QueuePop）

QueuePop 函数负责将队首元素出队。我们释放队首节点的内存，更新队首指针，并更新队列大小。特别注意，要避免单节点时删除头结点后，尾指针变为野指针的情况。

void QueuePop(Queue* q)
{
   
	assert(q);
	assert(q->size != 0);	// pop时保证队列非空

	QNode* tmp = q->front->next;
	free(q->front);      // 删除节点
	q->front = tmp;

	if (q->size == 1) {
    q->tail = NULL; }     // 避免单节点时删除头结点后，尾指针变为野指针

	q->size--;
}

5）判空操作（QueueIs_empty）

QueueIs_empty 函数用于判断队列是否为空，通过队列大小是否为0来实现。

bool QueueIs_empty(const Queue* q)
{
   
    assert(q);
    return (q->size == 0);
}

6）获取队列大小（QueueSize）

QueueSize 函数返回队列的大小。

size_t QueueSize(const Queue* q)
{
   
    assert(q);
    return q->size;
}

7）获取队首和队尾元素（QueueFront，QueueBack）

QueueFront 和 QueueBack 函数分别返回队列的队首和队尾元素值，确保队列非空。

QNodeType QueueFront(const Queue* q)
{
   
    assert(q);
    assert(q->size != 0);
    return q->front->val;
}

QNodeType QueueBack(const Queue* q)
{
   
    assert(q);
    assert(q->size != 0);
    return q->tail->val;
}

8）销毁队列（QueueDestory）

QueueDestory 函数用于销毁队列，释放所有节点的内存。

void QueueDestory(Queue* q)
{
   
    assert(q);

    QNode* cur = q->front;
    while (cur)
    {
   
        QNode* tmp = cur->next;
        free(cur);
        cur = tmp;
    }

    q->size = 0;
}

三、测试队列

测试代码：

void test()
{
   
	Queue q;

	QueueInit(&q);

	QueuePush(&q, 10);
	QueuePush(&q, 9);
	QueuePop(&q);
	QueuePush(&q, 8);
	QueuePush(&q, 7);
	QueuePush(&q, 6);

	QueuePop(&q);

	while (!QueueIs_empty(&q))
	{
   
		printf("%d\t", QueueFront(&q));
		printf("(%d)\t", QueueBack(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestory(&q);
}

运行结果：

功能测试结果与预期一致，同时并未发现内存泄漏，说明销毁队列也符合要求。

总结

​ 在实现队列的过程中，尤其注意逻辑成立的问题和程序鲁棒性增强，比如执行 QueuePop 操作时首先队列需非空，其次注意队列中只剩单个元素的情况下删除节点后记得安置尾指针，避免野指针存在的隐患。

​ 我们深入学习了队列的基本原理，并通过C语言实现了STL中队列的所有功能。我们详细解析了每个函数的实现细节，包括初始化、入队、出队等操作。队列作为一种重要的数据结构，在计算机科学中有着广泛的应用，对其深入了解有助于我们更好地解决实际问题。

​ 在实现队列的过程中，尤其注意逻辑成立的问题和程序鲁棒性增强，比如执行 QueuePop 操作时首先队列需非空，其次注意队列中只剩单个元素的情况下删除节点后记得安置尾指针，避免野指针存在的隐患。

​ 我们深入学习了队列的基本原理，并通过C语言实现了STL中队列的所有功能。我们详细解析了每个函数的实现细节，包括初始化、入队、出队等操作。队列作为一种重要的数据结构，在计算机科学中有着广泛的应用，对其深入了解有助于我们更好地解决实际问题。