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

后面咱们介绍了栈（Stack），队列和栈是比拟像的一种数据结构。咱们能够设想有很多辆汽车正在通过单行道的隧道，所有车辆不能插队、不能掉头，先进来的车也先进来，咱们能够把这种特色的数据结构称之为队列。


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

队列个性

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

手撸队列

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

首先咱们先应用数组来实现一个队列，它的构造如下图所示：

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.自定义队列—链表

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

实现代码如下：

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），并且在实现类中须要蕴含队列的四个外围办法：入列、出列、查问队列是否为空、返回队头元素等，就能够称为实现了一个自定义的队列。

最初，给大家留一个问题：队列的类型都有哪些？欢送评论区留言，我会在下篇文章中给出答案。欢送关注我，每天和你一起提高一点点~

文末福利：搜寻公众号「Java中文社群」发送“面试”，支付最新的面试材料。