LV050-链式队列简介

一、链式队列

1. 存储结构

链式队列的存储结构如下图所示，将从队尾入队，队头出队：

相对于顺序队列，链式队列没有假溢出，因为它不会满，链式队列入队操作会申请内存新建节点，出队会释放相应节点，动态存储，只要能成功申请内存创建新的节点，链式队列就不会满，所以不涉及溢出和队满的情况。（当然了，内存不够的时候也还是会满的啦，不过这个时候就可能需要考虑换更大空间的内存啦，哈哈哈。）

2. 结构体实现

对于链式队列，还是借助单链表来实现，然后我们再添加头尾指针指向头尾就好啦。

/* 自定义数据类型 */
typedef int data_t; /* 定义栈中数据元素的数据类型 */

typedef struct slqueue_node 
{
	data_t data;
	struct slqueue_node *next;
}slqueuenode, * slqueuelink;

typedef struct 
{
	slqueuelink front;
	slqueuelink rear;
}slqueue_sq;

【说明】单链表实现的队列，英文名字是 single linked list queue ，所以我后边都用 slqueue 作为链式队列结构体及函数命名的关键词啦。

3. 链式队列基本操作

相关源代码可以在这里下载：

数据结构	队列 (密码: 6sez)

3.1 创建

• （1）链式队列结构体变量 lq 申请内存(包含两个成员： front 和 rear )；
• （2）申请一个单链表结构体变量 Head 申请内存空间，也就是头节点的内存空间；
• （3）队列结构体指针变量成员的首尾指针均指向 Head ；
• （4）初始化单链表结构体变量成员

【注意】（2）、（3）两步可合并，省去 Head 变量的定义即有：

lq->front = lq->rear = (slqueuelink)malloc(sizeof(slqueuenode));

创建链式队列的函数如下所示：

/**
 * @Function: slqueue_create
 * @Description: 链式队列创建
 * @param   : none
 * @return  : 返回一个地址
 *            NULL, 创建失败;
 *            other, 创建成功
 */
slqueue_lq * slqueue_create() 
{
	/* 定义一个链式队列的结构体指针变量 */
	slqueue_lq *lq;
	/* 1. 申请链式队列结构体变量的内存空间(头尾指针内存空间) */
	lq = (slqueue_lq *)malloc(sizeof(slqueue_lq));
	/* 2. 判断链式队列结构体指针变量内存是否申请成功 */
	if(lq == NULL)
	{
		printf("single linked list queue malloc failed!\n");
		return NULL;
	}
	/* 3. 申请一个节点的内存空间(相当于申请一个链表头节点) */
	lq->front = lq->rear = (slqueuelink)malloc(sizeof(slqueuenode));
	/* 4. 判断节点是否申请成功 */
	if(lq->front == NULL)/* front 和 rear 开始都指向头节点, 用谁都可以 */
	{
		printf("single linked list queue node malloc failed!\n");
		free(lq);/* 释放掉之前申请的链式队列结构体指针变量内存空间 */
		return NULL;
	}
	/* 5. 初始化头节点 */
	lq->front->data = 0;
	lq->front->next = NULL;
	
	return lq;
}

3.2 入队

我们从链表尾进行入队操作：

/**
 * @Function: slqueue_enqueue
 * @Description: 链式队列入队
 * @param lq: 链式队列地址
 * @param value: 要入队的数据
 * @return  : 返回一个数值
 *            0, 入队成功;
 *            -1, 链式队列不存在或者新建节点失败
 */
int slqueue_enqueue(slqueue_lq *lq, data_t value) 
{
	/* 定义一个链式队列节点的结构体指针变量 */
	slqueuelink p;
	/* 1. 判断链式队列是否存在 */
	if(lq == NULL)
	{
		printf("single linked list queue is not existed!\n");
		return -1;
	}
	/* 2. 申请入队节点内存空间 */
	p = (slqueuelink)malloc(sizeof(slqueuenode));
	/* 3. 判断节点是否申请成功 */
	if(p == NULL)
	{
		printf("single linked list queue node malloc failed!\n");
		return -1;
	}
	/* 4. 初始化新申请的节点 */
	p->data = value;
	p->next = NULL;
	/* 5. 尾部插入节点实现入队 */
	lq->rear->next = p;
	lq->rear = p;/* 尾节点指针移动，p 成为新的尾节点 */
	
	return 0;
}

3.3 出队

我们将从链表头位置出队，由于我们创建的链表是有头节点的，头节点仅仅是代表这个队列的地址，所以每一次出队我们表面上是将数据出队，实际上这个数据还存在于出队后的头节点中，释放的空间也是出队前头节点的空间：

