队列（数据结构）——C语言

时间：2024-10-22 16:06:47

目录

1.概念与结构

2.队列的实现

初始化QueueInit

申请新节点BuyNode

入队QueuePush

判断队为空QueueEmpty

出队QueuePop

读取队头数据QueueFront

读取队尾数据QueueBack

元素个数QueueSize

销毁队列QueueDestroy

3.整体代码

(文章中结点和节点是同一个意思)

1.概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先 出FIFO(First In First Out)

⼊队列：进⾏插⼊操作的⼀端称为队尾

出队列：进⾏删除操作的⼀端称为队头

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出列在数组头上出数据，需要将后面所有的元素整体向前移动一位，时间复杂度为o（n），效率会⽐较低，入队操作是单链表需要遍历整个链表找到尾结点，所以这里定义一个头结点和尾结点，来避免入队操作时间复杂度高。

2.队列的实现

创建三个文件，Queue.h,Queue.c,test.c，分别为头文件，函数实现文件，以及测试文件

Queue.h

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

typedef int DataType;

typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

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

//入队列--队尾
void QueuePush(Queue* pq, DataType x);
//出队列--队头
void QueuePop(Queue* pq);

//取队头数据
DataType QueueFront(Queue* pq);
//取队尾数据
DataType QueueBack(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

这里很之前的一样，栈里存的元素。可以是各种数据类型，为了方便后续改成其他类型，这里重定义数据类型为SDataType，这里以int为例，定义结构体队列的节点，这里利用结构体的自引用，用来找到下一个结点，即next；以及队列的头结点，和尾结点，队列的元素个数；还有实现各种函数的申明。

初始化QueueInit

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

断言传的指针非空，头结点和尾结点置为空，元素个数为零。

申请新节点BuyNode

QueueNode* BuyNode(DataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

这里返回类型为结构体QueueNode*类型，利用malloc函数申请，申请成功后，再将结构体的data赋值为x，下一个结点，即next置为空。

入队QueuePush

void QueuePush(Queue* pq, DataType x)
{
	assert(pq);
	QueueNode*newnode= BuyNode(x);
	if (pq->phead ==NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

断言传的指针非空，申请一个节点，判断队是否为空，如果为空直接将新的结点，赋给头结点和尾结点，如果不为空，则在尾结点后面插入，（很前面单链表尾插一样，只是这里已经有尾结点了，不需要遍历单链表），最后元素个数++；

判断队为空QueueEmpty

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead==NULL;
}

这里返回类型为bool型，断言传的指针非空，通过判断头结点是否为NULL，为空则队列中没有元素。

出队QueuePop

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;	
	}
	pq->size--;	
}

断言传的指针非空，以及判断队列非空，出队要考虑两种情况，如果队列中只有一个节点，即头结点和尾结点指向同一个，直接释放掉头结点，然后头结点和尾结点置为空就行了，如果不止一个节点，则删除头结点指向那个结点，头结点指向下一个结点，（和单链表的头插一模一样），最后元素个数——。

读取队头数据QueueFront

DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

断言传的指针非空，以及判断队列非空，直接返回头结点的data。

读取队尾数据QueueBack

DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

断言传的指针非空，以及判断队列非空，直接返回尾结点的data。

元素个数QueueSize

int QueueSize(Queue* pq)
{
    assert（pq）；
	return pq->size;
}

断言传的指针非空，直接返回结构体Queue中的size，即为队列元素个数。

销毁队列QueueDestroy

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

断言传的指针非空，定义一个指针指向头结点，遍历链表，依次删除（这里和前面的单链表销毁的函数也是一模一样），最后将头结点，和尾结点都置为空，元素个数置为0.

3.整体代码

Queue.h

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

typedef int DataType;

typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

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

//入队列--队尾
void QueuePush(Queue* pq, DataType x);
//出队列--队头
void QueuePop(Queue* pq);

//取队头数据
DataType QueueFront(Queue* pq);
//取队尾数据
DataType QueueBack(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

QueueNode* BuyNode(DataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void QueuePush(Queue* pq, DataType x)
{
	assert(pq);
	QueueNode*newnode= BuyNode(x);
	if (pq->phead ==NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;	
	}
	pq->size--;	
}

DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead==NULL;
}

int QueueSize(Queue* pq)
{
	return pq->size;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

相关文章