Java数据结构和算法（五）——队列

桃扇骨 2022-03-16 10:48 217阅读 0赞

**目录**

*  [1、队列的基本概念][1]
 *  [2、Java模拟单向队列实现][2_Java]
 *  [3、双端队列][3]
 *  [4、优先级队列][4]
 *  [5、总结][5]

--------------------

前面一篇博客我们讲解了并不像数组一样完全作为存储数据功能，而是作为构思算法的辅助工具的数据结构——栈，本篇博客我们介绍另外一个这样的工具——队列。栈是后进先出，而队列刚好相反，是先进先出。

[回到顶部][Link 1]

### 1、队列的基本概念 ###

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

比如我们去电影院排队买票，第一个进入排队序列的都是第一个买到票离开队列的人，而最后进入排队序列排队的都是最后买到票的。

在比如在计算机操作系统中，有各种队列在安静的工作着，比如打印机在打印列队中等待打印。

队列分为：

①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。

②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。

这里我们还会介绍一种队列——优先级队列，优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

[回到顶部][Link 1]

### 2、Java模拟单向队列实现 ###

在实现之前，我们先看下面几个问题：

①、与栈不同的是，队列中的数据不总是从数组的0下标开始的，移除一些队头front的数据后，队头指针会指向一个较高的下标位置，如下图：

![1120165-20171129222048792-1660264024.png][]

②、我们再设计时，队列中新增一个数据时，队尾的指针rear 会向上移动，也就是向下标大的方向。移除数据项时，队头指针 front 向上移动。那么这样设计好像和现实情况相反，比如排队买电影票，队头的买完票就离开了，然后队伍整体向前移动。在计算机中也可以在队列中删除一个数之后，队列整体向前移动，但是这样做效率很差。我们选择的做法是移动队头和队尾的指针。

③、如果向第②步这样移动指针，相信队尾指针很快就移动到数据的最末端了，这时候可能移除过数据，那么队头会有空着的位置，然后新来了一个数据项，由于队尾不能再向上移动了，那该怎么办呢？如下图：

![1120165-20171129222912089-934400834.png][]

为了避免队列不满却不能插入新的数据，我们可以让队尾指针绕回到数组开始的位置，这也称为“循环队列”。

![1120165-20171129223015401-2128864629.png][]

