本文共 10834 字，大约阅读时间需要 36 分钟。

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。本文详细介绍了队列的特性，并且使用Java语言分别实现了基于顺序结构和链式结构的队列。

1 队列的概述

  队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车，而后来的人将会排在你朋友后面。队列的工作原理与此相同。

  队列是一种先进先出（First In First Out）的线性表，简称FIFO。 允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,…,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。   因为队列属于线性表，因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现，比如JUC中的各种阻塞、非阻塞队列。在生产环境中，各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。关于Java 栈的数据结构，可以看这篇文章：。

2 队列的顺序存储结构实现

2.1 队列的顺序存储结构概述

  和栈不同的是，队列的入队和出队操作在不同端。采用数组来实现时，如果和实现栈的思想一样，如果队头在数组元素最大索引处，那么入队列就是将元素添加到最大索引后的索引处，不需要移动元素，此时时间复杂度为Ｏ(1)；但是出队列就要在数组头部了，此时将会移动全部元素，时间复杂度为O(n)。如果队头在数组元素的起始索引处，那么出队列到时变快了，但是入队列的时间复杂度却又变成O(n)了。

  因此，这里要灵活处理对头或者队尾，不再是固定在数组起始索引或者最大索引处，应该是可变的，此时需要添加外部指针用来保存“队头”和“队尾”。操作数据的时候只需要操作队头和队尾就行了，这样入队和出队的时间复杂度都是O(1)。   按照上面的做法，队头和队尾是不用固定了，入队和出队操作确实很方便。但是可能造成索引溢出以及内存浪费，如下图：   可能会出现图上的情况，队头被移动到数组的中间，而队尾由于添加元素，移动到数组尾部，此时如果再次入队，由于数组索引溢出将会抛出ArrayIndexOutOfBoundsException，但是数组的前半部分空间却还没有使用，此时又造成了空间浪费。   上面这种溢出，称为“假溢出”。假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。   循环队列解决了假溢出的问题，同时入队和出队时间都是O(1)。此时需要考虑的就只是数组的容量有限的问题了。

2.2 数组循环队列的简单实现

