目录

1.队列

1.1队列的概念及结构

2.队列的实现

2.1接口

3.接口的实现

3.1初始化

3.2销毁

分析：

 3.3入队

分析：

3.4出队

分析：

 3.5判断是否为空

3.6队列的大小

3.7返回头结点的元素Data

3.8返回尾结点的元素Data

4.完整代码

5.测试

测试结果：

1.1队列的概念及结构

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

 

2.队列的实现 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低

2.1接口

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//判断是否为空
bool QueueEmpty(Queue* pq);
//队的大小
size_t QueueSize(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

3.接口的实现

3.1初始化

初始化只需要让pq->head和pq->tail为NULL即可。

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

3.2销毁

//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

分析：

我们需要创建一个cur指针保存head的地址，以及一个next指针保存cur的next地址

过程：

1、我们free(cur)，再让cur走到next位置即可开始循环销毁。

2、循环结束的条件是当cur为空时。

3、循环结束后也一定要让head和tail置NULL。

 3.3入队

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode =(QNode*)malloc(sizeof(QNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	
}

分析：

入队需要考虑两种情况，第一种情况是队为空，第二种情况为队不为空。

情况一：队为空

如果队为空，我们就需要让pq->head 和 pq->tail 都等于newnode。

情况二：队不为空

如果队不为空，我们需要让pq->tail的next指向newnode，再让pq->tail往后走，走到newnode的位置。

3.4出队

//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);
	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

分析：

如果要出队的话，根据对的性质，就当于是头删

过程：

1、创建一个next用来保存head的下一个节点的地址，我们free(head)，再让head等于我们的next。

2、如果出队到只剩一个节点，也就是pq->head->next == NULL(pq->head == pq->tail)，我们free掉pq->head之后要将pq->head 和 pq->tail 置NULL。

 3.5判断是否为空

 直接判断头是否为空，如果头为空说明队列为空

//判断是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

3.6队列的大小

定义一个size变量，遍历一遍队列，每次走一步让size++即可。

//队的大小
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

3.7返回头结点的元素Data

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

3.8返回尾结点的元素Data

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);
	return pq->tail->data;
}

4.完整代码

2022_03_26 -- 队列/2022_03_26 -- 栈和队列 · 李兴宇/数据结构 - 码云 - 开源中国 (gitee.com)

5.测试

void TestQueue()
{
	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");
}

int main()
{
	//TestStack();
	TestQueue();
	return 0;
}

测试结果：

 （本篇完）