一文详解「队列」，手撸队列的3种方法！

Love The Way You Lie 2023-10-05 12:11 13阅读 0赞

![format_png][]

作者 | 王磊

来源 | Java中文社群（ID：javacn666）

转载请联系授权（微信ID：GG\_Stone）

> 本文已收录至我的 Github《算法图解》系列：https://github.com/vipstone/algorithm

前面我们介绍了[栈（Stack）][Stack]，队列和栈是比较像的一种数据结构。我们可以想象有很多辆汽车正在通过单行道的隧道，所有车辆不能插队、不能掉头，先进来的车也先出去，我们可以把这种特征的数据结构称之为队列。

![format_png 1][]

队列也属于逻辑结构，所谓的物理结构是指可以将数据存储在物理空间中，比如数组和链表都属于物理数据结构；而逻辑结构则是用于描述数据间的逻辑关系的，它可以由多种不同的物理结构来实现，比如队列和栈都属于逻辑结构。

#### 队列特性 ####

队列中的元素必须是先进先出（First In First Out，FIFO）的，它有两个重要的方法：入队（enqueue）和出队（dequeue）。队列的入口端叫队尾（rear），出口端叫队头（front），如下图所示：

![format_png 2][]

####    手撸队列 ####

学习了队列的基本知识之后，接下来我们将使用代码来实现一个队列。

首先我们先使用数组来实现一个队列，它的结构如下图所示：

![format_png 3][]

##### 1.自定义队列—数组 #####

public class MyQueue<E> {
    
        private Object[] queue; // 存储容器
        private int head; // 头部指针
        private int tail; // 尾部指针
        private int size; // 队列实际存储长度
        private int maxSize; // 最大容量
    
        public MyQueue() {
            // 无参构造函数，设置默认参数
            this.maxSize = 10;
            this.head = 0;
            this.tail = -1;
            this.size = 0;
            this.queue = new Object[this.maxSize];
        }
    
        public MyQueue(int initSize) {
            // 有参构造函数，设置参数
            this.maxSize = initSize;
            this.head = 0;
            this.tail = -1;
            this.size = 0;
            this.queue = new Object[this.maxSize];
        }
    
        /**
         * 查询队头元素
         */
        public E peek() throws Exception {
            if (size == 0) {
                throw new Exception("队列中暂无数据");
            }
            return (E) this.queue[this.head];
        }
    
        /**
         * 入列
         */
        public boolean offer(E e) throws Exception {
            if (tail >= (maxSize - 1)) {
                throw new Exception("添加失败，队列已满");
            }
            this.queue[++tail] = e;
            size++;
            return true;
        }
    
        /**
         * 出列
         */
        public E poll() throws Exception {
            if (size == 0) {
                throw new Exception("删除失败，队列为空");
            }
            size--;
            return (E) this.queue[head++];
        }
    
        /**
         * 代码测试
         */
        public static void main(String[] args) throws Exception {
            MyQueue queue = new MyQueue();
            queue.offer("Hello");
            queue.offer("Java");
            System.out.println(queue.peek());
            queue.poll();
            System.out.println(queue.poll());
        }
    }

以上代码的执行结果如下：

> Hello
> 
> Java

##### 2.自定义队列—链表 #####

用链表实现队列的数据结构如下图所示：

![format_png 4][]

实现代码如下：

public class QueueByLinked {
    
        /**
         * 声明链表节点
         */
        static class Node<E> {
            E item; // 当前的值
    
            Node<E> next; // 下一个节点
    
            Node(E e) {
                this.item = e;
            }
        }
    
        private Node firstNode; // 队头元素
        private Node lastNode; // 队尾元素
        private int size; // 队列实际存储数量
        private int maxSize; // 队列最大容量
    
        public QueueByLinked(int maxSize) {
            if (maxSize <= 0) throw new RuntimeException("队列最大容量不能为空");
            // 默认初始化函数
            firstNode = lastNode = new Node(null);
            this.size = 0;
            this.maxSize = maxSize;
        }
    
