初夏小谈：队列的基本操作（完整版）

队列的入队，出队等操作

队列的特点：先进先出。这种规则在我们生活中屡见不鲜。比如：中午吃饭时的窗口前排队，火车过隧道，各种业务办理排队等等。如果谁插队，大家就会向他（她）投向愤怒，鄙视的目光。甚至可能展开一场弥漫火药的战争。所以还是不要插队，否则后果很严重。

这就意味着队列只能在队尾增加数据，只能在队头删除数据。

由于队列的特点，如果用顺序表来实现时间复杂度会变成O(n),所以我采用链表的方式来实现队列。时间复杂度O(1)。

代码如下：

//队列特点：先进先出

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//队列的数据别名
#define DataType int

//定义队列类型
typedef struct Queue
{
	DataType data;
	struct Queue* next;
}Queue;

//1.创建结点
Queue* CreateQueueNode(DataType data);

//2.初始化
void InitQueue(Queue* Quptr);

//3.出队列
void DelQueueNode(Queue* Quptr);

//4.入队列
void AddQueueNode(Queue* Quptr, DataType data);

//5.销毁队列
void DestoryQueueNode(Queue* Quptr);

//6.打印队列
void PrintQueue(Queue* Quptr);

#include"Queue.h"

//1.创建结点
Queue* CreateQueueNode(DataType data)
{
	Queue* ptr = (Queue*)malloc(sizeof(Queue));
	ptr->data = data;
	ptr->next = NULL;
	return ptr;
}

//2.初始化
void InitQueue(Queue* Quptr)
{
	assert(Quptr);
	Quptr->data = 0;
	Quptr->next = NULL;
}

//3.出队列
void DelQueueNode(Queue* Quptr)
{
	assert(Quptr);
	if (Quptr->next == NULL)
	{
		return;
	}
	Queue* ptr = Quptr->next;
	Quptr->next = ptr->next;
	free(ptr);
	ptr = NULL;
}

//4.入队列
void AddQueueNode(Queue* Quptr, DataType data)
{
	assert(Quptr);
	Queue* pos = CreateQueueNode(data);
	Queue* ptr = Quptr->next;
	if (ptr != NULL)
	{
		while (ptr->next != NULL)
		{
			ptr = ptr->next;
		}
		ptr->next = pos;
	}
	else
	{
		Quptr->next = pos;
	}
}

//5.销毁队列
void DestoryQueueNode(Queue* Quptr)
{
	assert(Quptr);
	while (Quptr->next != NULL)
	{
		DelQueueNode(Quptr);
	}
}

//6.打印队列
void PrintQueue(Queue* Quptr)
{
	assert(Quptr);
	Queue* ptr = Quptr->next;
	if (ptr == NULL)
	{
		printf("空链表\n");
	}
	else
	{
		while (ptr != NULL)
		{
			printf("<-- %d ", ptr->data);
			ptr = ptr->next;
		}
		printf("\n");
	}
}

#include"Queue.h"

void Test()
{
	Queue* QPtr = (Queue*)malloc(sizeof(Queue));
	InitQueue(QPtr);

	//入队列
	AddQueueNode(QPtr, 5);
	PrintQueue(QPtr);
	AddQueueNode(QPtr, 6);
	PrintQueue(QPtr);
	AddQueueNode(QPtr, 7);
	PrintQueue(QPtr);
	AddQueueNode(QPtr, 8);
	PrintQueue(QPtr);
	AddQueueNode(QPtr, 9);
	PrintQueue(QPtr);

	//出队列
	DelQueueNode(QPtr);
	PrintQueue(QPtr);
	DelQueueNode(QPtr);
	PrintQueue(QPtr);

	//销毁队列
	DestoryQueueNode(QPtr);
	PrintQueue(QPtr);
}

int main()
{
	Test();
	system("pause");
	return 0;
}

结果显示：

<-- 5
<-- 5 <-- 6
<-- 5 <-- 6 <-- 7
<-- 5 <-- 6 <-- 7 <-- 8
<-- 5 <-- 6 <-- 7 <-- 8 <-- 9
<-- 6 <-- 7 <-- 8 <-- 9
<-- 7 <-- 8 <-- 9
空链表
请按任意键继续. . .
 

在实现队列中我采用的是头结点的方式操作队列，头指针当然也可以。           

                                                                                                                                                   珍&源码