欢迎来到代码驿站!

C代码

当前位置:首页 > 软件编程 > C代码

C语言超详细讲解队列的实现及代码

时间:2022-09-24 10:20:47|栏目:C代码|点击:

前言

队列的概念

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

队列和前文所学的栈还是有一定区别的,队列明确指出先进先出。假如说一个队列的入队顺序为A B C D,那么出队顺序一定为A B C D,因为无论你是在A进去再出来,然后B进去再出来接着CD进去再出来或者类似的,都不会影响它最终的出队顺序A B C D。这点和栈还是有区别的,毕竟栈是后进先出。

队列的结构

队列的应用场景

队列:

  • 公平排队
  • 广度优先遍历 ……

栈:

  • 解决括号匹配
  • 逆波兰表达式求解
  • 递归改非递归 ……

队列的实现

  • 在实现之前,首先得考虑用哪种结构好,是用数组结构还是链式结构呢?上文的栈我们使用的是数组结构,难道队列也要用吗?
  • 其实不然。应该使用链式结构。前文栈删除数据不需要挪动数据,使用数组结构即可满足需求,而队列在删除数据时需要把后面的数据挪到前面,使用链式结构非常容易实现,只需改变节点指向即可,而数组结构想要实现挪动数据则非常麻烦。综上,使用链式结构是最优的。此外,单链表即可满足需求,不需要使用其余较为复杂的链式结构。

创建队列结构

思路:

这里要定义两个结构体,除了要定义1个链式结构来记录各个节点外,还要定义一个结构来记录队头和队尾。以此方便后续的队尾入数据,队头出数据。

Queue.h 文件:

//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型,本文以int为例
 //创建队列节点
typedef struct QueueNode
{
	QDataType data; //存储数据
	struct QueueNode* next; //记录下一个节点
}QNode;
 //保存队头和队尾
typedef struct Queue
{
	QNode* head; //头指针
	QNode* tail; //尾指针
}Queue;

队列初始化  

思路:

队列可以为空,但是管理头指针和尾指针的结构体不能为空,所以一开始就要断言。其次,在插入数据前,队列肯定是空的,所以直接把头指针和尾指针置空即可。

Queue.h 文件:

//初始化队列
void QueueInit(Queue* pq);

Queue.c 文件:

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

队列销毁  

思路:

销毁队列就是把队列的每个数据都销毁掉,那么需要遍历链表进行挨个销毁free。首先定义一个cur指针为pq->head,用来保存第一个数据,遍历cur,如果不为空,就free。最后把tail和head置空即可。

Queue.h 文件:

//销毁队列
void QueueDestory(Queue* pq);

Queue.c 文件:

//销毁队列
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;
}

入队列  

思路:

入队列其实很简单,只需要尾插即可,首先要新创建一个节点来保存新插入的数据。但是在尾插之前要考虑如果一开始队列没有数据,为空,那么只需要把head和tail节点指向新节点newnode节点即可。相反的,如果一开始就有数据,那么只需正常尾插把tail的next指向新节点newnode,再把newnode赋给tail即可。

Queue.h 文件:

//入队列
void QueuePush(Queue* pq, QDataType x);

 Queue.c 文件:

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建一个新节点保存数据
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力检测newnode,因为malloc的都要检测
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一开始没有数据,为空的情况
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

出队列  

思路:

特殊情况:

这里在删除数据时,首先要考虑特殊情况,当删到只剩一个数据时,再删一次,此时数据是没了,不过head为空了,而tail变成野指针了,为了避免此现象的产生,单独讨论并置空head和tail即可。

一般情况:

此时只需要定义一个next指针保存head的下一个节点,将head移动到next即可,并把旧的head置空。

 Queue.h 文件:

//出队列
void QueuePop(Queue* pq);

Queue.c 文件:

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能为空
	//特殊:当删到head=tail的位置时
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情况
	else
	{
		//保存head的下一个节点
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

队列判空  

思路:

如果head为空或者tail为空都是判空的条件,直接返回即可。

Queue.h 文件:

//判空
bool QueueEmpty(Queue* pq);

Queue.c 文件:

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

获取队列元素个数  

思路:

求元素个数其实不难,只需要定义一个cur指针为第一个数据pq->head,定义变量size来记录个数。依次遍历cur,不为空,size就++。这种遍历的思想不复杂,但时间复杂度达到O(N),不是太好,想要O(1)的话可以直接在当初定义结构体时多定义一个size变量,专门用来记录有效元素个数,每次入队列size++,出队列size--。这样实现是比较好的,不过为了封装成一个独立模块,还是采用遍历的方式。如下:

Queue.h 文件:

//获取有效元素个数
size_t QueueSize(Queue* pq);

Queue.c 文件:

//获取有效元素个数
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

获取队列头部元素  

思路:

首先要断言头部不能为空,如果头部都为空了,那还怎么能获得头部元素,其次直接返回头部head的数据即可。

Queue.h 文件:

//获取队头元素
QDataType QueueFront(Queue* pq);

Queue.c 文件:

//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //头部不能为空
	return pq->head->data;
}

获取队列尾部元素  

思路:

有了获取队头元素的经验,队尾就更简单了,把head换位tail即可,结构与上文一样。

Queue.h 文件:

//获取队尾元素
QDataType QueueBack(Queue* pq);

Queue.c 文件:

//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能为空
	return pq->tail->data;
}

总代码

Queue.h 文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型,本文以int为例
 //创建队列节点
typedef struct QueueNode
{
	QDataType data; //存储数据
	struct QueueNode* next; //记录下一个节点
}QNode;
 //保存队头和队尾
typedef struct Queue
{
	QNode* head; //头指针
	QNode* tail; //尾指针
}Queue;
 
//初始化队列
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);

Queue.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
 
//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
 
//销毁队列
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;
}
 
//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建一个新节点保存数据
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力检测newnode,因为malloc的都要检测
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一开始没有数据,为空的情况
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
 
//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能为空
	//特殊:当删到head=tail的位置时
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情况
	else
	{
		//保存head的下一个节点
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
 
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
 
//获取有效元素个数
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
 
//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //头部不能为空
	return pq->head->data;
}
 
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能为空
	return pq->tail->data;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	//插入数据
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	//打印
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
}
int main()
{
	TestQueue();
	return 0;
}

上一篇:基于C++泛型编程职工管理系统

栏    目:C代码

下一篇:如何利用Matlab绘制出好看的火山图

本文标题:C语言超详细讲解队列的实现及代码

本文地址:http://www.codeinn.net/misctech/214573.html

推荐教程

广告投放 | 联系我们 | 版权申明

重要申明:本站所有的文章、图片、评论等,均由网友发表或上传并维护或收集自网络,属个人行为,与本站立场无关。

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:914707363 | 邮箱:codeinn#126.com(#换成@)

Copyright © 2020 代码驿站 版权所有