【JavaDS】队列与集合Queue,Deque的理解和使用

古城微笑少年丶 2023-09-26 10:24 13阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【Java实现数据结构】**][Java]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  一. 什么是队列
 *   *  1. 队列的特点
     *  2. 队列的模拟实现
     *  3. 循环队列
     *  4. 双端队列
 *  二. 集合-Queue,Deque
 *   *  1. 结构介绍
     *  2. 方法介绍

## 一. 什么是队列 ##

### 1. 队列的特点 ###

**队列**也是一种组织数据的方式 , 队列中的元素具有**先进先出**的特点 , 是**只允许在一端进行插入数据操作，在另一端进行删除数据操作**的特殊**线性表** .

![img][]

**队列的几个术语：**

*  进行**插入操作**的一端称做**队尾**（tail/rear）。
 *  进行**删除操作**的一端称做**队首或队头**（head/front）。
 *  向队列中**插入新元素**称为**进队或入队**，新元素进队后就成为新的队尾元素。
 *  从队列中**删除元素**称为**出队或离队**，元素出队后，其后继元素就成为队首元素。

### 2. 队列的模拟实现 ###

队列可以使用链表或者顺序表来实现 , 在Java集合框架中的队列就是用双链表来实现的 , 下文会介绍到双端队列和循环队列 , 在这里**采用单链表来实现队列** .

我们这里设置单链表中的两个引用head和tail用来指向头节点和尾节点 , 需要**注意**的是我们应该**让单链表的头做队头 , 单链表的尾做队尾** , 也就是从**单链表的尾入队 , 头出队 , 此时入队和出队操作的时间时间复杂度都为O(1)** ; 而如果反过来入队使用头插 , 入队的时间复杂度为O(1) , 此时出队要删除单链表最后一个节点 , 需要先找到其前一个节点 , 出队的时间复杂度就为O(N)了;

如果使用双链表来实现栈的话那就简单了 , 由于是是双向的 , 不管哪一端来做队头/队尾 , 时间复杂度都为O(1) ; 会了单链表的 , 双链表的不在话下了 .

![img][img 1]

**MyQueue.java**

public class MyQueue {
        
        static class ListNode {
        
            public int val;
            public ListNode next;
    
            public ListNode(int val) {
        
                this.val = val;
            }
        }
        public ListNode head;
        public ListNode tail;
        public int usedSzie;
    
        public void offer(int val) {
        
            ListNode node = new ListNode(val);
            if(this.head == null) {
        
                this.head = node;
                this.tail = node;
            }else {
        
                this.tail.next = node;
                this.tail = this.tail.next;
            }
            this.usedSzie++;
        }
    
        public int poll() {
        
            if(this.head == null) {
        
                throw new MyEmptyQueueException("当前队列为空");
            }
            int ret = this.head.val;
            this.head = this.head.next;
            //如果只有一个节点,要将tail置空
            if(this.head == null) {
        
                this.tail = null;
            }
            this.usedSzie--;
            return ret;
        }
    
        public int peek() {
        
            if(this.head == null) {
        
                throw new MyEmptyQueueException("当前队列为空");
            }
            return this.head.val;
        }
    
        public boolean empty() {
        
            return this.head == null;
        }
    
        public int getUsedSzie() {
        
            return this.usedSzie;
        }
    }

**MyEmptyQueueException.java**

public class MyEmptyQueueException extends RuntimeException{
        
        public MyEmptyQueueException() {
        
        }
    
        public MyEmptyQueueException(String message) {
        
            super(message);
        }
    }

**加泛型的写法**:

// 单链表实现队列
    class Node<V> {
        
        public V val;
        public Node<V> next;
    
        public Node(V val) {
        
            this.val = val;
        }
    }
    public class MyQueue<V> {
        
        private Node<V> head;
        private Node<V> tail;
        private int size;
    
        // 判断队列是否为空
        public boolean isEmpty() {
        
            return size == 0;
        }
        // 获取队列中元素的个数
        public int size() {
        
            return size;
        }
        // 元素入队
        public void offer(V val) {
        
            Node<V> cur = new Node<>(val);
            if (head == null) {
        
                head = cur;
                tail = cur;
            } else {
        
                // 尾插入队
                tail.next = cur;
                tail = cur;
            }
            size++;
        }
        // 元素出队
        public V poll() {
        
            V ret = null;
            if (head != null) {
        
                ret = head.val;
                head = head.next;
                size--;
            }
            if (head == null) {
        
                tail = null;
            }
            return ret;
        }
        // 查看队头元素
        public V peek() {
        
            V ret = null;
            if (head != null) {
        
                ret = head.val;
            }
            return ret;
        }
    }

