当前位置:   article > 正文

c语言实现队列

c语言实现队列


前言

栈的特点是元素后进先出(Last In First Out),而对应的还有一种数据结构,该结构的特点是先进先出(First In First Out),即为队列。

一、队列的特征

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

二、队列的实现

1、队列的设计

队列可以使用数组或链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。因为队列需要尾插头删,当数组头删时,需要全部元素向前移动一位,时间复杂度为O(N),而使用链表来实现队列的话,头删和尾插元素的时间复杂度都是O(1)。

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

typedef int QDataType;
//队列的结点设计
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//创建一个Queue结构体变量,就相当于创建了一个队列,该结构体变量中存的有该队列的头结点地址,尾结点地址
//所以当有该结构体变量的地址时,可以通过该地址改变队列的头结点地址和尾结点地址,即改变head指针和tail指针。
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

2、队列的初始化

因为队列中需要有一个头指针用来记录队头结点的地址,一个尾指针用来记录队尾结点的地址。所以又创建了一个Queue结构体,该结构体中有两个QNode*类型的成员变量,即Queue结构体中定义了两个结构体指针变量,一个用来存储队列的队头结点的地址,一个用来存储队尾结点的地址。
结构体Queue里面就只有两个QNode * 类型的结构体指针,所以当想创建一个队列时,创建一个Queue类型的结构体变量s就好了,此时Queue类型的结构体变量s的成员head和tail里面存的都是随机的地址,所以需要初始化,则需要调用QueueInit()函数,并且将结构体变量s的地址传进去,因为只有传s的地址进去,函数里面才可以根据s的地址找到s的成员head和tail,然后才能改变head和tail里面存储的随机地址的值。
在这里插入图片描述

如果传的是s的话,那么函数的形参就设置为Queue pq,那么在函数中会临时创建一个Queue类型的结构体变量pq,然后将s的值拷贝到pq中,此时在函数中修改pq.head和pq.tail时,外面s的head和tail并不会改变,所以要传s的地址。
队列初始化就是通过s的地址 0x 1234找到s,然后改变s的成员变量head和tail的值为0x 0000。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在这里插入图片描述
在这里我们可以再看一下单链表的设计。
单链表中结构体的定义为

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

然后单链表在使用时,需要先创建一个SLTNode * 类型的结构体指针,然后再将该结构体指针的地址传入函数中。而函数中的形参都设计了二级指针来接收这个SLTNode * 类型的结构体指针的地址。这样设计是因为当单链表为空时,此时单链表的头结点指针ps就指向NULL,而当要给单链表插入元素时,如果只将ps传进去,那么在函数中形参只需设计为一级指针SLTNode*即可,但是这样设计的话,并不会改变ps的值,改变的只是函数中临时创建的和ps类型一致的一个指针变量的值。此时主函数的ps的值依旧为NULL,所以要向改变ps的值,只能将ps的地址传进去,然后函数中形参设计为二级指针,在函数中可以通过解引用ps的地址来找到ps,然后将ps的值设置为单链表结点的地址。
在这里插入图片描述
可以看到在前面的单链表中,我们用到了二级指针,但是为什么队列没有用二级指针呢?因为队列不止要有一个指针变量存储队头结点的地址,还需要一个指针变量来存储队尾结点的地址,而改变时需要改变存储队头结点的地址的指针head的值,也需要改变存储队尾结点的地址的指针tail的值。而改变这两个指针的值,就需要函数设计两个二级指针的形参,所以我们为了方便直接设计了一个结构体Queue,结构体的成员包含两个指针变量。
单链表的话就只需改变一个指向单链表头结点的指针的值,所以可以直接使用二级指针来实现。

3、元素的入队和出队

队列中元素在入队时我们要判断此时队列是否为空,如果队列为空的话,我们就需要将队头指针和队尾指针都指向入队的这个元素。如果队列不为空的话,此时就在队尾指针指向的队尾结点后插入这个新元素即可。然后将队尾指针指向这个新插入的结点,以保证队尾指针指向的总是队列的队尾结点。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = newNode;
		pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

队列中元素在出队时需要先判断队列是否为空,如果队列为空,则出队失败。判断队列是否为空,就是判断队列的队头指针或队尾指针的值是否为NULL。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	/*if (pq->head == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pq->head == NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

然后在队列中有元素要出队时,先判断队列是否为空,不为空才可以让队列中队头指针指向的结点出队,并且当队列中只有一个结点时,要进行出队的话,这一个结点出队之后,虽然head指针指向了NULL,但是tail指针还指向了这个被释放空间的原来的队尾结点,所以此时tail为野指针,这就需要我们再判断当队列中只有一个结点要出队时,该结点完成出队后,需要将head指针和tail指针都置为NULL,以恢复初始时队列为空的状态。



void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//当队列中只有一个结点时,该结点出队后队列就为空了
	//所以需要将队列的头指针和尾指针都置为NULL
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = NULL;
		//虽然按照下面的处理pq->head也会为NULL,
		//但tail指针还指向已经释放空间的最后一个结点的地址,所以此时tail为野指针,所以需要特别处理,将tail置为NULL
		pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
	}
	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

4、返回队头的数据和队尾的数据

队列还需要提供返回队头结点数据和队尾结点数据的函数,返回队头结点数据就是先判断队列是否为空,不为空的话将队头指针所指向结点的数据返回即可。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

返回队尾结点数据就是将队尾指针所指向结点的数据返回。

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

5、返回队列的长度

返回队列的长度可以通过遍历队列,每遍历一个结点,就将长度加1,最后将队列长度返回即可。不过这样求队列长度的时间复杂度为O(N)。

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* curr = pq->head;
	while (curr != NULL)
	{
		size++;
		curr = curr->next;
	}

	return size;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

还可以在设计队列时,将Queue结构体中再加一个成员size,用来记录队列的长度,当有元素入队时pq->size++,当有元素出队时pq->size–,这样队列长度直接通过pq->size就可以得到。

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;  //用来记录队列长度
}Queue;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

6、队列的销毁

队列的销毁就是先将队列的结点都一一销毁,然后将pq->head和pq->tail都指向NULL,此时队列中申请的结点占用的空间都被释放,而且队列回到了最初的状态。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* curr = pq->head;
	while (curr)
	{
		QNode* next = curr->next;
		free(curr);
		curr = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
	//在这里面将pq置为空没用,因为pq只是临时创建的一个Queue*类型的结构体指针
	//pq里面存的是Queue结构体变量的地址,在函数里面将pq置为NULL对外面没有影响。
	//只是让pq指向不了这个结构体变量了,但是这个结构体变量还存在,
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

三、循环队列

环形队列我们也可以通过一个例题来体会。
循环链表

四、队列和栈综合练习

在学习了队列和栈之后,我们可以用队列来实现栈,或用栈来实现队列,下面的链接为这两个问题的具体实现,可以点击链接进行学习。
用栈实现队列
用队列实现栈

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/644657
推荐阅读
相关标签
  

闽ICP备14008679号