Java-数据结构（三）------队列

- 日理万妓 2023-02-12 05:54 107阅读 0赞

## 一、什么是队列 ##

1、队列（简称作队，Queue）是一种特殊的线性表，差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作在其另一端进行删除操作。

2、队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。

3、队列的底层数据结构可以用数组来实现。

4、队列具有FIFO（先进先出）的特点。

## 二、3种队列的介绍 ##

Java 集合中的 Queue 继承自 Collection 接口 ，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。

**1、顺序队列**

![在这里插入图片描述][20200525215305539.png]

**特点**

顺序队列是常见的队列，从队尾添加元素，从对头删除元素。

**假溢出问题**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70]

PS：图片来源教材书籍

**缺点**

容易发生假溢出问题，当然如果确定不会发生溢出，也可以采用顺序队列

**2、循环队列**

如果队尾指针到达最后的时候，如果再往里面增加元素，我们使队尾指针指向队列的头部。

循环队列解决`假溢出`问题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 1]  
判断队列是满的还是空

front=(read+1) % length;

**缺点**

要求初始化时循环队列必须确定一个固定的长度，所以有储存元素个数的限制和浪费空间的问题；

**3、链式队列**

解决了普通队列的一些不足，那就是在空间上，链式队列更加灵活

用单链表存储队列，称为链队列。

定义front指针指向头结点，rear指针指向终端结点，空队列时，front和rear都指向头结点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 2]

**特点**

链队列没有溢出的问题，只有当内存没有可用空间时才会出现溢出，但是每个元素都需要一个引用域，从而产生了结构性开销。

**4、优先队列**

优先队列（PriorityQueue）是不同于普通队列的先进先出的队列，每次从队列中取出的是具有最高优先权的元素

案例：银行排队，vip客户优先

> PriorityQueue是从JDK1.5开始提供的新的数据结构接口。

如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列。

[20200525215305539.png]: https://img-blog.csdnimg.cn/20200525215305539.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020052522013934.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200525221143594.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200525224234875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70