### 3. 循环队列 ###

上面已经实现了用链表来实现队列 , 那么用顺序表如何来实现队列呢 ; 我们知道顺序表是具有随机访问的特点的 , 将若干个元素入队后 , 每次出队操作后 , 该元素原来所在的空间就无法再使用了 , 这就使得顺序表得空间利用不充分 ;

而如果采用循环队列就可以解决这个问题 , 如果数组最后一个空间已经有了元素 , 但前面由于出队有了空缺 , 此时再有元素入队就能重新从数组的尾部跳到数组的头部 , 对已经出队的空间进行重新利用 , 这样就避免了空间的浪费 .

![img][img 2]

实现循环队列还需要考虑的一个问题是，**如何确定队列是空还是满**？

这里我们设置**队头引用为front，队尾引用为rear，顺序表长度为len**。

*  **方式1**：

**记录队列元素个数size，当size的值与顺序表的长度相等时，代表队列已满 ; size值为0表示队列为空**。

*  **方式2**：

使用一个boolean类型的成员变量**flag标记**，初始为false，当每次成功入队时将flag设置为true，成功出队时将flag设置为false ; 那么，当front == rear && flag == true表示“在入队操作之后front == rear”, 显然入队造成的front == rear的原因就是队列满了 ; **所以 ,** **当rear == front && flag == true表示队列已满，同理 , 当rear == front && flag == false表示队列为空**。

*  **方式3**：

**牺牲一个单位的空间**，front 就指向队列的第一个元 , rear 指向队列的最后一个元素的后一个位置 , 在**每次入队前判断（rear+1）% len是否与front相等，如果相等表示队列已满，如果rear == front则表示队列为空。**

![img][img 3]

*  **数组下标循环的小技巧**

1.  往后走(offset 小于 array.length): index = (index + offset) % array.length

![img][img 4]

这里的意思是 , 长度为9的循环链表中 , 7下标位置 , 偏移4个位置 , 到了2位置

1.  往前走(offset 小于 array.length): index = (index + array.length - offset) % array.length

![img][img 5]

这里的意思是 , 长度为9的循环链表中 , 2下标位置 , 偏移4个位置 , 到了7位置

### 4. 双端队列 ###

**双端队列**是指**两端都可以进行进队和出队**操作的队列，将队列的两端分别称为前端和后端，两端都可以入队和出队。

**双端队列同时遵守了先进先出和后进先出的原则，所以可以说它是一种把队列和栈相结合的一种数据结构** ;

所以双端队列既能够当队列使用，也能当栈使用，Java底层是使用双链表(LinkedList)来实现双端队列(Deque)和队列(Queue)的 ;

限制一端进行出队或入队的双端队列称为受限的双端队列。

![img][img 6]  
代码实现:

