- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
队列也是一种操作受限的线性数据结构,与栈很相似.
栈的操作受限表现为只允许在队列的一端进行元素插入操作,在队列的另一端只允许删除操作。这一特性可以总结为先进先出(First In First Out,简称FIFO)。这意味着在队列中第一个加入的元素将第一个被移除.
入队:向队列中添加新元素的行为叫做入队; 。
出队:从队列中移除元素的行为叫做出队; 。
队头:在队列中允许进行元素移除行为的一端称为队头; 。
队尾:在队列中运行进行元素添加行为的一端称为队尾; 。
空队列:当队列中没有元素时称为空队列.
满队列:当队列是有限容量,并且容量已用完,则称为满队列.
队列容量:当队列是有限容量,队列容量表示队列可以容纳的最大元素数量.
队列大小:表示当前队列中的元素数量.
队列根据存储方式和功能特性有两种分类方式.
队列是逻辑结构,因此以存储方式的不同可以分为顺序队列和链式队列.
顺序队列就是所有的队列元素都存储在连续的地址空间中,因此可以通过数组来实现顺序队列,因为数组的特性也导致顺序队列容量是固定的,不易扩容,这也导致容易浪费空间,同时还要注意元素溢出等问题.
链式队列顾名思义就是采用链式方式存储,可以通过链表实现,因此链式队列可以做到无限扩容,大大的提高了内存利用率.
根据功能特性可以分类出很多专有队列,下面我们列举几个简单介绍一下.
阻塞队列:当空队列时会阻塞出队操作,当满队列时会阻塞入队操作.
优先队列:队列中每个元素都有一个优先级别属性,而元素的出队操作取决于这个优先级别属性,即优先级别高则优先出队.
延迟队列:队列中每个元素都标记一个时间记录,元素只有在指定的延时时间后才会触发出队操作.
循环队列:当使用数组实现队列时,可以通过把队头和队尾相连接,即当队尾到达数组的尾端可以“绕回”数组的开头,通过这种巧妙的设计来提高数组空间利用率.
双端队列:是一种两端都可以进行入队和出队操作的数据结构.
根据这些队列特性,在不同的场景中可以起到意想不到的效果.
下面我们将顺序队列和链式队列的实现进行详细讲解.
下面我们借助数组来实现顺序队列,其核心思想是把数组的起始位置作为队头,把数组尾方向作为队尾。当发生出队行为时,需要把剩余所有数据向队头方向移动一位,为什么要做这步操作呢?
首先顺序队列内部是数组,假设数组内可以存放7个元素,此时数组已存满,因此不可以再进行添加新元素入队操作了,然后我们对数组头元素进行出队操作,此时数组因为出队会留下一个空位,如下图.
那么此时是否可以进行入队操作呢?直接告诉我们应该可以,因为数组头已经有空位了。但是我们约定了队列只能从数组尾进行入队操作,而此时数组尾并没有空位提供给新入队的元素,因此实际上无法进行入队操作.
那要如何处理呢?最简单的方法就是当发生出队操作时,后面所有的元素都向着队头方向移动一位,把队尾空出一位,这每出一个元素就可以入一个元素.
当然这也不是唯一方案,还是通过循环队列解决这一问题,有兴趣的可以研究一下.
我们首先来定义顺序队列的ADT.
ADT Queue{ 。
数据对象:D 是一个非空的元素集合,D = {a1, a2, ..., an},其中 ai 表示队列中的第i个元素,n是队列的长度。
数据关系:D中的元素通过它们的索引(位置)进行组织,索引是从0到n-1的整数,并且遵循元素先进先出的原则。
基本操作:[
Init(n) :初始化一个指定容量的空队列。
Capacity:返回队列容量。
Length:返回队列长度。
Head:返回队头元素,当为空队列则报异常。
Tail:返回队尾元素,当为空队列则报异常。
IsEmpty():返回是否为空队列。
IsFull():返回是否为满队列。
Enqueue():入队即添加元素,当为满队列则报异常。
Dequeue():出队即返回队头元素并把其从队列中移除,当为空队列则报异常。
] 。
} 。
定义好队列ADT,下面我们就可以开始自己实现的队列.
首先定义3个变量用于存放队列元素数组、队列容量以及队尾索引,而没有定义队头索引是因为队头索引永远等于0.
初始化结构主要做几件事.
初始化队列的容量; 。
初始化存放队列元素数组; 。
初始化队尾索引; 。
具体实现代码如下:
//存放队列元素
private T[] _array;
//队列容量
private int _capacity;
//队尾索引,为-1表示空队列
private int _tail;
//初始化队列为指定容量
public MyselfQueueArray<T> Init(int capacity)
{
//初始化队列容量为capacity
_capacity = capacity;
//初始化指定长度数组用于存放队列元素
_array = new T[_capacity];
_tail = -1;
//返回队列
return this;
}
这个比较简单直接把队列容量私有字段返回即可.
//队列容量
public int Capacity
{
get
{
return _capacity;
}
}
我们并没有定义队列长度的私有字段,因为队尾索引即表示数组最后一个元素索引,即可以代表队列长度,因此只需用队尾索引加1即可得到队列长度,同时需要注意判断队列是否为空,如果为空则报错.
//队列长度
public int Length
{
get
{
if (IsEmpty())
{
return 0;
}
//队列长度等于队尾索引加1
return _tail + 1;
}
}
基于我们上面的约定,队头元素永远对应数组的第一个元素,因此可以直接获取索引为0的数组元素。空队列则报错。具体代码如下:
//获取队头元素
public T Head
{
get
{
if (IsEmpty())
{
//空队列,不可以进行获取队头元素操作
throw new InvalidOperationException("空队列");
}
return _array[0];
}
}
因为我们定义了队尾索引私有变量,因此可以直接通过队尾索引获取。具体代码如下:
//获取队尾元素
public T Tail
{
get
{
if (IsEmpty())
{
//空队列,不可以进行获取队头元素操作
throw new InvalidOperationException("空队列");
}
return _array[_tail];
}
}
是否空队列只需判断队尾索引是否小于0即可.
//是否空队列
public bool IsEmpty()
{
//队尾索引小于0表示空队列
return _tail < 0;
}
是否满队列只需判断队尾索引是否与队列容量减1相等,代码如下:
//是否满队列
public bool IsFull()
{
//队头索引等于容量大小减1表示满队列
return _tail == _capacity - 1;
}
入队只需向队列内部数组尾添加一个新元素即可,因此先把队尾索引先后移动一位,然后再把新元素赋值给队尾元素,同时还需要检查是否为满队列,如果是满队列则报错,具体实现代码如下:
//入队
public void Enqueue(T value)
{
if (IsFull())
{
//满队列,不可以进行入队列操作
throw new InvalidOperationException("满队列");
}
//队尾索引向后移动1位
_tail++;
//给队尾元素赋值新值
_array[_tail] = value;
}
出队则大致分为以下几步:
判断是否为空队列,空队列则报错; 。
取出队头元素暂存,重置队头元素为默认值; 。
把队头后面所有元素向队头方向移动一位; 。
重置队尾元素为默认值; 。
队尾索引向队头方向移动一位,即队尾索引减1; 。
返回暂存的队头元素; 。
具体实现代码如下:
//出队
public T Dequeue()
{
if (IsEmpty())
{
//空队列,不可以进行出队列操作
throw new InvalidOperationException("空队列");
}
//取出队头元素
var value = _array[0];
//对头元素重置为默认值
_array[0] = default;
//队头元素后面所有元素都向队头移动一位
for (int i = 0; i < _tail; i++)
{
_array[i] = _array[i + 1];
}
//队尾元素重置为默认值
_array[_tail] = default;
//队尾索引向队头方向移动一位
_tail--;
//返回队头元素
return value;
}
我们借助链表来实现链式队列,其核心思想是把链表尾节点作为队尾,把链表首元节点作为队头.
相对于顺序队列的ADT来说,链式队列的ADT少了两个方法即获取队列容量和是否满队列,这也是链表特性带来的好处.
首先需要定义链表节点类,包含两个属性数据域和指针域.
然后需要定义3个变量用于存放队头节点、队尾节点以及队列长度.
而初始化结构主要初始化3个变量初始值,具体实现如下:
public class MyselfQueueNode<T>
{
//数据域
public T Data;
//指针域,即下一个节点
public MyselfQueueNode<T> Next;
public MyselfQueueNode(T data)
{
Data = data;
Next = null;
}
}
public class MyselfQueueLinkedList<T>
{
//队头节点即首元节点
private MyselfQueueNode<T> _head;
//队尾节点即尾节点
private MyselfQueueNode<T> _tail;
//队列长度
private int _length;
//初始化队列
public MyselfQueueLinkedList<T> Init()
{
//初始化队头节点为空
_head = null;
//初始化队尾节点为空
_tail = null;
//初始化队列长度为0
_length = 0;
//返回队列
return this;
}
}
这个比较简单直接把队列长度私有字段返回即可.
//队列长度
public int Length
{
get
{
return _length;
}
}
获取队头元素可以通过队头节点数据域直接返回,但是要注意判断队列是否为空队列,如果为空队列则报异常。具体代码如下:
//获取队头元素
public T Head
{
get
{
if (IsEmpty())
{
//空队列,不可以进行获取队头元素操作
throw new InvalidOperationException("空队列");
}
//返回队头节点数据域
return _head.Data;
}
}
获取队尾元素可以通过队尾节点数据域直接返回,但是要注意空栈则报异常。具体代码如下:
//获取队尾元素
public T Tail
{
get
{
if (IsEmpty())
{
//空队列,不可以进行获取队尾元素操作
throw new InvalidOperationException("空队列");
}
//返回队尾节点数据域
return _tail.Data;
}
}
是否空队列只需判断队头节点和队尾节点是否都为空即可.
//是否空队列
public bool IsEmpty()
{
//队头节点为null和队尾节点都为空表示空队列
return _head == null && _tail == null;
}
入队大致分为以下几步:
需要先创建一个新节点; 。
如果原队尾节点不为空,则把原队尾节点指针域指向新节点; 。
把原队尾节点更新为新节点; 。
如果队头节点为空,则说明这是第一个元素,所以队头和队尾都是同一个节点,因此要把队尾节点赋值给队头节点; 。
队列长度加1; 。
具体实现代码如下:
//入队
public void Enqueue(T value)
{
//创建新的队尾节点
var node = new MyselfQueueNode<T>(value);
//如果队尾节点不为空,则把新的队尾节点连接到尾节点后面
if (_tail != null)
{
_tail.Next = node;
}
//队尾节点变更为新的队尾节点
_tail = node;
//如果队头节点为空,则为其赋值为队尾节点
if (_head == null)
{
_head = _tail;
}
//队列长度加1
_length++;
}
出队则大致分为以下几步:
判断是否空队列,空队列则报错; 。
获取队头节点数据域暂存; 。
更新头节点为原队头节点对应的下一个节点; 。
如果队头节点为空,则说明为空队列,队尾节点也要置空; 。
队列长度减1; 。
返回暂存的队头节点数据; 。
具体实现代码如下:
//出队
public T Dequeue()
{
if (IsEmpty())
{
//空队列,不可以进行出队列操作
throw new InvalidOperationException("空队列");
}
//获取队头节点数据
var data = _head.Data;
//把队头节点变更为原队头节点对应的下一个节点
_head = _head.Next;
//如果队列为空,表明为空队列,同时更新队尾为空
if (_head == null)
{
_tail = null;
}
//队列长度减1
_length--;
//返回队头节点数据
return data;
}
注:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner 。
最后此篇关于数据结构-队列的文章就讲到这里了,如果你想了解更多关于数据结构-队列的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我遇到一种情况,我需要从某个主题读取(正在进行的)消息并将它们放入另一个 Queue 中。我怀疑我是否需要 jms Queue 或者我可以对内存中的 java Queue 感到满意。我将通过同一 jv
队列也是一种操作受限的线性数据结构,与栈很相似。 01、定义 栈的操作受限表现为只允许在队列的一端进行元素插入操作,在队列的另一端只允许删除操作。这一特性可以总结为先进先出(First In
队列的定义 队列(Queue):先进先出的线性表 队列是仅在队尾进行插入和队头进行删除操作的线性表 队头(front):线性表的表头端,即可删除端 队尾(rear):线性表的表尾端,即可插入端 由于这
Redis专题-队列 首先,想一想 Redis 适合做消息队列吗? 1、消息队列的消息存取需求是什么?redis中的解决方案是什么? 无非就是下面这几点: 0、数据可以顺序读
0. 学习目标 栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有着巨大的不
我想在 redis + Flask 和 Python 中实现一个队列。我已经用 RQ 实现了这样的查询,如果你有 Flask 应用程序和任务在同一台服务器上工作,它就可以正常工作。我想知道是否有可能创
我正在使用 Laravel 5.1,我有一个大约需要 2 分钟来处理的任务,这个任务特别是生成报告...... 现在,很明显,我不能让用户在我接受用户输入的同一页面上等待 2 分钟,而是我应该在后台处
我正在使用 Azure 队列,并且有多个不同的进程从队列中读取数据。 我的系统的构建方式假设每条消息只读取一次。 这个Microsoft article声称 Azure 队列具有至少一次传送保证,这可
我正在创建一个Thread::Queue元素数组。 我这样做是这样的: for (my $i=0; $i new; } 但是,当我在每个队列中填充这样的元素时 $queues[$index]->enq
我试图了解如何将我的 Mercurial 补丁推送到远程存储库(例如 bitbucket.org),而不必先应用它们(实际上提交它们)。我的动机是在最终完成之前首先对我的工作进行远程备份,并且能够与其
我的本地计算机上有一个 Mercurial 队列补丁,我需要与同事共享该补丁,但我不想将其提交到上游存储库。有没有一种简单的方法可以打包该补丁并与他分享? 最佳答案 mq 将补丁作为不带扩展名的文
Java 中是否有任何类提供与 Queue 相同的功能,但有返回对象的选项,并且不要删除它,只需将其设置在集合末尾? 最佳答案 Queue不直接提供这样的方法。但是,您可以使用 poll 和 add
我在Windows上使用Tortoise svn客户端,我需要能够一次提交来自不同子文件夹的更改文件-一次提交。像在提交之前将文件添加到队列中之类的?我该怎么做? Windows上是否还有另一个svn
好吧,我正在尝试对我的 DSAQueue 类进行单元测试,它显示我的 isEmpty()、isFull() 和 dequeue() 方法失败。 以下是我的 DSAQueue 代码。我认为我的 Dequ
我想尽量减少对传入请求的数据库查询。它目前需要写入 6 个不同的表。在返回响应之前不需要完成处理。因此,我考虑了 laravel 队列,但我想知道我是否也可以摆脱写入队列/作业表所需的单独查询。我可以
我正在学习队列数据结构。我想用链表创建队列。我想编程输出:10 20程序输出:队列为空-1 队列为空-1 我哪里出错了? 代码如下: class Node { int x; Node next
“当工作人员有空时,他们会根据主题的优先级列表从等待请求池中进行选择。在时间 t 到达的所有请求都可以在时间 t 进行分配。如果两名工作人员同时有空,则安排优先权分配给最近的工作最早安排的人。如果仍然
我正在开发一个巨大的应用程序,它使用一些子菜单、模式窗口、提示等。 现在,我想知道在此类应用程序中处理 Esc 和单击外部事件的正确方法。 $(document).keyup(function(e)
所以 如果我有一个队列 a --> b --> NULL; 当我使用函数时 void duplicate(QueueNodePtr pHead, QueueNodePtr *pTail) 它会给 a
我正在尝试为键盘输入实现 FIFO 队列,但似乎无法让它工作。我可以让键盘输入显示在液晶显示屏上,但这就是我能做的。我认为代码应该读取键盘输入并将其插入队列,然后弹出键盘输入并将值读取到液晶屏幕上。有
我是一名优秀的程序员,十分优秀!