你真的会数据结构吗:队列

这篇具有很好参考价值的文章主要介绍了你真的会数据结构吗:队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❀❀❀ 文章由@不准备秃的大伟原创 ❀❀❀

♪♪♪ 若有转载,请联系博主哦~ ♪♪♪

❤❤❤ 致力学好编程的宝藏博主,代码兴国!❤❤❤

        halo大家好啊,没错,又是我大伟,今天也是满怀热情的来给大家学习知识,学校的课虽然很多,但是不听就不会那么累啦(假的),哈哈, 不知道大家有没有什么好办法来平衡学校的课和自己的学习时间以及自己的休息时间的呢?有良药的可以借大伟一剂吗 ^_~        

        那么话不多说,咱们正式进入今天的学习:队列

        不知道大家在生活中有没有去排过号(叫号)过,我们都知道客服人员几乎总是比客户要少很多的,在所有客服人员都占线的情况下,其余的客户会被要求等待,直到有客服人员空下来,才能给最先等的客户服务,这里其实就是用到了队列的性质。

队列(queue)是只允许在一端进行输入操作,而在另一端进行删除操作的线性表

        总的来说,队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端为队尾,允许删除的一端为对头,如下图:你真的会数据结构吗:队列,你真的学懂了数据结构?,c语言,数据结构,算法

        那同样,我们该如何实现队列呢?同栈一样,我们有两个思想:1.数组 2.链表 

        那我们来看看哪个方法可行吧!:

        如果我们使用数组,需要一个头指针(首元素的下标)和一个尾指针(尾元素的下一个元素的下标)在插入元素的时候当然要考虑扩容,然后放元素数值,然后尾指针加加,没问题,那我们再来看看删除元素,其实删(出)元素也很简单,只要头指针++就好了,各个方面都很完美,只是会浪费一些空间罢了。

        那我们再来看看链表的效果怎么样呢:同样,需要一个头指针和一个尾指针,还需要一个next指针,插入元素的时候就创建一个节点连接到尾节点就好了,出数据的时候就先记录头节点下一个元素的位置,再释放刚刚的头结点,再把记录的设置为新头。

        对比一下,大家觉得那个更好呢?毋庸置疑是链表好吧~ o(* ̄3 ̄)o 诶,但是现在先别小看用数组实现的队列,等会有道题数组会起到大作用哦~,但是现在还是就先把队列实现一下吧!

        Queue.h

        我们的队列的结构体和之前学的所有的数据结构的结构体的结构都不太一样,因为头指针和尾指针都需要next(下一个节点)和data(数据),所以我们可以定义两个结构体:

typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* front;
	QNode* tail;
	QDataType size;
}Queue;

         声明:

// 初始化队列 
void QueueInit(Queue* pq);
// 队尾入队列 
void QueuePush(Queue* pq, QDataType x);
// 队头出队列 
void QueuePop(Queue* pq);
// 获取队列头部元素 
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素 
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数 
int QueueSize(Queue* pq);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* pq);
// 销毁队列 
void QueueDestroy(Queue* pq);

        Queue.c 

                队列初始化:

void QueueInit(Queue* pq)
{
	assert(pq);

//由于一开始队列为空,所以都指向NULL,且队列大小为0
	pq->front = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

                 取队头元素:

QDataType QueueFront(Queue* pq)
{
	assert(pq);
//若队列为空
	assert(pq->front);

	return pq->front->data;
}

                取队尾元素:

QDataType QueueBack(Queue* pq)
{
	assert(pq);
//若队列为空
	assert(pq->tail);

	return pq->tail->data;
}

                队列入数据:

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;
//若队列不止一个元素
	if (pq->tail)
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
//若队列只有一个元素
	else
	{
		pq->front = pq->tail = newnode;
	}
	pq->size++;
}

                队列出数据:

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->front);

//若队列只有一个元素
	if (pq->front->next == NULL)
	{
		free(pq->front);
		pq->front = pq->tail = NULL;
	}
//若队列有多个元素
	else
	{
//先记录队头的下一个元素
		QNode* Next = pq->front->next;
		free(pq->front);
		pq->front = Next;
	}
	pq->size--;
}

                取队列大小:

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

                队列是否为空:

int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

                销毁队列:

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->front;
//依次释放节点
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->front = pq->tail = NULL;
	pq->size = 0;
}

                嗯,结束了,是不是感觉也不难,٩(͡๏̯͡๏)۶ ,那么老规矩,写完了,就来玩玩吧!

        test.c

#include"Queue.h"
int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);//1
	QueuePush(&q, 2);//1 2
	QueuePush(&q, 3);//1 2 3
	printf("%d ", QueueFront(&q));//1
	printf("%d ", QueueBack(&q));//3

	QueuePop(&q);//2 3

	printf("%d ", QueueBack(&q));//3
	QueuePush(&q, 4);//2 3 4
	QueuePush(&q, 5);//2 3 4 5
	printf("%d ", QueueFront(&q));//2
	printf("%d ", QueueBack(&q));//5

	return 0;
}

        对照一下:是不是和理想一模一样? 

