数据结构之队的实现-CSDN博客

𝙉𝙞𝙘𝙚!!‧✧̣̥̇‧✦‧✧̣̥̇‧✦ ‧✧̣̥̇:Solitary-walk

      ⸝⋆   ━━━┓
     - 个性标签 - 来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━  ➴ ⷯ

本人座右铭    欲达高峰,必忍其痛;欲戴王冠,必承其重。

 
自
信
　    希望在看完我的此篇博客后可以对你有帮助哟

   此外希望各位大佬们在看完后可以互赞互关一下看到必回
    

一·队的初始化

二·队的销毁

三·出队头删

四·进队尾插

五·队的判空

六·取队头元素

七·取队尾元素

八·求队的大小

---

 在进行以下接口的实现中我们需要首先对队有一定的了解

1队的特征队头出元素队尾进元素

2对于队我们又有顺序队和链队之分

3链队它是由一个一个的结点进行连接起来的其次每一个结点又有对应的数据域与指针域

                所以说我们的队其实是一个双层嵌套的结构体:一个是对队的自定义结构体队头指                      针队尾指针size注意他可以没有但是为了避免多次的遍历我们这里就设置了                    size记录队的大小另一个就是自定义的结点类型的结构体

1.初始化

这里只需把指向队的头指针尾指针置空即可

void QuequeInit(Queque* p)//对队进行初始化,所以这里传的是指向队的指针(QNode* p)这样写是不对的
{
	assert(p);
	p->phead = NULL;
	p->ptail = NULL;
	p->size = 0;
}

2.销毁

其实同链表的销毁是一样的我们只需把结点进行一个一个的free就行了

还有就是销毁完之后别忘了让头尾指针置空

3.出队

出队首先是队头进行的

这里我们就需要对元素个数进行判断是只有一个元素还是多个元素

元素出队之后别忘了size--

 

 当队里面只有一个元素的时候把1 删除之后这就是一个空队了所以在出队之后就需要对头尾指针进行置空

 

 当我有多个数据时就正常进行头删就行别忘了对应的头节点需要进行更新

void QuequePop(Queque* p)//出队,在队头进行
{
	//2种情况  只有1个结点  有多个结点
	assert(p);
	assert(!QuequeEmpty(p));//确保队不为空
	if (p->phead->next == NULL)
	{
		free(p->phead);
		p->phead =p->ptail =  NULL;
		return;
	}
	else
	{
		QNode* next = p->phead->next;
		free(p->phead);
		p->phead = next;
	}
	//别忘size--
	p->size--;//注意--和-1区别
}

4.进队

1进队换言之就是尾插首先我们需要对尾插进来的数据进行结点的创建

2判空 的操作为空此时尾插进来 的数据就是我的新的头尾结点不为空尾插进来的数据就是新的尾结点进行尾结点的更新

void QuequePush(Queque* p,DataType x)//进队在队尾进行
{
	// 1 创建一个结点   2 对队进行判空操作
	assert(p);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//这里是对结点开辟空间sizeof(Queque)这样写是错误的
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	//开辟成功
	newnode->data = x;
	newnode->next = NULL;
	//对队的判空操作
	if (p->phead == NULL)
	{
		assert(p->ptail == NULL);//确保尾指针也为空
		p->ptail = p->phead = newnode;
	}
	else
	{
		p->ptail->next = newnode;
		p->ptail = newnode;//尾结点更新
	}
	//别忘了size++
	p->size++;
}

5.判空

bool QuequeEmpty(Queque* p)//判空
{
	assert(p);
	return p->phead == NULL
		&& p->ptail == NULL;
	//return p->size == 0;//注意这里一定要保持size一致性即不要忘了++ / -- 
}

6.取队头元素

DataType QuequeFront(Queque* p)//取队头元素
{
	assert(p);
	assert(!QuequeEmpty(p));
	return p->phead->data;
	//取完队头元素不要忘了--
}

7.取队尾元素

DataType QuequeBack(Queque* p)//取队尾元素
{
	assert(p);
	assert(!QuequeEmpty(p));

	return p->ptail->data;

}

8.队的大小

int  QuequeSize(Queque* p)//队的大小
{
	assert(p);
	return p->size;
}

---

