[C语言实现]数据结构之《关于我转生成队列这档事》

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

作者: FlashRider

专栏: 数据结构

知识概要详解队列的概念、顺序队列和链式队列的优点和缺点以及代码实现。

什么是队列

队列其实就是一种操作受限的线性表即只能在表头弹出表尾插入。
我们把数据的删除端称为队头把数据的插入端称为队尾。
生活中我们在食堂打饭排队的时候从队尾进入队列我们前面的人打完饭后从队头离开队列。
由此可见队列这种结构也是非常重要的在生活中随处可见。

选择什么结构来实现队列

我们需要对队列进行插入删除操作的时候都是从队尾插入队头删除因此我们选用链式结构来实现队列链表实现队列如果我们采用顺序结构顺序表来实现队列的话在删除之后就要进行大量的数据挪动如果不挪动就会造成一定程度的空间浪费。

那么我们选用单链表还是双链表来实现队列
如果我们选择双向链表来实现队列在进行插入删除的时候会非常轻松但是总有一种大材小用的感觉。如果我们选用单链表实现队列我们就要实现头删和尾插但是尾插需要找尾这对于单链表来说是O(n)的时间复杂度因此我们新建一个结点tail来存储尾结点这样尾插就是O(1)了。

链式队列的实现

需要的头文件 stdlib.h stdbool.h assert.h stdio.h

队列的结构体实现

//队列元素类型 
typedef int QDataType;
//链式队列结点
typedef struct QueueNode
{
	QDataType x;
	struct QueueNode* next;
}QNode;
//队列 
typedef struct Queue
{
	QNode* front;//队头
	QNode* tail;//队尾 
}Queue;

队列需要的函数声明

首先是老四样初始化、插入删除、获取长度、销毁。
其次还有判空、获取队头元素、获取队尾元素。

void QueueInit(Queue* pq);//初始化队列 
void QueuePush(Queue* pq, QDataType x);//队尾插入元素
void QueuePop(Queue* pq);//删除队头元素
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//获取队列长度
QDataType QueueFront(Queue* pq);//获取队头元素 
QDataType QueueBack(Queue* pq);//获取队尾元素 
void QueueDestroy(Queue* pq);//销毁队列

队列的函数实现

//初始化队列 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->front = pq->tail = NULL;
}
//队尾插入元素 
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//如果队列为空 front也会改变 所以特判 
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if(pq->front == NULL)
		pq->front = pq->tail = newnode;
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
}
//删除队头元素 
void QueuePop(Queue* pq)
{
	assert(!(QueueEmpty(pq)));
	//如果只有一个元素 tail也会改变 所以特判
	QNode* del = pq->front;
	if(pq->front == pq->tail)
		pq->front = pq->tail = NULL;
	else pq->front = pq->front->next;
	free(del);
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->front == NULL;
}
//获取队列长度 
int QueueSize(Queue* pq)
{
	assert(pq);
	int cnt = 0;
	QNode* cur = pq->front;
	while(cur)
	{
		cnt++;
		cur = cur->next;
	}
	return cnt;
}
//获取队头元素 
QDataType QueueFront(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->front->data;
}
//获取队尾元素 
QDataType QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
//销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->front;
	while(cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->front = pq->tail = NULL;
}

测试代码

int main(void)
{
	Queue q;
	QueueInit(&q);
	printf("插入前QueueIsEmpty >> %d (1真0假)\n", QueueEmpty(&q));
	printf("插入后QueueSize >> %d\n\n", QueueSize(&q));
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	printf("插入后QueueIsEmpty >> %d (1真0假)\n", QueueEmpty(&q));
	printf("插入后QueueSize >> %d\n\n", QueueSize(&q));
	while(!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	printf("全部弹出后QueueIsEmpty >> %d (1真0假)\n", QueueEmpty(&q));
	printf("全部弹出后QueueSize >> %d\n", QueueSize(&q));
	return 0;
}

运行结果