        /**
         * 判断队列是否为空
         */
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * 入列
         */
        public void offer(Object e) {
            // 最大值效验
            if (maxSize <= size) throw new RuntimeException("队列已满");
            Node node = new Node(e);
            lastNode = lastNode.next = node; // 设置最后一个节点和倒数第二个节点的 next
            size++; // 队列数量 +1
        }
    
        /**
         * 出列
         */
        public Node poll() {
            if (isEmpty()) throw new RuntimeException("队列为空");
            size--; // 队列数量 -1
            return firstNode = firstNode.next; // 设置并返回队头元素（第一个节点是 null，当前元素则为 Node.next）
        }
        
        /**
         * 查询队头元素
         */
        public Node peek() {
            if (isEmpty()) throw new RuntimeException("队列为空");
            return firstNode.next;  // 返回队头元素（第一个节点是 null，当前元素则为 Node.next）
        }
    
        /**
         * 代码测试
         */
        public static void main(String[] args) {
            QueueByLinked queue = new QueueByLinked(10);
            queue.offer("Hello");
            queue.offer("JDK");
            queue.offer("Java");
            System.out.println(queue.poll().item);
            System.out.println(queue.poll().item);
            System.out.println(queue.poll().item);
        }
    }

以上代码的执行结果如下：

> Hello
> 
> JDK
> 
> Java

##### 3.扩展：使用 List 实现自定义队列 #####

除了以上两种方式之外，我们还可以使用 Java 自身的数据结构来实现队列，比如 List，我们这里提供一个实现的思路（但并不建议在实际工作中使用），实现代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 自定义队列（List方式）
     */
    public class QueueByList<E> {
    
        private List value; // 队列存储容器
    
        public QueueByList() {
            // 初始化
            value = new ArrayList();
        }
    
        /**
         * 判断队列是否为空
         */
        public boolean isEmpty() {
            return value.size() == 0;
        }
    
        /**
         * 入列
         */
        public void offer(Object e) {
            value.add(e);
        }
    
        /**
         * 出列
         */
        public E poll() {
            if (isEmpty()) throw new RuntimeException("队列为空");
            E item = (E) value.get(0);
            value.remove(0);
            return item;
        }
    
        /**
         * 查询队头元素
         */
        public E peek() {
            if (isEmpty()) throw new RuntimeException("队列为空");
            return (E) value.get(0);
        }
    
        /**
         * 代码测试
         */
        public static void main(String[] args) {
            QueueByList queue = new QueueByList();
            queue.offer("Hello");
            queue.offer("JDK");
            queue.offer("Java");
            System.out.println(queue.poll());
            System.out.println(queue.poll());
            System.out.println(queue.poll());
        }
    }

以上代码的执行结果如下：

> Hello
> 
> JDK
> 
> Java

#### 队列使用场景 ####

队列的常见使用场景有：

*  存储多线程中等待排队执行的任务；
 *  存储多线程公平锁中等待执行任务的线程；
 *  常见消息中间件的任务队列等。

#### 总结 ####

通过以上三种队列的实现方式我们可以看出，任意容器都是可以用来实现队列（Queue）的，只要保证队列的元素先进先出（FIFO），并且在实现类中需要包含队列的四个核心方法：入列、出列、查询队列是否为空、返回队头元素等，就可以称为实现了一个自定义的队列。

最后，给大家留一个问题：队列的类型都有哪些？欢迎评论区留言~

![format_png 5][]

往期推荐

[![format_png 6][]][format_png 6 1]

[动图演示：手撸堆栈的两种实现方法！][format_png 6 1]

[![format_png 7][]][format_png 7 1]

[链表反转的两种实现方法，后一种击败了100%的用户！][format_png 7 1]

[![format_png 8][]][format_png 8 1]

[算法图解：如何找出栈中的最小值？][format_png 8 1]

[![format_png 9][]][format_png 9 1]

[算法图解：如何判断括号是否有效？][format_png 9 1]

关注我，每天陪你进步一点点！

