栈和队列详解(2)

C/C++
157
0
0
2024-04-20
C++类相关oj题目分享（计算日期到天数转换、日期差值、打印日期、日期累加）
上一篇
栈和队列详解(1)
下一篇

一、什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。可以形象地将队列想象成生活中的挤地铁，在挤地铁的时候我们只能够从后面进入队伍，出也只能够从队头出到地铁。总结：队列是只支持尾插头删的线性表。

二、创建一个我们自己的队列

1.前置准备

1.1需要的三个文件
在开始之前，我们最好创建三个文件，一个放栈函数的实现，一个用来测试栈函数，最后一个放栈函数的引用和头文件的引用，这样到时侯想要使用栈函数直接包这一个头文件即可。创建完之后，呈现出来的效果与下图差不多即可。

1.2结构体的创建和头文件的引用
由于队列需要头删，使用数组实现的话最终呈现出来的效率十分低下，我们这里使用链表的方式实现，使用链表来实现线性表，头和尾是经常要用到的，同样队列的长度也很重要。因此我们创建两个结构体变量，一个结构体变量为链表的节点，一个结构体变量存放链表的头和尾以及队列的长度。

最终呈现出来的结果是这样的

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int QueDateType;
//到时修改类型时只用改这里的一个就可以，不需要一个个修改
//同样，这也是为了和单一的int作区分
typedef struct QueueListNode
{
	struct QueueListnode* next;
	//存放下一个节点
	QueDateType data;
	//存放当前节点的数据
}Quenode;
typedef struct QueueInformation
{
	Quenode* head;//存放头节点
	Quenode* tail;//存放尾节点
	int sz;//存放个数
}Que;

2.接口的实现

2.1初始化队列

没什么好说的，将队列的两个指针变为空，存放个数的变量变为0即可