弄懂原理之后，Java实现代码如下：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 </td> 
 <td> <code>package</code>&nbsp;<code>com.ys.datastructure;</code> &nbsp; <code>public</code>&nbsp;<code>class</code>&nbsp;<code>MyQueue { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>Object[] queArray;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//队列总大小</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>maxSize;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//前端</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>front;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//后端</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>rear;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//队列中元素的实际数目</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>nItems;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>MyQueue(</code><code>int</code>&nbsp;<code>s){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>maxSize = s;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queArray =&nbsp;</code><code>new</code>&nbsp;<code>Object[maxSize];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>front =&nbsp;</code><code>0</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>rear = -</code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>nItems =&nbsp;</code><code>0</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//队列中新增数据</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>void</code>&nbsp;<code>insert(</code><code>int</code>&nbsp;<code>value){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(isFull()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"队列已满！！！"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//如果队列尾部指向顶了，那么循环回来，执行队列的第一个元素</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(rear == maxSize -</code><code>1</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>rear = -</code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//队尾指针加1，然后在队尾指针处插入新的数据</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queArray[++rear] = value;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>nItems++;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//移除数据</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>Object remove(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Object removeValue =&nbsp;</code><code>null</code>&nbsp;<code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(!isEmpty()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>removeValue = queArray[front];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queArray[front] =&nbsp;</code><code>null</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>front++;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(front == maxSize){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>front =&nbsp;</code><code>0</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>nItems--;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>removeValue;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>removeValue;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//查看对头数据</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>Object peekFront(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>queArray[front];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//判断队列是否满了</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>isFull(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>(nItems == maxSize);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//判断队列是否为空</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>isEmpty(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>(nItems ==</code><code>0</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//返回队列的大小</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>int</code>&nbsp;<code>getSize(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>nItems;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

测试：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 </td> 
 <td> <code>package</code>&nbsp;<code>com.ys.test;</code> &nbsp; <code>import</code>&nbsp;<code>com.ys.datastructure.MyQueue;</code> &nbsp; <code>public</code>&nbsp;<code>class</code>&nbsp;<code>MyQueueTest { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>static</code>&nbsp;<code>void</code>&nbsp;<code>main(String[] args) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>MyQueue queue =&nbsp;</code><code>new</code>&nbsp;<code>MyQueue(</code><code>3</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queue.insert(</code><code>1</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queue.insert(</code><code>2</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queue.insert(</code><code>3</code><code>);</code><code>//queArray数组数据为[1,2,3]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(queue.peekFront());&nbsp;</code><code>//1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queue.remove();</code><code>//queArray数组数据为[null,2,3]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(queue.peekFront());&nbsp;</code><code>//2</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queue.insert(</code><code>4</code><code>);</code><code>//queArray数组数据为[4,2,3]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>queue.insert(</code><code>5</code><code>);</code><code>//队列已满,queArray数组数据为[4,2,3]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

[回到顶部][Link 1]

### 3、双端队列 ###

双端队列就是一个两端都是结尾或者开头的队列， 队列的每一端都可以进行插入数据项和移除数据项，这些方法可以叫做：

insertRight()、insertLeft()、removeLeft()、removeRight()

如果严格禁止调用insertLeft()和removeLeft()（或禁用右端操作），那么双端队列的功能就和前面讲的栈功能一样。

如果严格禁止调用insertLeft()和removeRight(或相反的另一对方法)，那么双端队列的功能就和单向队列一样了。

[回到顶部][Link 1]

### 4、优先级队列 ###

优先级队列（priority queue）是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

优先级队列 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有：

（1）查找

（2）插入一个新元素

（3）删除

一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素 。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

这里我们用数组实现优先级队列，这种方法插入比较慢，但是它比较简单，适用于数据量比较小并且不是特别注重插入速度的情况。

后面我们会讲解堆，用堆的数据结构来实现优先级队列，可以相当快的插入数据。

**数组实现优先级队列，声明为int类型的数组，关键字是数组里面的元素，在插入的时候按照从大到小的顺序排列，也就是越小的元素优先级越高。**

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 </td> 
 <td> <code>package</code>&nbsp;<code>com.ys.datastructure;</code> &nbsp; <code>public</code>&nbsp;<code>class</code>&nbsp;<code>PriorityQue { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>maxSize;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code><code>[] priQueArray;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>int</code>&nbsp;<code>nItems;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>PriorityQue(</code><code>int</code>&nbsp;<code>s){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>maxSize = s;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>priQueArray =&nbsp;</code><code>new</code>&nbsp;<code>int</code><code>[maxSize];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>nItems =&nbsp;</code><code>0</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//插入数据</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>void</code>&nbsp;<code>insert(</code><code>int</code>&nbsp;<code>value){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>j;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(nItems ==&nbsp;</code><code>0</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>priQueArray[nItems++] = value;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>j = nItems -</code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//选择的排序方法是插入排序，按照从大到小的顺序排列，越小的越在队列的顶端</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(j &gt;=</code><code>0</code>&nbsp;<code>&amp;&amp; value &gt; priQueArray[j]){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>priQueArray[j+</code><code>1</code><code>] = priQueArray[j];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>j--;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>priQueArray[j+</code><code>1</code><code>] = value;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>nItems++;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//移除数据,由于是按照大小排序的，所以移除数据我们指针向下移动</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//被移除的地方由于是int类型的，不能设置为null，这里的做法是设置为 -1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>int</code>&nbsp;<code>remove(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>k = nItems -</code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>value = priQueArray[k];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>priQueArray[k] = -</code><code>1</code><code>;</code><code>//-1表示这个位置的数据被移除了</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>nItems--;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>value;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//查看优先级最高的元素</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>int</code>&nbsp;<code>peekMin(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>priQueArray[nItems-</code><code>1</code><code>];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//判断是否为空</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>isEmpty(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>(nItems ==&nbsp;</code><code>0</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//判断是否满了</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>isFull(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>(nItems == maxSize);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

insert() 方法，先检查队列中是否有数据项，如果没有，则直接插入到下标为0的单元里，否则，从数组顶部开始比较，找到比插入值小的位置进行插入，并把 nItems 加1.

remove 方法直接获取顶部元素。

优先级队列的插入操作需要 O(N)的时间，而删除操作则需要O(1) 的时间，后面会讲解如何通过 堆 来改进插入时间。

[回到顶部][Link 1]

### 5、总结 ###

本篇博客我们介绍了队列的三种形式，分别是单向队列、双向队列以及优先级队列。其实大家听名字也可以听得出来他们之间的区别，单向队列遵循先进先出的原则，而且一端只能插入，另一端只能删除。双向队列则两端都可插入和删除，如果限制双向队列的某一段的方法，则可以达到和单向队列同样的功能。最后优先级队列，则是在插入元素的时候进行了优先级别排序，在实际应用中单项队列和优先级队列使用的比较多。后面讲解了堆这种数据结构，我们会用堆来实现优先级队列，改善优先级队列插入元素的时间。

通过前面讲的栈以及本篇讲的队列这两种数据结构，我们稍微总结一下：

①、栈、队列（单向队列）、优先级队列通常是用来简化某些程序操作的数据结构，而不是主要作为存储数据的。

②、在这些数据结构中，只有一个数据项可以被访问。

③、栈允许在栈顶压入（插入）数据，在栈顶弹出（移除）数据，但是只能访问最后一个插入的数据项，也就是栈顶元素。

④、队列（单向队列）只能在队尾插入数据，对头删除数据，并且只能访问对头的数据。而且队列还可以实现循环队列，它基于数组，数组下标可以从数组末端绕回到数组的开始位置。

⑤、优先级队列是有序的插入数据，并且只能访问当前元素中优先级别最大（或最小）的元素。

⑥、这些数据结构都能由数组实现，但是可以用别的机制（后面讲的链表、堆等数据结构）实现。

[1]: https://www.cnblogs.com/ysocean/p/7921930.html#_label0
[2_Java]: https://www.cnblogs.com/ysocean/p/7921930.html#_label1
[3]: https://www.cnblogs.com/ysocean/p/7921930.html#_label2
[4]: https://www.cnblogs.com/ysocean/p/7921930.html#_label3
[5]: https://www.cnblogs.com/ysocean/p/7921930.html#_label4
[Link 1]: https://www.cnblogs.com/ysocean/p/7921930.html#_labelTop
[1120165-20171129222048792-1660264024.png]: /images/20220316/faf84cdc25734889885f18b703180f9b.png
[1120165-20171129222912089-934400834.png]: /images/20220316/06815e787aed4f67bdf2ae16f28fce6d.png
[1120165-20171129223015401-2128864629.png]: /images/20220316/d88d2c48a50f46e1808c276581d1cd60.png