// 用双链表实现双端队列
    public class MyDeque<V> {
        
        public static class Node<V> {
        
            public V val;
            public Node<V> last;
            public Node<V> next;
    
            public Node(V val) {
        
                this.val = val;
            }
        }
    
        private Node<V> head;
        private Node<V> tail;
        private int size;
    
        public boolean isEmpty() {
        
            return size == 0;
        }
    
        public int size() {
        
            return size;
        }
    
        // 从队头入队
        public void pushHead(V val) {
        
            Node<V> cur = new Node<>(val);
            if (head == null) {
        
                head = cur;
                tail = cur;
            } else {
        
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size++;
        }
        // 从队头出队
        public V pollHead() {
        
            V ret = null;
            if (head == null) {
        
                return ret;
            }
            size--;
            ret = head.val;
            if (size() == 1) {
        
                head = null;
                tail = null;
            } else {
        
                head = head.next;
                head.last = null;
            }
            return ret;
        }
    
        public V peekHead() {
        
            V ret = null;
            if (head != null) {
        
                ret = head.val;
            }
            return ret;
        }
    
        // 从队尾入队
        public void pushTail(V val) {
        
            Node<V> cur = new Node<>(val);
            if (tail == null) {
        
                head = cur;
                tail = cur;
            } else {
        
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
            size++;
        }
        // 从队尾出队
        public V pollTail() {
        
            V ret = null;
            if (tail == null) {
        
                return ret;
            }
            size--;
            ret = tail.val;
            if (size() == 1) {
        
                head = null;
                tail = null;
            } else {
        
                tail = tail.last;
                tail.next = null;
            }
            return ret;
        }
    
        public V peekTail() {
        
            V ret = null;
            if (tail != null) {
        
                ret = tail.val;
            }
            return ret;
        }
    }

## 二. 集合-Queue,Deque ##

### 1. 结构介绍 ###

在Java中，Queue和Deque是两个接口，底层是通过双链表实现的 , 使用时必须创建LinkedList的对象 ;

这里观察Queue,Deque接口与LinkedList类关系 ;

LinkedList类实现了Queue,Deque接口，Deque接口扩展了Queue接口，三者都扩展或继承了Collection和Iterable接口。

![img][img 7]

### 2. 方法介绍 ###

**Queue接口提供了队列增删查改等基本操作的方法**，Deque接口提供了双端队列操作的一系列方法，LinkedList类实现了Queue,Deque接口，因此可以**使用Queue引用LinkedList对象当队列使用**，Deque引用LinkedList对象当双端队列使用，当然也**可以直接使用LinkedList引用LinkedList对象当队列，双端队列，双链表等数据结构使用**。

由于在实际开发中Deque使用的并不是非常多 , 所以这里只列出**Queue接口中常用的方法** :

<table> 
 <thead> 
  <tr> 
   <th><strong>方法</strong></th> 
   <th><strong>作用</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>队尾入队，入队失败引发异常</td> 
  </tr> 
  <tr> 
   <td>boolean offer(E e)</td> 
   <td>队尾入队，入队失败不引发异常（推荐）</td> 
  </tr> 
  <tr> 
   <td>E remove()</td> 
   <td>对头出队，并返回队头元素，出队失败引发异常</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>对头出队，并返回队头元素，出队失败不引发异常（推荐）</td> 
  </tr> 
  <tr> 
   <td>E element()</td> 
   <td>获取队头元素，获取失败引发异常</td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取队头元素，获取失败不引发异常（推荐）</td> 
  </tr> 
 </tbody> 
</table>

*  **add系列方法与offer系列方法的区别**：

两者都是在队列队头或队尾插入元素，前者（add）插入元素失败会引发异常，后者（offer）插入元素失败不会引发异常，只会以返回false的形式表示插入元素失败，如果是有容量限制的队列，使用offer系列方法更加合适。

*  **remove系列方法与poll系列方法的区别**：

两者都是在队列队头或队尾删除并返回元素，前者（remove）删除元素失败会引发异常，后者（poll）删除元素失败不会引发异常，只会以返回null的形式表示删除元素失败，如果是有容量限制的队列，使用poll系列方法更加合适。

*  **get系列方法与peek系列方法的区别**：

两者都是在队列队头或队尾获取并返回元素，前者（get）获取元素失败会引发异常，后者（peek）获取元素失败不会引发异常，只会以返回null的形式表示获取元素失败，如果是有容量限制的队列，使用peek系列方法更加合适。

**代码示例 :**

public static void main(String[] args) {
        
            Queue<Integer> q = new LinkedList<>();
            q.offer(1);
            q.offer(2);
            q.offer(3);
            q.offer(4);
            q.offer(5); // 从队尾入队列
            System.out.println(q.size());
            System.out.println(q.peek()); // 获取队头元素
            q.poll();
            System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
            if(q.isEmpty()){
        
                System.out.println("队列空");
            }else{
        
                System.out.println(q.size());
            }
        }

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[Java]: https://blog.csdn.net/trong_/category_11997769.html
[img]: https://img-blog.csdnimg.cn/img_convert/4ad78304170ed6f36fe906df758c1eac.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/9167ec2cdccc38de16be4a0c85095aac.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/3231f084a00b0a5fc2c8175ab33197c0.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/c8c7143214c1a8eff6179bcac9a7aed2.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/4fca688e7a4b290a19e7b3b1ebe6bf94.png
[img 5]: https://img-blog.csdnimg.cn/img_convert/d6fa260f53cdaa114f3b153ad5b47782.png
[img 6]: https://img-blog.csdnimg.cn/img_convert/cefa2161e0e1cbbde0434c6d6302f59c.png
[img 7]: https://img-blog.csdnimg.cn/img_convert/035088c5e952fc64d137ab6d0dbec154.png