数据结构初阶：实现队列的两种方法

用户11290664

发布于 2024-09-25 13:33:46

5000

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头. 注意和栈的先进后出有所不同。

1队列的概念和两种实现方式

我们在实现栈的时候有循环队列和链表队列两种方法。链表队是要用到两个结构体。一个结构体来存放数据，另一个结构体存放第一个结构体的指针然后用第二个结构体的指针来访问第一个结构体的指针和地址。这样做的好处是可以避免使用二级指针，进而优化算法。（因为在出队的时候要改变头指针的指向，但是形参不能改变实参，所以麻烦的方法是使用二级指针，然后解引用操作来改变头指针的地址，以达到出队的目的）。

typedef int SLType;
typedef struct SList
{
	struct SList* next;
	SLType val;
}Queue;

typedef struct Tool {
	Queue *ptail;
	Queue *head;
	int sum;
}Tool;  //链表队列

循环队列则是先定义一个最大的空间，然后出队是删除前面的元素，入队是在前面添加新元素。我们可以循环起来利用。那么有个问题就是我们如何判断循环队列已经满了？

我们常见的方法就是牺牲一个空间，每次让Taii指向队尾元素下一个元素。然后用(Head+1)%N(N为元素空间)是否等于Head来判断。模N的目的是为了防止出界。

如图我们有四个数据，虽然我们定义N是5但是只能存4个数据

2两种方式的具体方法

//初始化 //判断是否为满 //判断是否为空 //入队 //出队 //打印现有队列 //返回头元素 //返回尾部元素 //销毁队列

二种方法的定义 判断是否为满

链表队列

无序判断

循环队列

bool Full(Queue* p) {


	return (p->tail + 1) % N == p->head;

}//判断是否为满

链表队列

typedef int SLType;
typedef struct SList
{
	struct SList* next;
	SLType val;
}Queue;

typedef struct Tool {
	Queue *ptail;
	Queue *head;
	int sum;
}Tool;  //链表队列

循环队列

#define N 30//给数组30个空间大小来存放到循环数组中
typedef int QueType;
typedef struct Queue
{
	QueType* a;
	int head;
	int tail;


}Queue;//定义结构体内部有数组，头指针和尾指针

判断是否为空

链表队列

bool Empty(Tool* aa) {

	return (aa->phead == NULL) && (aa->ptail == NULL);

}

循环队列

bool Empty(Queue* p) {

	return (p->head == 0) && (p->tail == 0);
}//判断是否为空

初始化

链表队列

void Inite(Tool *aa)
{
	aa->phead = NULL;
	aa->ptail = NULL;
	aa->sum = 0;

}

循环队列

void Inite(Queue* p)
{
	p->a = NULL;
	p->head = 0;
	p->tail = 0;
	p->a = (Queue*)malloc(sizeof(QueType) * N);//申请N个空间。
	
	if (p->a == NULL) {//判断是否申请空间
		perror("fail");
		return;

	}
	

}

入队

链表队列

void PushBack(Tool* aa,SLType x) {
	Queue*  new =  Creat(x);
	if (aa->phead == NULL) {

		
		aa->phead = aa->ptail = new;

	}
	else
	{
		aa->ptail->next = new;
		aa->ptail = new;

	}


}

Queue* Creat(SLType x) {
	Queue* newnode = (Queue*)malloc(sizeof(SLType));
	if (newnode == NULL) {
		perror("fail");
		exit(-1);


	}
	
	newnode->next = NULL;

	newnode->val = x;

	return newnode;


}//创造新的结点

循环队列

void Pushback(Queue* p, QueType x)
{
	assert(p);
	assert(!Full(p));
	p->a[p->tail] = x;
	p->tail = (p->tail + 1) % N;//先入队再让tail++



}

打印现有队列

链表队列

void Print(Tool* aa){
	Queue* cur = aa->phead;
	while (cur!=aa->ptail->next) {
		printf("%d",cur->val);
		cur = cur->next;
	}

}//打印队列

循环队列

void Print(Queue* p) {

	int cur = p->head;
	while (cur != p->tail)
	{

		printf("%d", p->a[cur]);
		printf("\n");
		cur = (cur + 1) % N;
	}



}

返回头元素

链表队列

SLType HeadBack(Tool* aa) {
	assert(!Empty(aa));

	return aa->phead->val;
}

循环队列

Queue* HeadBack(Queue* p) {
	assert(!Empty(p));
	return p->a[p->head];

}//返回头元素

返回尾部元素

链表队列

SLType TailBack(Tool* aa){
	assert(!Empty(aa));

	return aa->ptail->val;
}

循环队列

Queue* TailBack(Queue* p) {
	
		assert(!Empty(p));
	return p->a[(p->tail - 1) % N];
		
}//返回尾部元素

