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

?作者: FlashRider

?专栏: 数据结构

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

什么是队列？

选择什么结构来实现队列？

链式队列的实现

队列的结构体实现

队列需要的函数声明

队列的函数实现

测试代码

什么是队列？

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

选择什么结构来实现队列？

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

文章来源地址https://uudwc.com/A/5LnJ

那么我们选用单链表，还是双链表来实现队列？
如果我们选择双向链表来实现队列，在进行插入删除的时候会非常轻松，但是总有一种大材小用的感觉。如果我们选用单链表实现队列，我们就要实现头删和尾插，但是尾插需要找尾，这对于单链表来说是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;
}

运行结果：

如果这篇博客对您有帮助的话，请记得点个赞或者三连。