基础数据结构——队列（链表实现，数组实现）

1.概述

计算机科学中，queue 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品

接口信息如下

public interface Queue<E> {//向队列尾部添加值boolean offer(E value);//从队列头部获取值并移除E poll();//从队列头部获取值不移除E peek();//判断队列是否为空boolean isEmpty();//判断队列是否已满boolean isFull();
}

2.单向环形链表（带哨兵）实现队列

public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {private Node<E> head = new Node<>(null, null);//定义头节点哨兵private Node<E> tail = head;//定义尾节点指针private int size;//队列长度private int capacity = 8;//容量public LinkedListQueue() {this.tail.next = head;}public LinkedListQueue(int capacity) {this.tail.next = head;this.capacity = capacity;}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}Node<E> add = new Node<>(value, head);tail.next = add;tail = add;size++;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}Node<E> first = head.next;head.next = first.next;if (first == tail) {tail = head;}size--;return first.value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return capacity == size;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> pointer = head.next;@Overridepublic boolean hasNext() {return pointer != head;}@Overridepublic E next() {E value = pointer.value;pointer = pointer.next;return value;}};}/*** 定义节点类*/private static class Node<E> {private E value;private Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}}
}

3.环形数组实现队列

好处

1. 对比普通数组，起点和终点更为自由，不用考虑数据移动
2. “环”意味着不会存在【越界】问题
3. 数组性能更佳
4. 环形数组比较适合实现有界队列、RingBuffer 等

下标计算

例如，数组长度是 5，当前位置是 3 ，向前走 2 步，此时下标为 $(3+2)\%5=0$

$$(cur+step)\%length$$

• cur 当前指针位置
• step 前进步数
• length 数组长度

注意：

• 如果 step = 1，也就是一次走一步，可以在 >= length 时重置为 0 即可

判断空

判断满
满之后的策略可以根据业务需求决定

• 例如我们要实现的环形队列，满之后就拒绝入队

public class ArrayQueue<E> implements Queue<E>, Iterable<E> {private int head = 0;//起始指针private int tail = 0;//终点指针private E[] array;//数组数据@SuppressWarnings("all")public ArrayQueue(int capacity) {this.array = (E[]) new Object[capacity + 1];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail] = value;//tail++;tail = (tail + 1) % array.length;return true;}@Overridepublic E poll() {if(isEmpty()){return null;}E value = array[head];//head++;head = (head + 1) % array.length;return value;}@Overridepublic E peek() {if(isEmpty()){return null;}return array[head];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {//return tail + 1 == head;return (tail + 1) % array.length == head;}@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 = (index + 1) % array.length;return value;}};}
}

引入size变量

public class ArrayQueue2<E> implements Queue<E>, Iterable<E> {private int head = 0;//起始指针private int tail = 0;//终点指针private E[] array;//数组数据private int size = 0;//数组大小@SuppressWarnings("all")public ArrayQueue2(int capacity) {this.array = (E[]) new Object[capacity];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail] = value;tail = (tail + 1) % array.length;size++;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}E value = array[head];head = (head + 1) % array.length;size--;return value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return array[head];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return array.length == size;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int pointer = head;int count = 0;@Overridepublic boolean hasNext() {return size > count;}@Overridepublic E next() {E value = array[pointer];pointer = (pointer + 1) % array.length;count++;return value;}};}
}

优化

public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {/*求模运算：- 如果除数是 2 的 n 次方- 那么被除数的后 n 位即为余数 (模)- 求被除数的后 n 位方法： 与 2^n-1 按位与*/private int head = 0;//起始指针private int tail = 0;//终点指针private final E[] array;//数组数据@SuppressWarnings("all")public ArrayQueue3(int capacity) {/*** capacity必须是 2的 n次方* 1.抛异常* 2.改成2的n次方*      1.找到比 capacity 大的最接近的 2 的 n 次方*//*if((capacity & capacity - 1) != 0){throw new IllegalArgumentException("capacity必须是2的幂");}*//*2^4     = 162^4.?   = 302^5     = 32(int)log2(30) + 12log2(x) = log10(x) / log10(2)110      2^1100     2^21000    2^3*/capacity = 1 << (int) (Math.log10(capacity - 1) / Math.log10(2)) + 1;this.array = (E[]) new Object[capacity];}@Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail & array.length - 1] = value;tail++;return true;}@Overridepublic E poll() {if (isEmpty()) {return null;}int idx = head & array.length - 1;E value = array[idx];array[idx] = null; // help GChead++;return value;}@Overridepublic E peek() {if (isEmpty()) {return null;}return array[head & array.length - 1];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {return tail - head == array.length;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int index = head;@Overridepublic boolean hasNext() {return index != tail;}@Overridepublic E next() {E value = array[index & array.length - 1];index++;return value;}};}
}