/** * 数组实现的循环队列,为了方便,这里底层数组设计为不可扩展 */public class MyArrayLoopQueue
   
     {       /**     * 采用数组实现链式存储     */    private final Object[] elements;    /**     * 容量     */    private final int capacity;    /**     * 队头元素索引     */    private int first;    /**     * 队尾元素索引     */    private int end;    /**     * 元素个数     */    private int size;    /**     * 构造器初始化数组     *     * @param capacity 容量     */    public MyArrayLoopQueue(int capacity) {           this.capacity = capacity;        this.elements = new Object[capacity];    }    /**     * 入队,元素添加在队尾     *     * @param element 添加的元素     * @return 添加成功返回true，添加失败返回false     */    public boolean add(E element) {           //如果队列容量已满.添加失败返回false        if (size == capacity) {               return false;        }        if (size == 0) {               /*如果是第一次放元素,则队头和队尾都指向索引0处的元素*/            elements[end] = element;        } else if (end + 1 == capacity) {               /*如果end + 1等于capacity说明队尾空间满了，转向队头,队尾队尾索引置0，循环*/            end = 0;            elements[end] = element;        } else {               /*否则,队尾索引正常自增*/            elements[++end] = element;        }        //size自增1        size++;        return true;    }    /**     * 出队,删除队头元素     *     * @return 被移除的元素, 或者null     */    public E remove() {           //队列是否已空        if (size == 0) {               // 返回null            return null;        }        Object o = elements[first];        //移除队头元素        elements[first] = null;        //如果队头索引+1之后等于capacity，重置队头索引，循环        if (++first == capacity) {               first = 0;        }        //如果出队列后队列为空,那么重置队头和队尾索引        if (--size == 0) {               first = 0;            end = 0;        }        return (E) o;    }    /**     * 返回队列元素数量     *     * @return     */    public int size() {           return size;    }    /**     * 清空队列     */    public void clear() {           for (int i = 0; i < size; i++) {               elements[i] = null;        }        size = 0;        first = 0;        end = 0;    }    /**     * 重写了toString方法     *     * @return     */    @Override    public String toString() {           StringBuilder stringBuilder = new StringBuilder();        if (size == 0) {               stringBuilder.append("[ ]");            return stringBuilder.toString();        }        stringBuilder.append("[ ");        if (first < end) {               for (int i = first; i <= end; i++) {                   stringBuilder.append(elements[i]);                if (i != end) {                       stringBuilder.append(", ");                }            }        } else if (size == 1) {               stringBuilder.append(elements[first]);        } else {               for (int i = first; i < capacity; i++) {                   stringBuilder.append(elements[i]);                stringBuilder.append(", ");            }            for (int i = 0; i <= end; i++) {                   stringBuilder.append(elements[i]);                if (i != end) {                       stringBuilder.append(", ");                }            }        }        stringBuilder.append(" ]");        return stringBuilder.toString();    }    /**     * 增强toString方法,用于测试     *     * @return     */    public String toStringPlus() {           StringBuilder stringBuilder = new StringBuilder();        if (size == 0) {               stringBuilder.append("[ ]");            stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);            return stringBuilder.toString();        }        stringBuilder.append("[ ");        if (first < end) {               for (int i = first; i <= end; i++) {                   stringBuilder.append(elements[i]);                if (i != end) {                       stringBuilder.append(", ");                }            }        } else if (size == 1) {               stringBuilder.append(elements[first]);        } else {               for (int i = first; i < capacity; i++) {                   stringBuilder.append(elements[i]);                stringBuilder.append(", ");            }            for (int i = 0; i <= end; i++) {                   stringBuilder.append(elements[i]);                if (i != end) {                       stringBuilder.append(", ");                }            }        }        stringBuilder.append(" ]");        stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);        return stringBuilder.toString();    }}
   

2.2.1 测试

MyArrayLoopQueue

3 队列的链式存储结构及实现

3.1 队列的链式存储结构概述

  队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

  可以看出来，使用链式结构实现队列相比顺序结构的实现更加简单。

3.2 队列的链式存储结构简单实现

/** * 队列的链式储存结构的简单单链表实现 */public class MySingleLinkedQueue
   
     {       /**     * 空构造器,内部的节点均没有初始化,在第一次添加时才会初始化。     */    public MySingleLinkedQueue() {       }    /**     * 元素个数     */    private int size;    /**     * 指向队头结点的引用     */    private Node
    
      first;    /**     * 指向队尾结点的引用     */    private Node
     
       end;    /**     * 单链表内部的节点     */    private static class Node
      
        {           //下一个结点的引用        Node
       
         next;        //结点数据        E data;        //节点构造器        public Node(E data, Node
        
          next) { this.data = data; this.next = next; } } /** * 入队，添加元素到单链表尾部 * * @param e 要添加的元素 */ public void add(E e) { //创建新节点 Node
         
           newNode = new Node<>(e, null); if (end != null) { /*如果尾结点不为空*/ end.next = newNode; //改变队尾节点引用 end = newNode; } else { end = newNode; first = newNode; } ++size; } /** * 出队，删除单链表头部元素 * * @return 被删除的元素 */ public E remove() { //如果头结点为空,抛出异常 if (first == null) { throw new NoSuchElementException("队列已经为空"); } E e = first.data; //改变队头节点引用 first = first.next; //如果元素为0,则将队尾节点引用置空 if (--size == 0) { end = null; } return e; } /** * 获取元素数量 */ public int size() { return size; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); if (size > 0) { Node
          
            f = first; stringBuilder.append("[ "); for (int i = 0; i < size; i++) { stringBuilder.append(f.data); if (i != size - 1) { stringBuilder.append(" , "); } f = f.next; } stringBuilder.append(" ]"); return stringBuilder.toString(); } return "[]"; }}
          
         
        
       
      
     
    
   

3.2.1 测试

MySingleLinkedQueue

4 总结

  本文介绍了队列的基本概念，并且提供了简单的实现，队列属于一种特殊的线性表。“先来的数据先处理”是一种很常见的思路，所以队列的应用范围非常广泛，实际上我们能够直接接触到的队列的应用是要高于栈的应用的，比如各种并发队列，消息队列。另外在广度优先搜索算法中，通常就会从搜索候补中选择最早的数据作为下一个顶点。此时，在候补顶点的管理上就可以使用队列。

  另外，关于Java 栈的数据结构，可以看这篇文章：。

参考

《大话数据结构》 《算法图解》 《我的第一本算法书》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！