初阶数据结构【队列及其接口的实现】

目录

• 前言
• 一、队列的概念及结构
• 二、队列的实现方式
• 三、队列的实现
• • 3.1 基本结构
  • 3.2 队列基本功能接口
  • • 初始化队列
    • 销毁队列
  • 3.3 入队列接口
  • 3.4 出队列接口
  • 3.5 队列的其它接口
  • • 获取队列头部元素
    • 获取队列队尾元素
    • 检测队列是否为空
    • 获取队列中有效元素个数
  • 3.6 测试
• 总结

前言

上一期我们讲到了栈，这期我们继续讲解与其相似的结构——队列

一、队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头；

二、队列的实现方式

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些；

因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

三、队列的实现

3.1 基本结构

由于这里我们用链表实现队列的结构，所以我们先要创建链表节点的结构体：

typedef struct QueueNode
{
	QDataType _data;
	struct QueueNode* _next;
}QueueNode;

我们再创建队列结构体：

typedef struct Queue
{
	QueueNode* _head;
	QueueNode* _tail;
}Queue;

我们通过这样结构体来改变里面的_head或_tail指针的值就可以避免传二级指针；

3.2 队列基本功能接口

初始化队列

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->_head = NULL;
	q->_tail = NULL;
}

销毁队列

// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QueueNode* cur = q->_head;
	while (cur)
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_head = NULL;
	q->_tail = NULL;
}

3.3 入队列接口

注：由于队列只有这个接口需要创建节点，所以我们不再写创建节点接口；

这个接口我们要考虑队列为空的情况：

// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QueueNode* newnode = (QDataType*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->_data = x;
	newnode->_next = NULL;
	if (q->_head == NULL) //当队列为空时
	{
		q->_head = newnode;
		q->_tail = newnode;
	}
	else
	{
		q->_tail->_next = newnode;
		q->_tail = newnode;
	}
}

3.4 出队列接口

这个接口我们要注意当只有一个节点的时候，删除后防止_tail为野指针，所以也要将其置空；

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_head->_next != NULL); //防止队列为空
	QueueNode* next = q->_head->_next;
	free(q->_head);
	q->_head = next;

	if (q->_head == NULL)
	{
		q->_tail = NULL;
	}
}

3.5 队列的其它接口

获取队列头部元素

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_head);
	return q->_head->_data;
}

获取队列队尾元素

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_tail);
	return q->_tail->_data;
}

检测队列是否为空

// 检测队列是否为空，如果为空返回非零结果1，如果非空返回0 
QDataType QueueEmpty(Queue* q)
{
	assert(q);
	return q->_head == NULL ? 1 : 0;
}

获取队列中有效元素个数

QDataType QueueSize(Queue* q)
{
	assert(q);
	QueueNode* cur = q->_head;
	QDataType size = 0;
	while (cur)
	{
		size++;
		cur = cur->_next;
	}
	return size;
}

3.6 测试

void QueueTest()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);

	printf("%d ", QueueFront(&q));
	QueuePop(&q);

	QueuePush(&q, 3);
	QueuePush(&q, 4);

	//遍历
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
}

测试结果：

与预想结果一致，符合；

总结

这期我们用C语言实现了队列的基本操作，我们发现队列与栈有很多相似的地方，在实际应用中我们灵活运用；下期见；
26考研加油！