你真的会数据结构吗:队列,你真的学懂了数据结构?,c语言,数据结构,算法

        好的,队列到这里也就结束了,诶诶诶,先别急着退出嘛,这里给大家来一条题目练练手呗○( ^皿^)っHiahiahia…: 力扣循环链表

        你真的会数据结构吗:队列,你真的学懂了数据结构?,c语言,数据结构,算法         兄弟们,有没有想法呢?还是用链表实现吗?在这里博主多嘴一句,用链表会特别烦,细节处理很难搞,还记得本篇博客上面讲的啥吗?用数组实现,这里就用到啦!

        那该如何操作呢?我们知道,数组的下标是逐渐增长的,但是我们需要一个循环的,而正巧,这个世界上存在一个十分精妙的操作符 “%” 取余,而我们正是要借助 “%” 来实现我们的循环队列。具体怎么做呢?如下:

        定义个头指针和尾指针,尾插,如果尾指针大于队列长度,就%一个队列长度,让尾走到数组的头,删除操作也是同一个思路。什么,没听懂?上图!

你真的会数据结构吗:队列,你真的学懂了数据结构?,c语言,数据结构,算法

         如图,我们的tail指向的是尾数据的下一个节点位置,而当我们插入最后一个数据时,此时队列满了,而tail++,此刻tail不就越界了吗,所以为了使队列满的时候tail还不越界,我们就多开一个空间。

        OK,那我们接下来一个功能一个功能的思考,实现:

        首先是结构体的定义:如上,我们需要一个数组a,一个头结点tail 一个尾节点rear(由于题目给的是rear,我们跟着改就好了),此外还需要一个记录队列长度的整形变量k,代码如下:

typedef struct {
    int *a;
    int k;
    int front;
    int rear;
} MyCircularQueue;

        接着就是初始化

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = malloc(sizeof(MyCircularQueue));
//多创建一个节点的空间
    obj->a = malloc(sizeof(int)*(k+1));
//初始化的时候先头尾指向0
    obj->front = 0;
    obj->rear = 0;
    obj->k = k;
    return obj;
}

        然后就是循环队列判空,那什么情况下我们的队列是空的呢?没错,是不是就是头和尾指向同一个位置?头和尾都指向同一个节点了,那么之间肯定没有元素了,对吧!于是,我们可以这么写:


bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

        好的,那既然有了判空,反过来就肯定有判满对吧?那什么情况会满呢?诶,这时候有铁汁看着大伟上面给的图就会发现,既然多开了一个空间,那么逻辑结构上来说rear(尾)的下一个是front(头)不就可以判满了吗?“完美”,我只能说完美,逻辑结构上确实是如此,那物理结构上呢? 诶,别忘记了我们的神器:“%” 啊!还是如上图,如果我们直接把rear % k不就好了?

        对,对,对?不再仔细想想 <(* ̄▽ ̄*)/ ,有没有一种可能,rear在front的前面呢? 哈哈,答案是完全可能,就打个比方,我们一共3个空间,加了5次元素,删了3次元素(增删结合的),那么物理结构上,rear超过了k是不是就要回到下标为0的位置重新开始,所以,我们还需要重新考虑一下。你真的会数据结构吗:队列,你真的学懂了数据结构?,c语言,数据结构,算法

        如图,在增了1,2,3的基础上,删了1和2,然后再增4和5,此时队列也是满的,但是tail%k就不算front了,那咋办?害,其实很简单,tail%k不行,那我们就(k+1)%(k+1) 不就好了,这样子就当tail在front的前面后面都可以解决啦!代码实现如下:

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->front == (obj->rear + 1) % (obj->k+1);
}

        也是很短的一行啊,代码虽短,思考很多!切记!切记!切记! 

        OK,那么接下来就是要开始返回队头数据了,当我们的思路清晰后,后面的实现其实也没什么难度了: 

nt myCircularQueueFront(MyCircularQueue* obj) {
//队列为空
    if(myCircularQueueIsEmpty(obj))
    return -1;
    return obj->a[obj->front];
}

        返回队尾元素,简单!直接返回 obj->a[obj->rear] 结束!对吗?○( ^皿^)っHiahiahia… 那当然不对了,对的话大伟也不会提出来对吧? 

        那大家想想问题出现在哪里?是的,细心的铁汁就会发现还是物理结构逻辑结构的冲突,当我们的rear指向物理结构,也就是数组的第一个元素时,我们需要返回的却是数组的最后一个元素,这里可能会有点绕,但是我相信凭你们的智商肯定会想明白。

        所以该怎么解决呢?当然,还是无敌的 “%” 神器,我们加上数组实际(不含加的空间)的长度,再%数组的总长度,不就好了?代码如下:

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    return obj->a[(obj->rear+obj->k) % (obj->k+1)];
}

         讲了这些,接下来就到了最重要的插入和删除了!首先是插入


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//若满了,就不好插入了
    if(myCircularQueueIsFull(obj))
    return false;

    obj->a[obj->rear] = value;
    obj->rear++;
//这一步取模很重要,解决了越界的问题
    obj->rear %= (obj->k+1);
    return true;
}

        然后是删除


bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//若队列为空
    if(myCircularQueueIsEmpty(obj))
    return false;

    obj->front++;
//同样取模
    obj->front %= (obj->k+1);
    return true;
}

        到这里有铁汁问大伟了,前面的讲的这么详细,到了后面最重要的地方反而一笔带过,为啥?为啥?竟然问我为啥?原因很简单啊,当然是没必要了,这种题目考的是啥?就是思维细节的处理,代码的难度高不高?不高鸭,理解了就很好写的,对吧?

        废话不多说了,让我们完成最后的销毁链表,迎向成功吧!:


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

        到此,整个题目也算是写完了,只需要用手指轻点一下提交,一个漂亮的通过就生成啦!

ヽ( ̄ω ̄( ̄ω ̄〃)ゝ 

        其实我们再返回过来看这个题目,感觉也么多难,但是怎么就是写不出来呢?大伟有一些拙见:1.思维(决定代码整体的走向与实现算法,是开始写之前就需要决定好的)2.细节(有些刁钻的实例总喜欢找代码中不足的地方,而只有全面思考,才能一次性通过)3.心态(不知道大家有没有这种情况,就是有些题目挺难的,我们也花了挺长时间的,但是左改右改就是改不对,每到这个时候就是自我生气,从而导致更难成功)

        所以我是希望以后刷题的时候大家(包括博主自己啦)从这三个方面思考。

         到这里本篇博客已经可以是完结了,接着栈后面就是二叉树了,下篇文章我会对大家介绍,请大家继续支持大伟,谢啦!!☆⌒(*^-゜)v 

  • Knowledge makes humble, ignorance makes proud. 知识使人谦虚,无知使人骄傲。

        本篇博客也就到此为止了,送大家一碗鸡汤,勉励自己以及这世界上所有追逐梦想的赤子趁年华尚好努力提升自己,莫欺少年穷!   你真的会数据结构吗:队列,你真的学懂了数据结构?,c语言,数据结构,算法

 文章来源地址https://www.toymoban.com/news/detail-839582.html

到了这里,关于你真的会数据结构吗:队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——队列(C语言实现)

    队列是一种特殊的线性结构,数据只能在一端插入,数据也只能在另一端进行删除。插入数据的那一端称之为队尾,插入数据的动作称之为入队。删除数据的那一端称之为队头,删除数据的动作称之为出列。队列遵守的是FIFO原则(Frist In First Out),即先进先出原则。 队列具

    2024年02月03日
    浏览(79)
  • C语言实现队列--数据结构

    😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️ 💥个人主页:🔥🔥🔥大魔王🔥🔥🔥 💥所属专栏:🔥魔王的修炼之路–数据结构🔥 如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的 点赞 👍和 关注 💖,支持一

    2024年02月05日
    浏览(45)
  • 数据结构:队列(Python语言实现)

    队列是一种 先进先出 的数据结构(特殊的线性结构),在队列 尾部 插入新元素,在队列 头部 删除元素。 一般队列的基本操作如下: create:创建空队列。 enqueue:将新元素加入队列的尾部,返回新队列。 dequeue:删除队列头部元素,返回新队列。 front:返回队列头部的元素

    2024年02月13日
    浏览(45)
  • c语言的数据结构:队列

    动态内存分配:链表在C语言中通常使用动态内存分配,这意味着可以在运行时根据需要动态地添加或删除节点。这对于实现一个动态大小的队列非常有用,因为队列的大小可以在运行时变化。相比之下,数组的大小通常是固定的,需要在编译时确定,这可能会限制队列的灵活

    2024年03月14日
    浏览(39)
  • 【数据结构】C语言队列(详解)

    前言: 💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥 ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现队列 目录 一.队列概念及结构 1.1队列的概念 1.2队列的结构 二.队列的实现 2.1头文件 2.2链式队列的结构定义 2.3队列接口的定义 2.4初始化队列 2.5判断队列

    2024年02月10日
    浏览(44)
  • 【C语言】动态内存管理(C语言的难点与精华,数据结构的前置知识,你真的掌握了吗?)

    学习专栏 : 《零基础学C语言》 《数据结构世界》 俗话说的好,要想学好 数据结构 (数据结构世界,对数据结构感兴趣的小伙伴可以移步),就必须学好以下三方面知识: 指针 不允许你还不了解指针的那些事(一)(内存和地址+指针变量+指针运算+野指针+传址调用) 不

    2024年02月05日
    浏览(43)
  • [数据结构 -- C语言] 队列(Queue)

    目录 1、队列 1.1 队列的概念及结构 2、队列的实现 2.1 接口 3、接口的实现 3.1 初始化队列 3.2 队尾入队列 分析: 3.3 队头出队列 分析: 3.4 获取队列头部元素 3.5 获取队列尾部元素 3.6 获取队列中有效元素个数 3.7 检测队列是否为空 3.7.1 int 类型判空 3.7.2 bool 类型判空 3.8 销毁队

    2024年02月07日
    浏览(45)
  • 【数据结构】队列---C语言版(详解!!!)

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

    2024年02月10日
    浏览(52)
  • 【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(43)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

    2024年02月08日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包