Quqque.h对应完整代码

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

typedef int DataType;
//定义一个结构体单链表可以解决没必要用双向链表(单链表)链队列数据域指针域
//注意以下2个结构体不能进行合并
typedef struct QuequeNode
{
	//注意以下只是定义队列的一个结点对应的类型
	DataType data;//数据域
	struct SLQuequeNode* next;//指针域
}QNode;
typedef struct Queque
{
	//注意以下只是定义队列的类型
	QNode* phead;//队列的头指针
	QNode* ptail;//队列的尾指针
	int size;//记录数据个数避免后续的遍历
}Queque;
//队列接口的实现
void QuequeInit(Queque* p);//初始化
void QuequeDestroy(Queque* p);//销毁
void QuequePop(Queque* p);//出队在队头进行
void QuequePush(Queque* p,DataType x);//进队在队尾进行
bool QuequeEmpty(Queque* p);//判空
DataType QuequeFront(Queque* p);//
DataType QuequeBack(Queque* p);//
int  QuequeSize(Queque* p);//队的大小

Quqque.c对应完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queque.h"

void QuequeInit(Queque* p)//对队进行初始化,所以这里传的是指向队的指针(QNode* p)这样写是不对的
{
	assert(p);
	p->phead = NULL;
	p->ptail = NULL;
	p->size = 0;
}
void QuequeDestroy(Queque* p)//销毁
{
	assert(p);
	/*Queque* pcur = p->phead;*///因为是对结点一个一个删除
	QNode* pcur = p->phead;
	while (pcur)
	{
		/*Queque* next = pcur->next;*///错误写法原因同上
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//别忘了执行以下操作
	p->phead = NULL;
	p->ptail = NULL;
	p->size = 0;
}
void QuequePop(Queque* p)//出队,在队头进行
{
	//2种情况  只有1个结点  有多个结点
	assert(p);
	assert(!QuequeEmpty(p));//确保队不为空
	if (p->phead->next == NULL)
	{
		free(p->phead);
		p->phead =p->ptail =  NULL;
		return;
	}
	else
	{
		QNode* next = p->phead->next;
		free(p->phead);
		p->phead = next;
	}
	//别忘size--
	p->size--;//注意--和-1区别
}
void QuequePush(Queque* p,DataType x)//进队在队尾进行
{
	// 1 创建一个结点   2 对队进行判空操作
	assert(p);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//这里是对结点开辟空间sizeof(Queque)这样写是错误的
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	//开辟成功
	newnode->data = x;
	newnode->next = NULL;
	//对队的判空操作
	if (p->phead == NULL)
	{
		assert(p->ptail == NULL);//确保尾指针也为空
		p->ptail = p->phead = newnode;
	}
	else
	{
		p->ptail->next = newnode;
		p->ptail = newnode;//尾结点更新
	}
	//别忘了size++
	p->size++;
}
bool QuequeEmpty(Queque* p)//判空
{
	assert(p);
	return p->phead == NULL
		&& p->ptail == NULL;
	//return p->size == 0;//注意这里一定要保持size一致性即不要忘了++ / -- 
}
DataType QuequeFront(Queque* p)//取队头元素
{
	assert(p);
	assert(!QuequeEmpty(p));
	return p->phead->data;
	//取完队头元素不要忘了--
}
DataType QuequeBack(Queque* p)//取队尾元素
{
	assert(p);
	assert(!QuequeEmpty(p));

	return p->ptail->data;

}
int  QuequeSize(Queque* p)//队的大小
{
	assert(p);
	return p->size;
}

test.c对应完整代码

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queque.h"
void Quequetest()
{
	Queque plist;
	QuequeInit(&plist);
	QuequePush(&plist, 1);
	QuequePush(&plist, 2);
	QuequePush(&plist, 3);
	QuequePush(&plist, 4);
	//QuequePop(&plist);
	//QuequePop(&plist);
	//QuequePop(&plist);
	//QuequePop(&plist);
	while (!QuequeEmpty(&plist))//打印队的数据只要不为空即可
	{
		printf("%d ", QuequeFront(&plist));//其实就是取出队头元素
		QuequePop(&plist);//出队
	}
	printf("\n");

	QuequeDestroy(&plist);

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