数据结构--队列Queue的实现原理

「爱情、让人受尽委屈。」 2023-07-14 05:27 52阅读 0赞

**目录**

一、what is 队列？

1.1  现实中的队列

1.2  代码中的队列

1.3  队列分类

1.4  队列适用范围

二、队列使用

二、队列的实现

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

# 一、what is 队列？ #

## 1.1  现实中的队列 ##

队列队列就是要排队啊，排队就是要等待啊，现实中有哪些需要等待的？

你们有没有这样的经历，在用电脑的时候，鼠标点什么似乎都没用，双击任何快捷方式都不动弹，处于疑似死机的状态。但等一会后，电脑又似乎醒过来了，又把你刚才点击的所有操作全部按顺序执行一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。

还有你在超市的某个收银通道排队付款时，也是一样按照排队顺序来进行。

还有你给某个客服打电话时，经常遇到“人工坐席忙，请稍后再拨”的提示，那也是因为客户太多而客服少，只有等上一个完事才能处理你的业务

.....

还有好多队列的例子，那我们可以概括一下这些例子的一些特点：

*  你在排队的时候，永远是在队尾加入（插队估计要被打）
 *  队首的人付完钱会离开
 *  排在你前面的人先离开

## 1.2  代码中的队列 ##

代码中的队列和现实中的队列思想上实际是一致的：

*  **队列是一种先进先出（First in First Out）的线性表，简称FIFO**
 *  **允许插入的一端称为队尾，允许删除的一端称为队头**
 *  **顺序插入，不允许插队**

![20200313144348110.png][]

## 1.3  队列分类 ##

按照存储方式（既然是线性表，按照存储方式那就有两种存储方式）：

1.  基于数组的顺序存储方式
2.  基于链表的链式存储方式

按照实现方式也分为：

1.  单向队列（Queue）：只能在一端插入数据，另一端删除数据
2.  双向队列（Deque）：每一端都可以进行插入数据和删除数据操作

## 1.4  队列适用范围 ##

如果是一些及时消息的处理，并且处理时间很短的情况下是不需要使用队列的。

如果在消息处理的时候特别费时间，这个时候如果有新的消息来了，就只能处于阻塞状态，造成用户等待。这个时候在项目中引入队列是十分有必要的。当我们接受到消息后，先把消息放到队列中，然后再用新的线程进行处理，这个时候就不会有消息的阻塞了。

# 二、队列使用 #

Queue接口与List、Set同一级别，都是继承了Collection接口。

Queue的实现有PriorityQueue、ArrayDeque、LinkedList。其中ArrayDeque、LinkedList是实现的其子接口Deque。

Queue中包含的方法如下：

![20200313150833977.png][]

*  add(E e)将指定元素加入到队列尾部，会抛出IllegalStateException异常
 *  offer(E e) 将指定元素加入到队列尾部，会返回 false
 *  remove() 返回队列头部元素并删除，如果队列为空,会抛NoSuchElementException
 *  poll() 返回队列头部元素并删除，如果队列为空,返回null
 *  element() 返回队列头部元素不删除，如果队列为空,会抛NoSuchElementException
 *  peek() 返回队列头部元素不删除，如果队列为空,返回null

ArrayDeque和 LinkedList都是Queue的实现类，实际Queue的add（）方法就是调用的ArrayDeque或 LinkedList的add（）方法，Queue 接口中的方法在两者中都有具体实现，尽管实现方式不同，但是因为共同接口Queue的原因，使用方法是一样的，这就是面向接口的好处（不管你咋实现，我对外提供的API是统一的）。

基于ArrayDeque：（构造时ArrayDeque可以传入大小，不传默认数组大小为16）

public class Demo {
        public static void main(String[] args) {
            Queue queue = new ArrayDeque();
            queue.offer("1");
            queue.offer("2");
            queue.offer("3");
            queue.add("4");
            queue.add("5");
            queue.add("6");
            queue.stream().forEach(item ->{
                System.out.println(item);
            });
            // 返回队首的元素
            Object firstElement = queue.element();
            System.out.println("队首的元素：" + firstElement);
            // 移除并返回队列头部的元素
            System.out.println("移除并返回队列头部的元素:" + queue.remove());
            System.out.println("移除后：");
            queue.stream().forEach(item ->{
                System.out.println(item);
            });
        }
    }

基于LinkedList：

public class Demo {
        public static void main(String[] args) {
            Queue queue = new LinkedList();
            queue.offer("1");
            queue.offer("2");
            queue.offer("3");
            queue.add("4");
            queue.add("5");
            queue.add("6");
            queue.stream().forEach(item ->{
                System.out.println(item);
            });
            // 返回队首的元素
            Object firstElement = queue.element();
            System.out.println("队首的元素：" + firstElement);
            // 移除并返回队列头部的元素
            System.out.println("移除并返回队列头部的元素:" + queue.remove());
            System.out.println("移除后：");
            queue.stream().forEach(item ->{
                System.out.println(item);
            });
        }
    }

