基础数据结构——队列（链表实现，数组实现）
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;
}
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
Node<E> add = new Node<>(value, head);
tail.next = add;
tail = add;
size++;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
Node<E> first = head.next;
head.next = first.next;
if (first == tail) {
tail = head;
}
size--;
return first.value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return head.next.value;
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
return capacity == size;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> pointer = head.next;
@Override
public boolean hasNext() {
return pointer != head;
}
@Override
public 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.环形数组实现队列
好处
- 对比普通数组，起点和终点更为自由，不用考虑数据移动
- “环”意味着不会存在【越界】问题
- 数组性能更佳
- 环形数组比较适合实现有界队列、RingBuffer 等
下标计算
例如，数组长度是 5，当前位置是 3 ，向前走 2 步，此时下标为
(
3
+
2
)
%
5
=
0
(3 + 2)\%5 = 0
(3+2)%5=0
( c u r + s t e p ) % l e n g t h (cur + step) \% length (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];
}
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
array[tail] = value;
//tail++;
tail = (tail + 1) % array.length;
return true;
}
@Override
public E poll() {
if(isEmpty()){
return null;
}
E value = array[head];
//head++;
head = (head + 1) % array.length;
return value;
}
@Override
public E peek() {
if(isEmpty()){
return null;
}
return array[head];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
//return tail + 1 == head;
return (tail + 1) % array.length == head;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int index = head;
@Override
public boolean hasNext() {
return index != tail;
}
@Override
public 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];
}
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
array[tail] = value;
tail = (tail + 1) % array.length;
size++;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
E value = array[head];
head = (head + 1) % array.length;
size--;
return value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return array[head];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return array.length == size;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int pointer = head;
int count = 0;
@Override
public boolean hasNext() {
return size > count;
}
@Override
public 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 = 16
2^4.? = 30
2^5 = 32
(int)log2(30) + 1
2
log2(x) = log10(x) / log10(2)
1
10 2^1
100 2^2
1000 2^3
*/
capacity = 1 << (int) (Math.log10(capacity - 1) / Math.log10(2)) + 1;
this.array = (E[]) new Object[capacity];
}
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
array[tail & array.length - 1] = value;
tail++;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
int idx = head & array.length - 1;
E value = array[idx];
array[idx] = null; // help GC
head++;
return value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return array[head & array.length - 1];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
return tail - head == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int index = head;
@Override
public boolean hasNext() {
return index != tail;
}
@Override
public E next() {
E value = array[index & array.length - 1];
index++;
return value;
}
};
}
}