您现在的位置是：首页 >学无止境 >【数据结构】队列的实现网站首页学无止境

【数据结构】队列的实现

日出等日落 2023-05-24 00:00:03
简介【数据结构】队列的实现

😛作者：日出等日落

📘 专栏：数据结构

时间一直在流逝，貌似所有人都在向前走，只有我一直在原地踏步，说着要向前看要向前看，可总感觉没有完全放开步子大步向前走，2022我们来一次告别仪式吧，告别所有的不好，迎来崭新的2023，已然找不到坚持下去的理由，那就找一个重新开始的理由吧。

目录

队列 ：

队列的概念及结构：

 队列的各功能实现：

 结构体：

 QueueInit(初始化队列)：

QueueDestroy(销毁队列)：

QueuePush(队尾入队列):

 QueuePop(队头出队列):

QueueFront(获取队列头部元素):

 QueueBack(获取队列队尾元素):

QueueEmpty(检测队列是否为空):

QueueSize(返回队列大小):

完整代码：

Queue.h:

Queue.c:

Text.c:

 

 

队列 ：

队列的概念及结构：

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

 

 队列的各功能实现：

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

 结构体：

// 链式结构：表示队列
typedef struct QueueNode
{
	QDataType data;
	struct Queue* next;
}Qnode;

// 队列的结构
typedef struct Queue
{
	Qnode* head;
	Qnode* tail;
	int size;
}Queue;

 QueueInit(初始化队列)：

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

}

QueueDestroy(销毁队列)：

// 销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	Qnode* cur = pq->head;
	while (cur)
	{
		Qnode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

QueuePush(队尾入队列):

// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if (newnode == NULL)
	{
		perror("malloc: fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

 QueuePop(队头出队列):

// 队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		Qnode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
	}
	pq->size--;
}

QueueFront(获取队列头部元素):

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

 QueueBack(获取队列队尾元素):

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

QueueEmpty(检测队列是否为空):

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

QueueSize(返回队列大小):

//返回队列大小
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

完整代码：

Queue.h:

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


typedef int QDataType;

// 链式结构：表示队列
typedef struct QueueNode
{
	QDataType data;
	struct Queue* next;
}Qnode;

// 队列的结构
typedef struct Queue
{
	Qnode* head;
	Qnode* tail;
	int size;
}Queue;

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

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

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

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

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

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

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);

//返回队列大小
int QueueSize(Queue* pq);

Queue.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

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

}

// 销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	Qnode* cur = pq->head;
	while (cur)
	{
		Qnode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if (newnode == NULL)
	{
		perror("malloc: fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

// 队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		Qnode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
	}
	pq->size--;
}

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

//返回队列大小
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

Text.c:

#define _CRT_SECURE_NO_WARNINGS 1

#include "Queue.h"

void TestQueue()
{
	//Queue q1;
	//Queue q2;
	//QueueInit(&q1);
	//QueueInit(&q2);


	//QueueDestroy(&q1);
	//QueueDestroy(&q2);

	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	printf("%d
", QueueSize(&q));
	printf("%d
", QueueEmpty(&q));
	printf("%d
", QueueFront(&q));
	printf("%d
", QueueBack(&q));

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("
");

	printf("%d
", QueueSize(&q));
	printf("%d
", QueueEmpty(&q));
	//printf("%d
", QueueFront(&q));
	//printf("%d
", QueueBack(&q));

	QueueDestroy(&q);
}


int main()
{
	TestQueue();
	return 0;
}

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