两种结果一样：

1
    2
    3
    4
    5
    6
    队首的元素：1
    移除并返回队列头部的元素:1
    移除后：
    2
    3
    4
    5
    6

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

# 二、队列的实现 #

前面说过队列按照存储结构可以分为顺序队列和链式队列。顺序队列采用数组实现，链式队列采用链表的方式实现。

**顺序队列实现：**

/**
     * Feng, Ge 2020/3/13 0013 16:18
     */
    public class MyArrayQueue {
        private Object[] data;
        // 最大容量
        private int maxSize = 0;
        // 队首位置
        private int head = 0;
        // 队尾位置
        private int tail = 0;
    
        /**
         * 构造方法，初始化队列大小
         */
        public MyArrayQueue(int size) {
            data = new Object[size];
            maxSize = size;
        }
    
        public MyArrayQueue() {
            this(6);
        }
    
        /**
         * 判断队列是否为空
         */
        public boolean isEmpty() {
            return tail == head ? true : false;
        }
    
        /**
         * 判断队列是否已满
         */
        public boolean isMax() {
            return tail >= maxSize ? true : false;
        }
    
        /**
         * 加入队列
         */
        public boolean offer(Object obj) {
            if (isMax()) {
                System.out.println("队列已存满");
                return false;
            }
            // 队尾加入元素
            data[tail] = obj;
            tail++;
            return true;
        }
    
        /**
         * 删除队首元素，并返回队首元素
         */
        public Object poll() {
            if (isEmpty()) {
                System.out.println("队列为空");
            }
            Object fisrtElement = data[head];
            // 从 head+1 位置开始到tail位置的数据向前移动一位
            System.arraycopy(data, head+1, data, head, tail-1);
            tail--;
            return fisrtElement;
        }
    
    
        public static void main(String[] args) {
            MyArrayQueue myArrayQueue = new MyArrayQueue();
            myArrayQueue.offer(0);
            myArrayQueue.offer(1);
            myArrayQueue.offer(2);
            myArrayQueue.offer(3);
            myArrayQueue.offer(4);
            myArrayQueue.offer(5);
            System.out.println("添加顺序：");
            for (int i = 0; i < myArrayQueue.data.length; i++) {
                System.out.println(myArrayQueue.data[i]);
            }
            System.out.println("队首元素：" + myArrayQueue.poll());
            myArrayQueue.offer(6);
            System.out.println("删除后再添加的顺序：");
            for (int i = 0; i < myArrayQueue.data.length; i++) {
                System.out.println(myArrayQueue.data[i]);
            }
        }
    }

添加顺序：
    0
    1
    2
    3
    4
    5
    队首元素：0
    删除后再添加的顺序：
    1
    2
    3
    4
    5
    6

**链式队列实现：**

