大家好，感谢邀请，今天来为大家分享一下queue-queue的中文意思的问题，以及和的一些困惑，大家要是还不太明白的话，也没有关系，因为接下来将为大家分享，希望可以帮助到大家，解决大家的问题，下面就开始吧！
想象一下我们日常的排队买票，只能向队尾插入数据，然后从队头取数据。在大型项目中常用的消息中间件就是一个队列的非常好的实现。
一个队列需要一个enQueue入队列操作和一个DeQueue操作，当然还可以有一些辅助操作，比如isEmpty判断队列是否为空，isFull判断队列是否满员等等。
为了实现在队列头和队列尾进行方便的操作，我们需要保存队首和队尾的标记。
先看一下动画，直观的感受一下队列是怎么入队和出队的。
先看入队：
再看出队：
可以看到入队是从队尾入，而出队是从队首出。
和栈一样，队列也有很多种实现方式，最基本的可以使用数组或者链表来实现。
先考虑一下使用数组来存储数据的情况。
我们用head表示队首的index，使用rear表示队尾的index。
当队尾不断插入，队首不断取数据的情况下，很有可能出现下面的情况：
上面图中，head的index已经是2了，rear已经到了数组的最后面，再往数组里面插数据应该怎么插入呢？
如果再往rear后面插入数据，head前面的两个空间就浪费了。这时候需要我们使用循环数组。
循环数组怎么实现呢？只需要把数组的最后一个节点和数组的最前面的一个节点连接即可。
有同学又要问了。数组怎么变成循环数组呢？数组又不能像链表那样前后连接。
不急，我们先考虑一个余数的概念，假如我们知道了数组的capacity，当要想数组插入数据的时候，我们还是照常的将rear+1，但是最后除以数组的capacity, 队尾变到了队首，也就间接的实现了循环数组。
看下java代码是怎么实现的：
大家注意我们的enQueue和deQueue中使用的方法：
这两个就是循环数组的实现。
上面的实现其实有一个问题，数组的大小是写死的，不能够动态扩容。我们再实现一个能够动态扩容的动态数组实现。
需要注意的是，在进行数组扩展的时候，我们不能简单的进行拷贝，因为是循环数组，可能出现rear在head后面的情况。这个时候我们需要对数组进行特殊处理。
其他部分是和普通数组实现基本一样的。
除了使用数组，我们还可以使用链表来实现队列，只需要在头部删除和尾部添加即可。
看下java代码实现：
上面的3种实现的enQueue和deQueue方法，基本上都可以立马定位到要入队列或者出队列的位置，所以他们的时间复杂度是O(1)。
本文的代码地址：
learn-algorithm
本文已收录于 http://www.flydean.com/12-algorithm-queue/
最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！
欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！
NVMe系列二：队列(Queue)管理
在上一篇文章(NVMe系列专题之一：NVMe技术概述)中，我们提到了NVMe有一个很大的优势就是队列深度达到了64K，并且支持队列个数最大可达64K。所以呢，这里我们就先聊聊NVMe中队列相关的一些知识点。
队列，在NVMe协议中，是专门为NVMe命令服务的。介绍队列之前，我们还是先看看NVMe定义的命令种类：
NVMe定义的命令很简单，只有两种:Admin Command和IO Command。加起来总共只要求13个(10 Admin Commands + 3 IO Commands)，相比于ATA Commands，真是减少了很多~
- 当Host要下发Admin command时，需要一个放置Admin command的队列，这个队列就叫做Admin Submission Queue, 简称Admin SQ.
- Device执行完成Admin command时，会生成一个对应的Completion回应，此时也需要一个放置Completion的队列，这个队列就叫做Admin Completion Queue，简称Admin CQ.
同样，执行IO Command时，也会有对应的两个队列，分别是IO SQ和IO CQ。
NVMe Spec对Admin SQ/CQ和IO SQ/CQ有不同的约定：
系统中只有一对Admin SQ/CQ，则可以有最多64K对 IO SQ/CQ;
Admin SQ/CQ的队列深度是2~4K；而IO SQ/CQ的队列深度是2~64K;
注: Admin/IO command大小为64B，对应的Completion大小为16B。
Admin SQ和CQ是一对一的，而IO SQ和CQ可以一对一，也可以多对一。多个SQ可以支持多线程工作，不同SQ之间可以赋予不同的优先级;
Admin和IO的SQ/CQ均放在Host端Memory中；
SQ由Host来更新，CQ则由NVMe Controller更新。
SQ/CQ是队列，那就应该有队列的头(Head)和尾(Tail)。在NVMe Spec中定义SQ/CQ均是循环队列，可以理解为一个圆形(如下图左)，但是内存中实际的长条状的(如下图右)，其实，队列可以是连续的物理空间，也可以不连续。
Tail: 指向队列中的下一个空位；
Head: 指向下一个将要被执行的命令所在的位置。
当队列为空时，Head==Tail;
当队列为满时，Head==Tail+1;
我们先看一下NVMe Spec中Command执行的整个流程再回过来审视一下这个问题。
在NVMe Spec中Command执行的流程有八步，Host与Controller之间用PCIe TLP传递信息。
Host提交新的Command。Host下发一个新Command时，将其放入Host内存中SQ;
Host通知Controller提取Command
Host把Command写入SQ之后，此时Device并不知道这件事。所以，Host此时需要给Controller发信息，通知NVMe Controller:\\”我提交了新的命令请求，麻烦尽快帮忙处理！\\”。这个过程通过更新在Controller内部的寄存器SQ Tail Doorbell来完成。
NVMe Controller从SQ提取Command
取走Command之后，需要在Controller内部的SQ Head Pointer寄存器中更新Head所在的位置。NVMe没有规定Command存入队列的执行顺序，Controller可以一次取出多个Command进行批量处理。
NVMe Controller执行从SQ提取的Commands
一个队列中的Command执行顺序是不固定的（可能导致先提交的请求后处理），这涉及到NVMe Spec定义的命令仲裁机制，在后续文章中介绍。执行Read/Wirte Command时，这个过程也会与Host Memory进行数据传递。
NVMe Controller将Commands的完成状态写入CQ
此时，Controller需要更新CQ Tail Pointer寄存器。
NVMe Controller通知Host检查Commands的完成状态
Controller通过发送一个中断信息告知Host:\\”您提交的Commands，我已经执行完毕了，请您检查结果！\\”。
Host检查CQ中的Completion信息
Host告知Controller已处理完成Completion信息。
此时，Host更新Controller内部的CQ Head Doorbell。告知Controller:\\”您发送回来的Command执行结果，我已处理完毕，非常感谢！\\”。
看完上面NVMe Command执行流程之后，我们再回过头来看一下刚才我们的问题:\\”有了SQ/CQ是不是就可以放心的执行Command了呢？\\”.
答案是否定的。从上述Command执行流程中，我们发现除了SQ/CQ之外，还有两个关键的\\”人物\\”:PCIe TLP和寄存器.
在之前的PCIe专题(PCIe系列专题之二：2.2 TLP事务处理方式解析)中，我们有介绍过PCIe TLP的类型有很多，如下图，不过，NVMe只挑选了Memory Read/Wirte传递信息。
注：Non-Posted: 需要completion返回响应包；Posted: 不需要completion返回响应包
NVMe Command执行过程中所需的寄存器有两种：Doorbell Register和Pointer Register。Doorbell，可以简称DB，是NVMe Spec定义的寄存器；Pointer register 是主控厂商自定义的寄存器，归纳一下：
从上表的信息中，不知道聪慧的你，有没有发现：
这个四个寄存器全部放在Controller内存中。也就是说Controller知道这SQ Tail/Head和CQ Tail/Head的全部信息。
而Host仅仅知道自己更新的两个信息SQ Tail和CQ Head。
很显然，Host与Controller之间的信息是不对等的。不过，还好Controller是个乐于分享的人。Controller会与Host共享自己所知的信息。那Controller怎么把SQ Head和CQ Tail的信息告知Host呢？
不怕，聪明如你！Controller把SQ Head和CQ Tail的信息写入了Completion报文中，如下图：
SQ Head Pointer就是SQ Head的信息。
P代表着Phase bit。CQ队列中所有的位置会被初始为0， 当有新的Completion信息写入时，Phase bit被置为1. Host通过读取Host 内存中CQ的Phase bit信息就能判断中CQ Tail的位置。
1. Set Feature
首先，看全局，如下图，
结合前面介绍的Command执行流程的八步分解Trace:
(1)第一步是Host向Host内存中的SQ写入新的Command。因为这部分是在Host内部执行的，所以在PCIe Trace中没有体现。
(2)第二步是Host更新Controller内存中的SQ Tail DB，告知Controller过来提取Command。
PCIe通过Memory Write TLP(Posted)完成Host对SQ Tail DB的更新。从下图的Trace中，我们可以看到SQ Tail=0x1E（先记住这个值哈，后面有用）. SQ Tail DB在Controller内存中的位置=0xFB301000.
(3)第三步是Controller去Host内存中的SQ中取回Command。Controller通过发送Memory Read TLP（Non-Posted）从Host内存提取Command。SQ在Host内存中的位置=0x10040C740. 读出数据的长度=0x40（64），这个也是NVMe规定Command的长度64B。
因为Memory Write是Non-Posted TLP，所以Host会发回一个Memory Write对应的Completion TLP。(需要注意的是在Xgig PCIe设备中，此时MRd的CpID被叫做了ASubmQ，实际就是CpID)
从CpID中包含取回Command的一些信息，比如这个Set feature命令是为了改变NVMe设备的Power state.
(4)第四步是在Controller内部开始执行上一步取回的Set feature命令。此时在PCIe链路中没有交互，所以在PCIe Trace中看不到执行过程的Trace。
(5)第五步是Controller更新CQ，反馈Set feature命令执行结果。
Controller发送Memory Write TLP将set feature命令执行结果写入CQ。此时CQ在Host内存中的位置=0x10041090. 同时在告知Host SQ Head的位置=0x1E。还记得第二步中SQ Tail=0x1E这个信息吗？ Head==Tail就说明了SQ现在空了。此外，还有一个信息就是Phase Tag=1, 代表Host CQ中有新增Completion信息。
(6)第六步是Controller通知Host检查Set feature命令执行结果。这个过程中，Controller通过发送MSI-X中断告知Host去检查CQ中的返回结果。
(7)第七步是Host检查CQ中的Set feature命令执行结果。这个过程时在Host内部实现的，在PCIe Trace中也没有体现。
(8)第八步是Host更新Controller内存中的CQ Head DB，告知Controller:\\”您的完成报告我已经处理完了，非常感谢您！\\” 从Trace中可以看到，CQ Head的位置=0x1A. CQ Head DB在Controller内部的位置=0xFB301004.
2. Read
如果你还想了解更多这方面的信息，记得收藏关注本站。
用户评论
江山策
队长！不就是队伍排队的意思吗？ 哈哈，这词儿挺形象，直接就体现了“排队”的状态。
有14位网友表示赞同！
窒息
看了下解释后觉得还挺有意思。用“Queue-Queue”做中文翻译，或许还能理解为一种更加拟人的表达方式，增添了一些趣味性。
有5位网友表示赞同！
独角戏°
这种新词的出现，是不是也反映了现在科技语言和日常生活词汇融合越来越强的趋势？
有19位网友表示赞同！
￡烟消云散
说实话感觉有点别扭，还是用“排队”这个老字更顺口些。毕竟它已经深入人心了，大家都习惯用了。
有7位网友表示赞同！
哭着哭着就萌了°
其实不管是“queue-queue”还是“排队”，都指向同一件事，只要能理解对方的意思就好嘛！过度纠结名称反而没必要。
有7位网友表示赞同！
空谷幽兰
在某些特定的领域，比如软件开发或者技术文档，这种新词的确会更加精准地传达信息，方便专业人士交流。但是对普通大众来说，也许还是“排队”更易懂一些。
有11位网友表示赞同！
未来未必来
翻译成中文“队列”。我觉得还是直接用英文“Queue-Queue”比较好，避免了多余的解释和可能存在的理解偏差。
有13位网友表示赞同！
何年何念
我平时常在手机软件里看到“queue”，所以已经习惯了这种说法。这篇博文让我认识到，“queue-queue” 其实就是中文翻译里的“排队”。
有18位网友表示赞同！
微信名字
挺有意思的！现在年轻人玩技术词汇真是一把好手，"Queue-Queue" 感觉很酷似的。
有9位网友表示赞同！
青衫故人
对科技领域的理解有限。希望能够通过这种新词的解释，更好地了解一些专业知识！谢谢分享！
有5位网友表示赞同！
寂莫
其实很多时候“queue” 不一定是人排队的意思，它在计算机科学中也有其他的含义，比如数据传输的队列、程序执行的顺序等等。
有16位网友表示赞同！
拥菢过后只剰凄凉
看来英语词汇还真是广泛影响着我们日常使用的话语。学习起来压力山大啊！
有11位网友表示赞同！
拥抱
我的经验是：面对不懂的词语，遇到就查，多了解的多好啊！这样才能跟上时代步伐！
有12位网友表示赞同！
孤街浪途
感觉标题有点 misleading，以为是关于排队的什么新鲜事，结果只是解释一个单词。。。
有19位网友表示赞同！
雨后彩虹
"Queue-Queue" 这样的词汇不就是一种语言风格吗？就像当年的人们把 "Cool" 当作流行语一样。接受新事物也需要度量一下！
有6位网友表示赞同！
白恍
我觉得这篇文章很有价值，帮助我理解了"queue-queue" 这个词的含义和由来。原来它不仅仅是一种简单的“排队”，还有更深层的信息表达。
有15位网友表示赞同！
猫腻
以后遇到这种奇怪的词汇，可以参考这种博客文章的方式进行解释！学习新知识真是方便了许多!
有10位网友表示赞同！