龙空技术网

数据结构|队列

自考的程序员 139

前言:

现时各位老铁们对“队列元素个数怎么求”都比较珍视,你们都想要分析一些“队列元素个数怎么求”的相关文章。那么小编在网络上汇集了一些关于“队列元素个数怎么求””的相关知识,希望看官们能喜欢,兄弟们一起来了解一下吧!

一、队列的定义

队列(queue):队列是只允许在-端进行插入操作,而在另-端进行删除操作的线性表。队列是一种先进先出 (First In First Out) 的线性表,简称 FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。

队列

队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:

队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构。在队尾添加元素,在队头删除元素。

线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。队列作为一种特殊的线性表,也同样存在着这两种存储方式。

二、队列的顺序存储

我们假设一个队列有 n 个元素,则顺序存储的队列需建立一个大于 n 的数组,并把队列的所有元素存储在数组的前 n 个单元,数组下标为0的一端即是队头。

队列的顺序存储

顺序存储的入队操作:

所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度O(1)。

顺序存储的入队操作

顺序存储的出队操作:

队列与栈不同的是,队列元素的出队是在队头,即下标为0的位置,所以队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时时间复杂度为O(n)

顺序存储的出队操作

我们发现队列的顺序存储与现实情况非常相似,大家排队做核酸,先来的人先去做,当第一个人做完核酸离队后,其他人都向前进一位。我们可以发现,现在我们是限制了元素必须存储在顺序表的前 n 个元素,如果我们不限制元素在顺序表的位置,该如何做呢。

三、首尾指针的顺序存储

front 指针指向队头元素 , rear 指针指向队尾元素的一个位置。假设数组的长度为 5,初始状态,空队列时 front rear指针均指向下标为0的位置

空队列

然后入队a1a2a3、a4,front指针依然指向下标为0位置,而rear指针指向下标为4的位置。

入队

出队 a1、a2 ,则front指针指向下标为2的位置, rear 不变。

出队

再入队 a5,此时数组已经溢出了,但是下标为0,1的位置实际上是空闲的。

假溢出

由上图我们发现,队列的大小是5,但实际上我们只有3个元素,由于 rear 指针已经在数组尾部,再进行入队就发生了数组的越界,这就是顺序队列的“假溢出”现象。

四、循环队列

解决假溢出的办法就是后面满了,就从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列

我们接着处理上面入队 a5元素的操作,如果是循环队列,我们可以把 rear 指针指向下标0的位置。

循环队列

接着入队a6,将它放置于下标为0处, rear 指针指向下标为1处。

入队

接着入队a7,将它放置于下标为1的位置rear 指针指向下标为2处。

入队

此时我们发现 rear 与 front 相等,队列却满了,这不就与空队列为空的判断条件冲突了吗;在实际开发中,我们会预留一个空位置,就是数组只有一个空位置时,我们就认为队列满了。

队满

由于 rear 可能比 front大,也可能比 front小,所以尽管它们只相差一个位置时就是队满的情况,但也可能是相差整整一圈。 我们假设队列的大小为QueueSize。

空队列:rear=front;队列满:(rear+1) % QueueSize=front队列元素的个数:(rear-front+QueueSize) %QueueSize五、队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已, 我们把它简称为链队列 。为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。

队列的链式存储结构

空队列时, front和 rear都指向头结点。

空队列

数据结构:

  class Node<T>{    //数据    T data;    //下一个元素指针    Node next;  }  class Queue{    //头指针    Node front;    //尾指针    Node rear;  }
六、队列的应用

1、键盘的输入与输出,比如你微信聊天输入god,由于队列是先进先出所以出来就是 god,如果是栈就是 dog。

2、打印机的任务

3、编程语言中线程池的任务队列

4、现在很多的消息中间件MQ

5、图的遍历

标签: #队列元素个数怎么求 #输出顺序队列中的所有元素