这个实现和之前写过的一篇 《JAVA集合类（详解）》里的LinkedList几乎一样，可以跳过去看看，地址：[https://blog.csdn.net/weixin\_41231928/article/details/103413167][https_blog.csdn.net_weixin_41231928_article_details_103413167]

# 三、JDK中的队列 #

Queue 有 (PriorityQueue/Deque/ArrayDeque/LinkedList) 这几种子接口或实现类。

## 3.1 PriorityQueue ##

PriorityQueue是Queue队列实现类，PriorityQueue是优先队列，保存队列元素的顺序不是按照加入队列的顺序，而是按照队列元素的大小进行重新排序。当调用 `peek()`或 `poll()`方法获取队列元素时，获取的是最小元素，而不是先入队列的元素。这一点是不符合队列先进先出的特征的。

public static void main(String[] args) {
            PriorityQueue priorityQueue = new PriorityQueue();
            priorityQueue.offer(5);
            priorityQueue.offer(-1);
            priorityQueue.offer(3);
            priorityQueue.offer(7);
    
            // 查看入队顺序
            System.out.println("队列输出：" + priorityQueue);
            // peek方法获取队头元素但是不删除元素
            System.out.println("peek()方法获取队头：" + priorityQueue.peek());
            // 查看第一个元素即为最小元素
            System.out.println("第一个队列元素出队：" + priorityQueue.poll());
            System.out.println("第二个队列元素出队：" + priorityQueue.poll());
            System.out.println("第三个队列元素出队：" + priorityQueue.poll());
            System.out.println("第四个队列元素出队：" + priorityQueue.poll());
            System.out.println("null队列：" + priorityQueue.poll());
        }

队列输出：[-1, 5, 3, 7]
    peek()方法获取队头：-1
    第一个队列元素出队：-1
    第二个队列元素出队：3
    第三个队列元素出队：5
    第四个队列元素出队：7
    null队列：null

## 3.2 Deque ##

Deque是Queue子接口，也叫双端队列。

可以同时从两端（队列头部和尾部）添加、删除元素，所以可以用来实现栈的数据结构。

有两个实现类（ `ArrayDeque `和 `LinkedList`）

**常用方法：**

*  `void addFirst(E e)`：将指定元素插入该双端队列的头部，比较重要，下面很多方法头部插入内部实现都是通过这个来实现的，如offerFirst()。
 *  `void addLast(E e)`：将指定元素插入该双端队列的尾部。比较重要，下面添加到尾部插入内部实现都是通过这个来实现的，如offerLast()。
 *  `E getFirst()`：获取但不删除双端队列的第一个元素。
 *  `E getLast()`：获取但不删除双端队列的最后一个元素。
 *  `E removeFirst()`：获取并删除该双端队列的第一个元素。栈的出队列方法pop()也是通过该方法实现的。
 *  `E removeLast()`：获取并删除该双端队列的最后一个元素。
 *  `Iterator<E> descendingIterator()`：返回双端队列的迭代器，逆向顺序迭代元素。
 *  `boolean offerFirst(E e)`：将指定元素插入该双端队列的头部。

## 3.3 ArrayDeque ##

ArrayDeque底层实现类似于ArrayList，都是通过动态、可分配的Object\[\]数组来实现元素存储，当集合元素超过数组容量，会重新分配一个新的数组来存储集合元素。前面都已经说过原理了。

public static void main(String[] args) {
            //可以作为栈来使用，先进后出
            ArrayDeque<String> arrayDeque = new ArrayDeque<>();
            arrayDeque.push("book01");
            arrayDeque.push("book03");
            arrayDeque.push("book02");
            arrayDeque.push("book04");
    
            System.out.println("原栈：" + arrayDeque);
    
            System.out.println("获取头部元素，但不删除该元素，peek(): " + arrayDeque.peek());
            System.out.println("获取头部元素，且删除该元素，pop(): " +arrayDeque.pop());
            System.out.println("获取第一个元素，但不删除：" + arrayDeque.getFirst());
            System.out.println("获取最后一个元素，但不删除：" + arrayDeque.getLast());
    
            System.out.println("在双端队列头部插入元素：" + arrayDeque.offerFirst("booknew01"));
            System.out.println("在双端队列尾部插入元素：" + arrayDeque.offerLast("booknew02"));
            System.out.println("新栈：" + arrayDeque);
        }

原栈：[book04, book02, book03, book01]
    获取头部元素，但不删除该元素，peek(): book04
    获取头部元素，且删除该元素，pop(): book04
    获取第一个元素，但不删除：book02
    获取最后一个元素，但不删除：book01
    在双端队列头部插入元素：true
    在双端队列尾部插入元素：true
    新栈：[booknew01, book02, book03, book01, booknew02]

# 3.4 LinkedList #

LinkedList实现List，同时也实现了Deque，可以当做双端队列来使用，可以当做“栈”或“队列”使用。

LinkedList与ArrayList、ArrayDeque不同之处在于底层实现，LinkedList底层是通过链表的形式存储元素，**`随机访问性能比较差`**，但是在 **`插入`、`删除 `**的时候 **`性能比较好`**（只需要改变指针所指的地址就行）

# 补充一：peek()和element()的异同 #

*  同：peek()和element()都是在不移除的情况下返回队头；
 *  异：peek()方法在队列为空时返回null，而element()会抛出NoSuchElementException异常。

# 补充二：poll()和remove()的异同 #

*  同：poll()和remove()都是将移除并返回队头；
 *  异：poll()在队列为空时返回null，而remove()会抛出NoSuchElementException异常。

# 补充三：队列和栈区别？ #

**队列：**

1.  队列是按照`先进先出FIFO`原则进行操作元素的。
2.  队列是限定所有的插入只能在表的一端进行，而删除在表的另一端进行的线性表。
3.  表中允许插入的一端为队尾，允许删除的一端为队头。

**栈** ：

1.  栈是一种特殊的线性表，是一种`后进先出LIFO`的结构；
2.  栈是先定仅在表尾插入和删除运算的线性表，表尾即为`栈顶`，表头称为栈底。
3.  栈的物理存储可以用顺序存储结构，也可以用链式存储结构。

[20200313144348110.png]: /images/20230529/126c9884613e42718c2150ab4f363605.png
[20200313150833977.png]: /images/20230529/111303514e5b45c8a4cd36c0e5609457.png
[https_blog.csdn.net_weixin_41231928_article_details_103413167]: https://blog.csdn.net/weixin_41231928/article/details/103413167