数据结构：栈和队列（下）

代码汇总见：登录 - Gitee.com

上篇文章：数据结构：栈和队列（上）-CSDN博客

1.队列

1.1概念与结构

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

队列的底层结构选型：

队列的实现一般可以使用数组或者链表实现，相对而言，链表的结构实现更优一些。

原因：数组实现队列：插入数据为O(1)，删除数据为O(N);链表实现队列：插入数据为O(n)，删除数据为O(1)。但是若对于链表的队尾加入一个指针，那么其插入数据就会为O(1)，所以链表更优。

1.2队列的实现

1.2.1队列结构的定义

typedef int QDataType;
//定义结点结构
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue {
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
}Queue;

1.2.2初始化

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
}

调用测试：

1.2.3入队

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空
	if (pq->phead = NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
}

调用测试：

1.2.4队列判空

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

1.2.5出队

//出队列，队头
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//只有一个结点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
}

调用测试：

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

QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);

1.2.6取队头数据

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

1.2.7取队尾数据

QDataType QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

调用测试：

printf("对头：%d\n", QueueFront(&q));
printf("对尾：%d\n", QueueBack(&q));

1.2.8队列有效元素个数

代码：

//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->phead;
	int size = 0;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

调用测试：

	printf("size:%d\n", QueueSize(&q));

不过，这样的时间复杂度为O(N)，为提升效率，进行如下优化：

修改队列结构：

//定义队列的结构
typedef struct Queue {
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
	int size;//队列中的有效个数
}Queue;

再对初始化，入队和出队都加入pq->size，最终可简化为：

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

1.2.9销毁队列

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->phead;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

本章完。