销毁队列

链表队列

void Destroy(Tool* aa)
{      

	Queue* cur = aa->phead;
	while (cur)
	{
		Queue* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	aa->phead = aa->ptail = NULL;
}

循环队列

void Destroy(Queue* p){
	free(p->a);
	p->a = NULL;
	p->head = p->tail = 0;

}//销毁队列

3源代码

链表队列

SSList.h

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


typedef int SLType;
typedef struct SList
{
	struct SList* next;
	SLType val;
}Queue;

typedef struct Tool {
	Queue *ptail;
	Queue *phead;
	int sum;
}Tool;  //链表队列

//防止二级指针的方法，1.在定义

//2

void Inite(Tool* aa);//初始化
Queue* Creat(SLType x);//创造新的结点
void PushPop(Tool* aa);//出队
void Print(Tool* aa);//打印

void PushBack(Tool* aa);//入队
SLType HeadBack(Tool* aa);//返回头指针的元素
SLType TailBack(Tool* aa);//返回尾指针的元素
bool Empty(Tool* aa);//判空
void Destroy(Tool* aa);//销毁

SSList.c

#include"SSList.h"
void Inite(Tool *aa)
{
	aa->phead = NULL;
	aa->ptail = NULL;
	aa->sum = 0;

}

Queue* Creat(SLType x) {
	Queue* newnode = (Queue*)malloc(sizeof(SLType));
	if (newnode == NULL) {
		perror("fail");
		exit(-1);


	}
	
	newnode->next = NULL;

	newnode->val = x;

	return newnode;


}//创造新的结点
void PushPop(Tool* aa) {
	
	aa->phead = aa->phead->next;
	

}//出队
void Print(Tool* aa){
	Queue* cur = aa->phead;
	while (cur!=aa->ptail->next) {
		printf("%d",cur->val);
		cur = cur->next;
	}

}//打印队列

void PushBack(Tool* aa,SLType x) {
	Queue*  new =  Creat(x);
	if (aa->phead == NULL) {

		
		aa->phead = aa->ptail = new;

	}
	else
	{
		aa->ptail->next = new;
		aa->ptail = new;

	}


}
SLType HeadBack(Tool* aa) {
	assert(!Empty(aa));

	return aa->phead->val;
}
SLType TailBack(Tool* aa){
	assert(!Empty(aa));

	return aa->ptail->val;
}
bool Empty(Tool* aa) {

	return (aa->phead == NULL) && (aa->ptail == NULL);

}
void Destroy(Tool* aa)
{      

	Queue* cur = aa->phead;
	while (cur)
	{
		Queue* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	aa->phead = aa->ptail = NULL;
}

循环队列

QueueArray.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define N 5//给数组30个空间大小来存放到循环数组中
typedef int QueType;
typedef struct Queue
{
	QueType* a;
	int head;
	int tail;


}Queue;//定义结构体内部有数组，头指针和尾指针
void Inite(Queue* p);//初始化
void Pushback(Queue* p,QueType x);//入队
void PushPop(Queue* p);//出队
void Print(Queue* p);//打印现有队列
Queue* HeadBack(Queue *p);//返回头元素
Queue* TailBack(Queue* p);//返回尾部元素
bool Full(Queue* p);//判断是否为满
bool Empty(Queue* p);//判断是否为空
void Destroy(Queue* p);//销毁队列

QueueArray.c

#include"QueueArray.h"
void Inite(Queue* p)
{
	p->a = NULL;
	p->head = 0;
	p->tail = 0;
	p->a = (Queue*)malloc(sizeof(QueType) * N);
	
	if (p->a == NULL) {
		perror("fail");
		return;

	}
	

}

void Pushback(Queue* p, QueType x)
{
	assert(p);
	assert(!Full(p));
	p->a[p->tail] = x;
	p->tail = (p->tail + 1) % N;



}

void PushPop(Queue* p)
{
	p->head = (p->head + 1) % N;

}
void Print(Queue* p) {

	int cur = p->head;
	while (cur != p->tail)
	{

		printf("%d", p->a[cur]);
		printf("\n");
		cur = (cur + 1) % N;
	}



}
Queue* HeadBack(Queue* p) {
	assert(!Empty(p));
	return p->a[p->head];

}//返回头元素
Queue* TailBack(Queue* p) {
	
		assert(!Empty(p));
	return p->a[(p->tail - 1) % N];
		
}//返回尾部元素
bool Full(Queue* p) {


	return (p->tail + 1) % N == p->head;

}//判断是否为满
bool Empty(Queue* p) {

	return (p->head == 0) && (p->tail == 0);
}//判断是否为空
void Destroy(Queue* p){
	free(p->a);
	p->a = NULL;
	p->head = p->tail = 0;

}//销毁队列