![format_png 10][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzZzN2cXI2elRJckdLaFB2bGU5Y0xyZkRDSEkzcUZzN1lQWXhNVDlTUlpSeUl4Q29KRWljczBVTmN2SU5kR0E2UWp0TGV1REhJRjFreXcvNjQw?x-oss-process=image/format,png
[Stack]: https://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&idx=1&mid=2247489260&scene=21&sn=c5871b77d084d11319fffc7197be9669#wechat_redirect
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzZzN2cXI2elRJckdLaFB2bGU5Y0xyZlV3RUFRSmxIdjhrSmRTT1dHRGljSzlqbEloOUZmMDcwOWduYzVIV29XWENYajFzOGNPNkRiYncvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzZzN2cXI2elRJckdLaFB2bGU5Y0xyZnRmdGY0R1JzU2liYURVUllObll3Q2dRcFJjbjhtY3ZsSVRJMVJCVkw1eER4ZjFMeGxDeTZtcVEvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzZzN2cXI2elRJckdLaFB2bGU5Y0xyZklKY0k4OTd4M3NmcHUyZ25JOXZpYkZpYk9ab2xhYXU2cVNRaDdhRmQ2YVV4SlFHOUlhZ0UxRVdBLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzZzN2cXI2elRJckdLaFB2bGU5Y0xyZnpEd0ZBMUhpYktZR1BjdmlhVHJWbmlhTHppY1YxaG9JeFBpYmFyM0tVTm5mbnhYek9LN2Rib2wwR0lnLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9iOTZDaWJDdDcwaWFid2p5b2pMaEEwM1B0eFVua05QUkVudDJGNDh5d2ZYTHBEZERBamljT1RQSThROTR0VkxiSjU4dGJSczEyaWFYREtoVU9XOWdkNE5sRkEvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaWFrUFVCNW9UeWx4eXFzOXJzdlZvYUtvd1VYaWFoU1NIYjJSUmhpYzlnOVBlbXppY3RIaWJRcWdvOUNYMGljckw4TEQzNXFUWnExSFkzbjViUS82NDA?x-oss-process=image/format,png
[format_png 6 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7bd4ccbbf2c25efa3fcdc9ab4fe1b74279f59015cafac24661b3c71b3fdcc19187e8ef3e&idx=1&mid=2247489260&scene=21&sn=c5871b77d084d11319fffc7197be9669#wechat_redirect
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzanJRMWt6ZjZ1cTNoTE1qNG1TQk95Zmh1R3hNd091TVh0WW5iSkFXWDBDOUJqejREcXFPWkpDTjloTXFwOW96SHZ3dk1oNWxiU01YUS82NDA?x-oss-process=image/format,png
[format_png 7 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7519ccbbfc0f847ac650e02419ab813f6a5ea320cc37baac0c227f8fb241990fcbf265bd&idx=1&mid=2247489569&scene=21&sn=ead310b54ef0b51574c34426b0190d87#wechat_redirect
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaEMzWjdBWUxTdm1HSzBMVTZsRFd1QUk3UTV4WWdXeExWaWJpYURvMkFUdEs2RFc4UHhDMndoSFlrMmljNFE3Wk5BMmt3a1ZyZFlsc1lIZy82NDA?x-oss-process=image/format,png
[format_png 8 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc777bccbbfe6d1af1645942e4ded63424779a83b1a1c7d2d75506d8d1f0fa11f97e645b8d&idx=1&mid=2247490115&scene=21&sn=28cd907ca0393cd1ef664a6c21dff78c#wechat_redirect
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9HNVJRU0ZCR0U1RmliZnhydWJ5S1V0a0U0Z0h6TjdjekJyRVRkUFh2V1RxRXlZMnhsNXEwbVl3LzY0MA?x-oss-process=image/format,png
[format_png 9 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc769cccbbff8a20c17688217fc0fcb4e4803cc84c23142badcdb2a1cbf855bb5301626bd3&idx=1&mid=2247490468&scene=21&sn=08ddb106449257d7d74ef589eb23a7e0#wechat_redirect
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9zWnlBSnRpYWVzV2NqajRZNmIyUnNZampPNGNtc0E3OXZKY2RyY080RDZxb2t6V1l6NjQ4S2ZQVFNsSWhCeWVKbGZzQmtLaWFzWHR4a2JSTFRUSUxRcGlidy82NDA?x-oss-process=image/format,png