基础数据结构——队列（双端队列，优先级队列，阻塞队列）

双端队列、队列、栈对比

	定义	特点
队列	一端删除（头）另一端添加（尾）	First In First Out
栈	一端删除和添加（顶）	Last In First Out
双端队列	两端都可以删除、添加
优先级队列		优先级高者先出队
延时队列		根据延时时间确定优先级
并发非阻塞队列	队列空或满时不阻塞
并发阻塞队列	队列空时删除阻塞、队列满时添加阻塞

注1：

• Java 中 LinkedList 即为典型双端队列实现，不过它同时实现了 Queue 接口，也提供了栈的 push pop 等方法

注2：

不同语言，操作双端队列的方法命名有所不同，参见下表

操作	Java	JavaScript	C++	leetCode 641
尾部插入	offerLast	push	push_back	insertLast
头部插入	offerFirst	unshift	push_front	insertFront
尾部移除	pollLast	pop	pop_back	deleteLast
头部移除	pollFirst	shift	pop_front	deleteFront
尾部获取	peekLast	at(-1)	back	getRear
头部获取	peekFirst	at(0)	front	getFront

• 常见的单词还有 enqueue 入队、dequeue 出队

定义接口

public interface Deque<E> extends Iterable<E>{//向队列头部添加boolean offerFirst(E e);//向队列尾部添加boolean offerLast(E e);//从队列头部获取值并移除E pollFirst();//从队列尾部获取值并移除E pollLast();//从队列头部获取值E peekFirst();//从队列尾部获取值E peekLast();//判断队列是否为空boolean isEmpty();//判断队列是否已满boolean isFull();
}

一.双端队列

1.基于双向环形链表实现双端队列

public class LinkedListDeque<E> implements Deque<E> {private Node<E> sentinel = new Node<>(null, null, null);//定义哨兵节点private int size = 0;//队列长度private int capacity;//定义容量public LinkedListDeque() {sentinel.next = sentinel;sentinel.prev = sentinel;this.capacity = Integer.MAX_VALUE;}public LinkedListDeque(int capacity) {sentinel.next = sentinel;sentinel.prev = sentinel;this.capacity = capacity;}@Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}Node<E> next = sentinel.next;Node<E> offer = new Node<>(sentinel, e, next);sentinel.next = offer;next.prev = offer;size++;return true;}@Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}Node<E> last = sentinel.prev;Node<E> offer = new Node<>(last, e, sentinel);sentinel.prev = offer;last.next = offer;size++;return true;}@Overridepublic E pollFirst() {if (isEmpty()) {return null;}Node<E> poll = sentinel.next;Node<E> next = poll.next;sentinel.next = next;next.prev = sentinel;size--;return poll.value;}@Overridepublic E pollLast() {if (isEmpty()) {return null;}Node<E> poll = sentinel.prev;Node<E> prev = poll.prev;prev.next = sentinel;sentinel.prev = prev;size--;return poll.value;}@Overridepublic E peekFirst() {if (isEmpty()) {return null;}return sentinel.next.value;}@Overridepublic E peekLast() {if (isEmpty()) {return null;}return sentinel.prev.value;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == capacity;}@Overridepublic Iterator<E> iterator() {return new Iterator<>() {Node<E> pointer = sentinel.next;@Overridepublic boolean hasNext() {return pointer != sentinel;}@Overridepublic E next() {E value = pointer.value;pointer = pointer.next;return value;}};}//节点类private static class Node<E> {private Node<E> prev;private E value;private Node<E> next;public Node(Node<E> prev, E value, Node<E> next) {this.prev = prev;this.value = value;this.next = next;}}
}

2.基于环形数组实现双端队列

