𝙉𝙞𝙘𝙚!!👏🏻‧✧̣̥̇‧✦👏🏻‧✧̣̥̇‧✦ 👏🏻‧✧̣̥̇: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;
}
9.循环队列的基本操作
对于循环队列,自然也是有2 种方式可以实现:数组 或者是 链表
循环队列的特点就是避免了空间的浪费,可以重复使用
9.1 前期知识的了解
队最基本的性质:先进先出,队尾进入,队头出数据
为例了方便出队,进队的操作,定义2个指针 rear(尾指针)front (头指针)
数组实现如下:
定义一个队的结构
typedef struct Queue
{
DataType* a ;
int rear ;
int front ;
}Queue;
9.2 循环队列的初始化
问题就来了:rear 的初始值到底是 -1 还是 0 ?
其实都可以,关键是看自己的需求:我暂时以 rear = 0 他可以很直接的表明 队有效 的长度
9.3 进队
9.4 出队
9.5 判空
rear == front
9.6 判满
9.7 队头元素获取
这个就很简单了,直接对 front这个下标位置进行访问即可
9.8 队尾元素获取
注意rear 是指向队尾元素的下一个位置,所以需要 访问的是 rear -1 这个下标位置的数据
OK以上就是对循环队列的简单介绍
下面小试牛刀一把吧
9.9 设计循环队列
题目:
OJ代码:
typedef struct {
// 用数组方式实现循环队列
int* a;
int front;//队头指针
int rear;//队尾指针
int k;//队长,方便确定数组开多大空间
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->rear == obj->front;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->front == (obj->rear+1) %(obj->k+1);
}
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj = ( MyCircularQueue*)malloc(sizeof( MyCircularQueue));
obj->a = (int*)malloc(sizeof(int)*(k+1));//数组开辟空间
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if( myCircularQueueIsFull(obj) == true)//判断是否满
return false;
//进队动rear指针
obj->a[obj->rear] = value;
obj->rear = (obj->rear+1)% (obj->k+1);//保证rear 指向队尾元素的下一个位置避免越界
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj) == true)//是否为空
return false;
obj->front = (obj->front+1)% (obj->k+1);//避免越界
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj) == true)//是否为空
return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj) == true)//是否为空
return -1;
//return obj->a[obj->rear];//越界了,注意rear是指向队尾元素的下一个位置
// if(obj->rear == 0)
// return obj->a[obj->k];
// else
// return obj->a[obj->rear-1];
return obj->a[((obj->rear - 1) + (obj->k + 1)) % (obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
结语:
对于队列这种数据结构在我们的日常生活中还是随处可见的。餐厅的取号买饭,任务队列、事件队列、消息队列,和时间相关的东西都有队列的影响。所以说学好队列对生活的理解也会更深刻,以上就是我share 的内容,希望各位可以支持关注,谢谢大家!
版权声明:本文为博主作者:Solitary_walk原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/X_do_myself/article/details/134220644