void init_queue(Que* q1)
{
	assert(q1);
    //q1存放的是结构体的指针，不应为空，为空操作不了
	q1->head = NULL;
	q1->tail = NULL;
	q1->sz = 0;
}
2.2入队
void push_queue(Que* q1, QueDateType x)
{
	assert(q1);
	//创建一个新节点，并初始化
	Quenode* newnode = (Quenode*)malloc(sizeof(Quenode));	
	if (newnode == NULL)
	{
		perror("push_queue");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->data = x;
	if (q1->head == NULL)
	//如果头为空，意味着还没有节点，单独处理
	{
		q1->head = q1->tail = newnode;
	}
	else
	{
		q1->tail->next = newnode;
		//原来的尾链接上新的尾
		q1->tail = newnode;
		//将尾更新
	}
	q1->sz++;
}
2.3队列元素个数和判空
可能有小伙伴不明白为什么又要设计这两个接口，因为这两个信息都可以直接通过队列的结构体获得，好像没什么作用啊。设计这两个接口并使用它们而不是直接通过结构体的内容来判断是因为，当我们的需求发生改变了，所创建的结构体可能也会跟着修改，可能提取的方式会发生一些改变 如果我们在使用队列的时候已经直接通过结构体的内容进行了多次的判断，那么我们要修改起来，要修改多次，很不方便，这样做的好处就是只用修改一次即可

队列元素个数

int size_queue(Que* q1)
{
	assert(q1);
	return q1->sz;
}

判空

int empty_queue(Que* q1)
{
	assert(q1);
	return q1->sz == 0;
	//相等即为空，返回1(真)
	//不相等即为非空，返回0(假)
}
2.4取队头元素和队尾元素

这两个操作很相似，唯一要注意的就是，为空的时候不能取

取队头元素

QueDateType queue_front(Que* q1)
{
	assert(q1);
	assert(!empty_queue(q1));
	//队列不能是空
	return q1->head->data;
}

取队尾元素

QueDateType queue_back(Que* q1)
{
	assert(q1);
	assert(!empty_queue(q1));
	//队列不能是空
	return q1->tail->data;
}
2.5出队

需要注意的是，不能够删除空队列，其次我们删除到最后一个节点时要单独处理

void pop_queue(Que* q1)
{
	assert(q1);
	assert(!empty_queue(q1));
	if (q1->head->next == NULL)
	//最后一个节点单独处理
	//避免尾指针变野指针
	{
		free(q1->head);
		q1->head = NULL;
		q1->tail = NULL;
	}
	else
	{
		Quenode* next = q1->head->next;
		free(q1->head);
		q1->head = next;
	}
	q1->sz--;
}
2.6摧毁队列
void destroy_queue(Que* q1)
{
	assert(q1);
	Quenode* cur = q1->head;
	while (cur)
	{
		Quenode* next = cur->next;
		free(cur);
		cur = next;
	}
}
2.7测试接口

测试代码：

#include"queue.h"
void test1()
{
	Que q1;
	init_queue(&q1);
	push_queue(&q1, 1);
	push_queue(&q1, 2);
	push_queue(&q1, 3);
	push_queue(&q1, 4);
	push_queue(&q1, 5);
	printf("%d\n", queue_back(&q1));
	while (!empty_queue(&q1))
	{
		printf("%d ", queue_front(&q1));
		pop_queue(&q1);
	}
	destroy_queue(&q1);
}
int main()
{
	test1();
}

测试结果：

三、所有代码

1.接口实现

#include"queue.h"
void init_queue(Que* q1)
{
	assert(q1);
    //q1存放的是结构体的指针，不应为空，为空操作不了
	q1->head = NULL;
	q1->tail = NULL;
	q1->sz = 0;
}
void push_queue(Que* q1, QueDateType x)
{
	assert(q1);
	//创建一个新节点，并初始化
	Quenode* newnode = (Quenode*)malloc(sizeof(Quenode));	
	if (newnode == NULL)
	{
		perror("push_queue");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->data = x;
	if (q1->head == NULL)
	//如果头为空，意味着还没有节点，单独处理
	{
		q1->head = q1->tail = newnode;
	}
	else
	{
		q1->tail->next = newnode;
		//原来的尾链接上新的尾
		q1->tail = newnode;
		//将尾更新
	}
	q1->sz++;
}
int size_queue(Que* q1)
{
	assert(q1);
	return q1->sz;
}
int empty_queue(Que* q1)
{
	assert(q1);
	return q1->sz == 0;
	//相等即为空，返回1(真)
	//不相等即为非空，返回0(假)
}
QueDateType queue_front(Que* q1)
{
	assert(q1);
	assert(!empty_queue(q1));
	//队列不能是空
	return q1->head->data;
}
QueDateType queue_back(Que* q1)
{
	assert(q1);
	assert(!empty_queue(q1));
	//队列不能是空
	return q1->tail->data;
}
void pop_queue(Que* q1)
{
	assert(q1);
	assert(!empty_queue(q1));
	if (q1->head->next == NULL)
	//最后一个节点单独处理
	//避免尾指针变野指针
	{
		free(q1->head);
		q1->head = NULL;
		q1->tail = NULL;
	}
	else
	{
		Quenode* next = q1->head->next;
		free(q1->head);
		q1->head = next;
	}
	q1->sz--;
}
void destroy_queue(Que* q1)
{
	assert(q1);
	Quenode* cur = q1->head;
	while (cur)
	{
		Quenode* next = cur->next;
		free(cur);
		cur = next;
	}
}

2.队列的头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int QueDateType;
//到时修改类型时只用改这里的一个就可以，不需要一个个修改
//同样，这也是为了和单一的int作区分
typedef struct QueueListNode
{
	struct QueueListnode* next;
	//存放下一个节点
	QueDateType data;
	//存放当前节点的数据
}Quenode;
typedef struct QueueInformation
{
	Quenode* head;//存放头节点
	Quenode* tail;//存放尾节点
	int sz;//存放个数
}Que;
void init_queue(Que* q1);
void push_queue(Que* q1, QueDateType x);
void pop_queue(Que* q1);
int size_queue(Que* q1);
int empty_queue(Que* q1);
QueDateType queue_front(Que* q1);
QueDateType queue_back(Que* q1);
void destroy_queue(Que* q1);

3.测试代码

#include"queue.h"
void test1()
{
	Que q1;
	init_queue(&q1);
	push_queue(&q1, 1);
	push_queue(&q1, 2);
	push_queue(&q1, 3);
	push_queue(&q1, 4);
	push_queue(&q1, 5);
	printf("%d\n", queue_back(&q1));
	while (!empty_queue(&q1))
	{
		printf("%d ", queue_front(&q1));
		pop_queue(&q1);
	}
	destroy_queue(&q1);
}
int main()
{
	test1();
}

好了，今天的分享到这里就结束了感谢各位友友的来访，祝各位友友前程似锦O(∩_∩)O

C++类相关oj题目分享（计算日期到天数转换、日期差值、打印日期、日期累加）
上一篇
栈和队列详解(1)
下一篇