「队列 queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列的尾部，而位于队列头部的人逐个离开。

基本介绍

将队列的头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”

特点：

1. 先进先出（FIFO）：队列中的元素按照它们进入队列的顺序进行处理，最先进入队列的元素最先被处理。
2. 有限容量：队列可以有固定的容量，限制可以添加到队列中的元素数量。
3. 动态扩展：有些队列实现可以动态地扩展其容量，以适应需要添加更多元素的情况。

经典实现

基于链表的队列实现

链表是一种动态数据结构，它可以轻松地进行插入和删除操作。使用链表实现队列时，可以使用一个指针来跟踪队头和队尾节点。具体实现如下：

public class LinkedListQueue<T> {
    private Node<T> head; // 队头指针
    private Node<T> tail; // 队尾指针
    
    private static class Node<T> {
        private T data;
        private Node<T> next;
        
        public Node(T data) {
            this.data = data;
        }
    }
    
    public void enqueue(T item) {
        Node<T> newNode = new Node<>(item);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
    
    public T dequeue() {
        if (head == null) {
            throw new NoSuchElementException("Queue is empty.");
        }
        T data = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return data;
    }
    
    public boolean isEmpty() {
        return head == null;
    }
}

基于数组的队列实现

使用数组实现队列时，需要维护队头和队尾的索引，并且在入队和出队操作时，需要移动这些索引。具体实现如下：

public class ArrayQueue<T> {
    private Object[] queue;
    private int head;
    private int tail;
    private int size;
    
    public ArrayQueue(int capacity) {
        queue = new Object[capacity];
        head = 0;
        tail = 0;
        size = 0;
    }
    
    public void enqueue(T item) {
        if (size == queue.length) {
            throw new IllegalStateException("Queue is full.");
        }
        queue[tail] = item;
        tail = (tail + 1) % queue.length;
        size++;
    }
    
    public T dequeue() {
        if (size == 0) {
            throw new NoSuchElementException("Queue is empty.");
        }
        T data = (T) queue[head];
        head = (head + 1) % queue.length;
        size--;
        return data;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}

经典应用

广度优先搜索（BFS）

在图或树中进行广度优先搜索时，通常使用队列来管理待访问的节点

举例：102. 二叉树的层序遍历 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： [[3],[9,20],[15,7]]

代码实现如下：

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }

线程池任务调度

在多线程编程中，可以使用队列来管理任务队列，确保任务按照顺序执行

比如java的SynchronousQueue、ArrayBlockingQueue、LinkedBlockingQueue等

缓存