【注意】这里出队的时候不要做队列是否存在以及是否为空的判断，这两个判断若是有返回值的话程序会认为返回值就是出队的元素，所以队列的存在性以及是否为空，要在使用出队函数前进行判断。

/**
 * @Function: slqueue_dequeue
 * @Description: 链式队列出队
 * @param lq: 链式队列地址
 * @return  : 返回一个出队的元素
 *            0, 入队成功;
 *            -1, 链式队列不存在或者新建节点失败
 */
data_t slqueue_dequeue(slqueue_lq *lq) 
{
	/* 定义一个链式队列节点的结构体指针变量 */
	slqueuelink p;
	/* 1. 判断链式队列是否存在 */
	/* 此步骤需要在函数外判断，因为这里返回的话，会认为返回值是出队的数据 */
	/* 2. 判断链式队列是否为空 */
	/* 此步骤需要在函数外判断，因为这里返回的话，会认为返回值是出队的数据 */
	/* 3. 出队 */
	p = lq->front;
	lq->front = p->next;/* 下一个节点将成为头指针 */
	/* 3. 释放出队的节点的上一个节点空间 */
	free(p);
	p = NULL;
	
	return (lq->front->data);
}

3.4 释放

释放的方式与出队一样，只是需要将所有节点出队，并且释放掉最后一个头节点，如下图所示：

/**
 * @Function: slqueue_free
 * @Description: 链式队列释放
 * @param lq: 链式队列地址
 * @return  : 返回一个 NULL
 *            NULL, 释放完成
 */
slqueue_lq * slqueue_free(slqueue_lq *lq) 
{
	/* 定义一个链式队列节点的结构体指针变量 */
	slqueuelink p;
	/* 1. 判断链式队列是否存在 */
	if(lq == NULL)
	{
		printf("single linked list queue is not existed!\n");
		return NULL;
	}
	/* 2. 释放所有节点空间 */
	printf("single linked list queue free:");
	while(lq->front)
	{
		p = lq->front;
		lq->front = p->next;/* 下一个节点成为新的头节点 */
		printf("%d ", p->data);
		free(p);
	}
	puts("");
	/* 3. 释放链式队列的内存空间(front 和 rear 指针) */
	free(lq);
	lq = NULL;
	
	return NULL;
}

3.5 清空

清空的过程，也是将所有节点出队，只不过不释放最后一个节点：

/**
 * @Function: slqueue_clear
 * @Description: 链式队列清空
 * @param lq: 链式队列地址
 * @return  : 返回一个数值
 *            0, 清空完成;
 *            -1, 链式队列不存在
 */
int slqueue_clear(slqueue_lq *lq) 
{
	/* 定义一个链式队列节点的结构体指针变量 */
	slqueuelink p;
	/* 1. 判断链式队列是否存在 */
	if(lq == NULL)
	{
		printf("single linked list queue is not existed!\n");
		return -1;
	}
	/* 2. 清空链式队列 */
	printf("single linked list queue clear free:");
	while(lq->front->next != NULL)/* 结束条件是剩余一个节点 */
	{
		p = lq->front;
		lq ->front = p->next;
		printf("%d ", p->data);
		free(p);
		p = NULL;
	}
	puts("");
	return 0;
}

3.6 显示

此函数将显示所有节点的数据，包括头节点。

/**
 * @Function: slqueue_show
 * @Description: 链式队列所有节点显示(包括头节点)
 * @param lq: 链式队列地址
 * @return  : 返回一个数值
 *            0, 显示完成;
 *            -1, 链式队列不存在
 */
int slqueue_show(slqueue_lq *lq) 
{
	/* 定义一个链式队列节点的结构体指针变量 */
	slqueuelink p;
	/* 1. 判断链式队列是否存在 */
	if(lq == NULL)
	{
		printf("single linked list queue is not existed!\n");
		return -1;
	}
	/* 2. 遍历链式队列 */
	p = lq->front;
	printf("single linked list queue:");
	while(p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	puts("");
	return 0;
}

3.7 判空

此函数将显示所有节点的数据，包括头节点。

/**
 * @Function: slqueue_empty
 * @Description: 链式队列是否为空
 * @param lq: 链式队列地址
 * @return  : 返回一个数值
 *            0, 链式队列非空;
 *            1, 链式队列为空;
 *            -1, 链式队列不存在
 */
int slqueue_empty(slqueue_lq *lq) 
{
	/* 1. 判断链式队列是否存在 */
	if(lq == NULL)
	{
		printf("single linked list queue is not existed!\n");
		return -1;
	}
	/* 2. 判断 front 和 rear 是否相等 */
	if(lq->front == lq->rear)
		return 1;
	else
		return 0;
	/* 或者可以写成下边的情况 */
	// return (lq-> front == lq-> rear ? 1 : 0);
}