日拱一卒：队列（Queue）

1. 队列（Queue）

• 队列是一种特殊的线性表，队头(front) 进行删除，队尾(rear) 进行插入
• 特性：先进先出
• LinkedList 实现了 Queue，一般使用的是 LinkedList

1.1 常用方法

• 会抛异常的方法：add(), remove(), element()
• 不抛异常的方法：offer(), poll(), peek()

while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

public class QueueDemo<E> {
    // 使用双向链表
    private List<E> linkedList = new LinkedList<>();
    public boolean offer(E element) {
        return linkedList.add(element);
    }
    public E poll() {
        // 队头出队，index=0
        return linkedList.remove(0);
    }
    public int size() {
        return linkedList.size();
    }
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }
}

2. 用栈实现队列

public class QueueByStack<E> {
    private Stack<E> inStack = new Stack<>();
    private Stack<E> outStack = new Stack<>();

    public boolean isEmpty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    public E offer(E element) {
        return inStack.push(element);
    }

    public E poll() {
        checkOutStack();
        return outStack.pop();
    }

    public E peek() {
        checkOutStack();
        return outStack.peek();
    }

    public void checkOutStack() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }

}

3. 阻塞队列（BlockedQueue）

3.1 等待 - 通知机制

• synchronized 配合 wait()、notify()、notifyAll() 实现等待 - 通知机制
• notify() 会随机地通知等待队列中的一个线程，而 notifyAll() 会通知等待队列中的所有线程
• 用 notifyAll() 来实现通知机制，使用 notify() 也很有风险，它的风险在于可能导致某些线程永远不会被通知到
• 可用等待 - 通知机制来优化轮询

参考：极客时间 - Java 并发编程实战 - 06 用“等待-通知”机制优化循环等待

3.2 Lock + Condition 实现阻塞队列

3.3 LinkedBlockingQueue

• 基于链表的阻塞队列
• 应用：生产者消费者模型