public class ArrayDeque<E> implements Deque<E> {private E[] array;//数据private int head = 0;//头指针private int tail = 0;//尾指针@SuppressWarnings("unchecked")public ArrayDeque() {this.array = (E[]) new Object[Integer.MAX_VALUE];}@SuppressWarnings("all")public ArrayDeque(int capacity) {this.array = (E[]) new Object[capacity + 1];}@Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}head = dec(head, array.length);array[head] = e;return true;}@Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}array[tail] = e;tail = inc(tail, array.length);return true;}@Overridepublic E pollFirst() {if (isEmpty()) {return null;}E value = array[head];array[head] = null;//help gchead = inc(head, array.length);return value;}@Overridepublic E pollLast() {if (isEmpty()) {return null;}tail = dec(tail, array.length);E value = array[tail];array[tail] = null;return value;}@Overridepublic E peekFirst() {if (isEmpty()) {return null;}return array[head];}@Overridepublic E peekLast() {if (isEmpty()) {return null;}return array[tail];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {if (tail > head) {return tail - head == array.length - 1;} else if (tail < head) {return head - tail == 1;} else {return false;}}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int index = head;@Overridepublic boolean hasNext() {return index != tail;}@Overridepublic E next() {E value = array[index];index = inc(index, array.length);return value;}};}private static int inc(int index, int length) {if (index + 1 == length) {return 0;}return index + 1;}private static int dec(int index, int length) {if (index - 1 == -1) {return length - 1;}return index - 1;}
}

二叉树的锯齿形层序遍历-LeetCode 103

public class Leetcode103 {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {//定义返回的数据List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}//定义双端队列LinkedListDeque<TreeNode> deque = new LinkedListDeque<>();deque.offerFirst(root);int outNum = 1;boolean odd = true;while (!deque.isEmpty()) {int innerNum = 0;LinkedList<Integer> list = new LinkedList<>();//定义双端队列for (int i = 0; i < outNum; i++) {TreeNode node = deque.pollLast();if (odd) {list.offerLast(node.val);} else {list.offerFirst(node.val);}if (node.left != null) {deque.offerFirst(node.left);innerNum++;}if (node.right != null) {deque.offerFirst(node.right);innerNum++;}}outNum = innerNum;odd = !odd;result.add(list);}return result;}public static void main(String[] args) {TreeNode root = new TreeNode(1,new TreeNode(2,new TreeNode(4, null, null),new TreeNode(5, null, null)),new TreeNode(3,new TreeNode(6, null, null),new TreeNode(7, null, null)));List<List<Integer>> result = new Leetcode103().zigzagLevelOrder(root);System.out.println(result);}
}

二.优先级队列

1.基于无序数组实现优先级队列

要点

1. 入队保持顺序
2. 出队前找到优先级最高的出队，相当于一次选择排序

public class PriorityArrayQueue<E extends Priority> implements Queue<E> {private Priority[] array;;//具有优先级的数据private int size = 0;public PriorityArrayQueue() {array = new Priority[Integer.MAX_VALUE];}public PriorityArrayQueue(int capacity) {array = new Priority[capacity];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[size++] = value;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}int max = maxPriority();E value = (E) array[max];remove(max);//移除索引数据return value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[maxPriority()];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}//获取优先级最高的索引private int maxPriority() {int max = 0;for (int i = 1; i < size; i++) {if (array[i].priority() > array[max].priority()) {max = i;}}return max;}//根据索引移除元素private void remove(int index) {if (index < size - 1) {System.arraycopy(array, index + 1, array, index, size - index - 1);}array[--size] = null;}
}

2.基于有序数组实现优先级队列

要点

1. 入队后排好序，优先级最高的排列在尾部
2. 出队只需删除尾部元素即可

public class PriorityArrayQueue2<E extends Priority> implements Queue<E> {private Priority[] array;private int size;public PriorityArrayQueue2() {this.array = new Priority[Integer.MAX_VALUE];}public PriorityArrayQueue2(int capacity) {this.array = new Priority[capacity];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}insert(value);size++;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}E value = (E) array[size - 1];array[--size] = null;//help gcreturn value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[size - 1];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}private void insert(E value) {int index = size - 1;while (index >= 0 && value.priority() < array[index].priority()) {array[index + 1] = array[index];index--;}array[index + 1] = value;}
}

3.基于大顶堆实现优先级队列

计算机科学中，堆是一种基于树的数据结构，通常用完全二叉树实现。堆的特性如下

• 在大顶堆中，任意节点 C 与它的父节点 P 符合 $P.value\ge C.value$
• 而小顶堆中，任意节点 C 与它的父节点 P 符合 $P.value\le C.value$
• 最顶层的节点（没有父亲）称之为 root 根节点

例1 - 满二叉树（Full Binary Tree）
特点：每一层都是填满的

例2 - 完全二叉树（Complete Binary Tree）
特点：最后一层可能未填满，靠左对齐

例3 - 大顶堆

例4 - 小顶堆

完全二叉树可以使用数组来表示

特征

• 如果从索引 0 开始存储节点数据
  • 节点 $i$ 的父节点为 $floor((i-1)/2)$，当 $i>0$ 时
  • 节点 $i$ 的左子节点为 $2i+1$，右子节点为 $2i+2$，当然它们得 $<size$
• 如果从索引 1 开始存储节点数据
  • 节点 $i$ 的父节点为 $floor(i/2)$，当 $i>1$ 时
  • 节点 $i$ 的左子节点为 $2i$，右子节点为 $2i+1$，同样得 $<size$

大顶堆实现代码

public class MaxTopHeapQueue<E extends Priority> implements Queue<E> {private Priority[] array;private int size;public MaxTopHeapQueue() {this.array = new Priority[Integer.MAX_VALUE];}public MaxTopHeapQueue(int capacity) {this.array = new Priority[capacity];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[size] = value;int child = size;//根据子节点进行堆排序orderByChild(child);size++;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}//根节点和最后一个节点进行交换E value = (E) array[0];array[0] = array[size - 1];array[size - 1] = value;//根据根节点进行下浮orderByParent(0);size--;return value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[0];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}private void orderByChild(int child) {//1.根据子节点找到父节点，公式是： floor((i−1)/2)int parent = (child - 1) >>> 1;while (child != 0) {if (array[parent].priority() >= array[child].priority()) {break;} else {swap(child, parent);child = parent;parent = (child - 1) >>> 1;}}}private void orderByParent(int parent) {int left = 2 * parent + 1;int right = left + 1;int max = parent; // 假设父元素优先级最高if (left < size && array[left].priority() > array[max].priority()) {max = left;}if (right < size && array[right].priority() > array[max].priority()) {max = right;}if (max != parent) { // 有孩子比父亲大swap(parent, max);orderByParent(max);}}//根据两个索引进行交换private void swap(int i, int j) {Priority temp = array[i];array[i] = array[j];array[j] = temp;}
}

小顶堆实现代码

public class MinTopHeapQueue<E extends Priority> implements Queue<E> {private Priority[] array;private int size;public MinTopHeapQueue() {this.array = new Priority[Integer.MAX_VALUE];}public MinTopHeapQueue(int capacity) {this.array = new Priority[capacity];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[size] = value;//上浮新加入的节点up(size);size++;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}Priority value = array[0];//交换swap(0, --size);//下潜根节点down(0);return (E) value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[0];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}private void swap(int i, int j) {Priority temp = array[i];array[i] = array[j];array[j] = temp;}private void up(int index) {int child = index;int parant = (child - 1) % 2;while (parant > 0) {if (array[child].priority() > array[parant].priority()) {swap(child, parant);child = parant;parant = (child - 1) % 2;} else {break;}}}private void down(int index) {int left = 2 * index + 1;int right = 2 * index + 2;int min = index;if (left < size && array[min].priority() > array[left].priority()) {min = left;}if (right < size && array[min].priority() > array[right].priority()) {min = right;}if (min != index) {swap(min, index);down(min);}}
}

三.阻塞队列

使用场景

1. 很多场景要求分离生产者、消费者两个角色、它们得由不同的线程来担当，而之前的实现根本没有考虑线程安全问题
2. 队列为空，那么在之前的实现里会返回 null，如果就是硬要拿到一个元素呢？只能不断循环尝试
3. 队列为满，那么再之前的实现里会返回 false，如果就是硬要塞入一个元素呢？只能不断循环尝试

解决方法

1. 用锁保证线程安全
2. 用条件变量让 poll 或 offer 线程进入等待状态，而不是不断循环尝试，让 CPU 空转

1.单锁实现

Java 中要防止代码段交错执行，需要使用锁，有两种选择

• synchronized 代码块，属于关键字级别提供锁保护，功能少
• ReentrantLock 类，功能丰富

以 ReentrantLock 为例

public class BlockingArrayQueue1<E> implements BlockingQueue<E> {private E[] array;private int head = 0;private int tail = 0;private int size = 0; // 元素个数private ReentrantLock lock = new ReentrantLock();private Condition headWaits = lock.newCondition();private Condition tailWaits = lock.newCondition();@SuppressWarnings("all")public BlockingArrayQueue1() {this.array = (E[]) new Object[32];}@SuppressWarnings("all")public BlockingArrayQueue1(int capacity) {this.array = (E[]) new Object[capacity];}@Overridepublic void offer(E e) throws InterruptedException {lock.lockInterruptibly();//可以打断try {while (isFull()) {//进入阻塞，使用while防止虚假唤醒tailWaits.await();}array[tail] = e;if (++tail == array.length) {size = 0;}size++;headWaits.signal();//唤醒等待非空的 offer 线程} finally {lock.unlock();//释放锁}}@Overridepublic boolean offer(E e, long timeout) throws InterruptedException {lock.lockInterruptibly();//可以打断try {long nanos = TimeUnit.MILLISECONDS.toNanos(timeout);while (isFull()) {//进入阻塞，使用while防止虚假唤醒if (nanos <= 0) {return false;}nanos = tailWaits.awaitNanos(nanos);//有一个返回值，表示剩余多少纳秒}array[tail] = e;if (++tail == array.length) {size = 0;}size++;headWaits.signal();//唤醒等待非空的 offer 线程return true;} finally {lock.unlock();//释放锁}}@Overridepublic E poll() throws InterruptedException {lock.lockInterruptibly();//可以打断try {while (isEmpty()) {headWaits.await();}E e = array[head];array[head] = null; //help gcif (++head == array.length) {head = 0;}size--;tailWaits.signal();return e;} finally {lock.unlock();//释放锁}}private boolean isEmpty() {return size == 0;}private boolean isFull() {return size == array.length;}
}

2.双锁实现

单锁的缺点在于：

• 生产和消费几乎是不冲突的，唯一冲突的是生产者和消费者它们有可能同时修改 size
• 冲突的主要是生产者之间：多个 offer 线程修改 tail
• 冲突的还有消费者之间：多个 poll 线程修改 head

如果希望进一步提高性能，可以用两把锁

• 一把锁保护 tail
• 另一把锁保护 head

public class BlockingArrayQueue2<E> implements BlockingQueue<E> {private E[] array;private int head = 0;private int tail = 0;private AtomicInteger size = new AtomicInteger(); // 元素个数private ReentrantLock headLock = new ReentrantLock();private ReentrantLock tailLock = new ReentrantLock();private Condition headWaits = headLock.newCondition();private Condition tailWaits = tailLock.newCondition();@SuppressWarnings("all")public BlockingArrayQueue2() {this.array = (E[]) new Object[32];}@SuppressWarnings("all")public BlockingArrayQueue2(int capacity) {this.array = (E[]) new Object[capacity];}@Overridepublic void offer(E e) throws InterruptedException {int c;//添加前元素的个数tailLock.lockInterruptibly();//可以打断try {while (isFull()) {//进入阻塞，使用while防止虚假唤醒tailWaits.await();}array[tail] = e;if (++tail == array.length) {tail = 0;}c = size.getAndIncrement();//队列不满唤醒if (c + 1 < array.length) {tailWaits.signal();}} finally {tailLock.unlock();//释放锁}//写成嵌套会造成死锁if (c == 0) {headLock.lock();try {headWaits.signal();//唤醒等待非空的 offer 线程} finally {headLock.unlock();}}}@Overridepublic boolean offer(E e, long timeout) throws InterruptedException {int c;//添加前元素的个数tailLock.lockInterruptibly();//可以打断try {long nanos = TimeUnit.MILLISECONDS.toNanos(timeout);while (isFull()) {//进入阻塞，使用while防止虚假唤醒if (nanos <= 0) {return false;}nanos = tailWaits.awaitNanos(nanos);//有一个返回值，表示剩余多少纳秒}array[tail] = e;if (++tail == array.length) {tail = 0;}c = size.getAndIncrement();//队列不满唤醒if (c + 1 < array.length) {tailWaits.signal();}} finally {tailLock.unlock();//释放锁}//写成嵌套会造成死锁if (c == 0) {headLock.lock();try {headWaits.signal();//唤醒等待非空的 offer 线程} finally {headLock.unlock();}}return true;}@Overridepublic E poll() throws InterruptedException {int c;//减少前元素的个数E e;headLock.lockInterruptibly();//可以打断try {while (isEmpty()) {headWaits.await();}e = array[head];array[head] = null; //help gcif (++head == array.length) {head = 0;}c = size.getAndDecrement();if (c > 1) {headWaits.signal();}} finally {headLock.unlock();//释放锁}//写成嵌套会造成死锁if (c == array.length) {tailLock.lock();try {tailWaits.signal();} finally {tailLock.unlock();}}return e;}private boolean isEmpty() {return size.get() == 0;}private boolean isFull() {return size.get() == array.length;}
}