数据结构之Queue解析

队列是一种特殊的线性表，只能在头尾两端进行操作
FIFO（first in first out）：先进先出原则
在表一端（表尾）插入，在另一端（表头）删除
队尾添加元素enQueue,入队
队头移除元素deQueue,出队
优先使用双向链表，因为队列主要是往头尾操作元素
入队时间复杂度O(1),每当一个元素入队时，队尾+1
出队时间复杂度O(n),每当一个元素出队时，后面节点依次向前移动
队列的实现方式：链表、栈、动态数组

使用链表实现简单队列

Queue和Deque是两种不同的队列实现类型

Queue：只支持在队列的末尾添加元素（入队）和从队列的头部移除元素（出队）的操作。它遵循先进先出（FIFO）的原则。
Deque：不仅支持在队列的末尾添加元素和从队列的头部移除元素，还支持在队列的头部添加元素和从队列的末尾移除元素的操作。它可以将双端队列用作栈。
ps:栈是一种遵循后进先出（LIFO）原则的数据结构，只允许在栈顶进行插入和删除操作。使用双端队列作为栈的底层实现时，一般只在队列的一端执行插入和删除操作，通常选择使用双端队列的头部（或尾部）作为栈顶。这样可以保证元素的插入和删除都在同一端进行，符合栈的后进先出的行为。

使用链表创建queue

public class Queue<E> {
    private List<E> list = new LinkedList<>();
    
    public int size() {
        return list.size();
    }
    public boolean isEmpty() {
        return list.isEmpty();
    }
    public void clear() {
        list.clear();
    }
    public void enQueue(E element) {
        list.add(element);
    }
    public E deQueue() {
        return list.remove(0);
    }
    public E front() {
        return list.get(0);
    }
}

使用链表创建deque

public class Deque<E> {
    private List<E> list = new LinkedList<>();
    
    public int size() {
        //proect修饰的使用get方法
        return list.size();
    }
    public boolean isEmpty() {
        return list.isEmpty();
    }
    public void clear() {
        list.clear();
    }
    public void enQueueRear(E element) {
        list.add(element);
    }
    public E deQueueFront() {
        return list.remove(0);
    }
    public void enQueueFront(E element) {
        list.add(0, element);
    }
    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }
    public E front() {
        return list.get(0);
    }
    public E rear() {
        return list.get(list.size() - 1);
    }
}

链式队列：链式队列可以不断的存入，只有当内存不足时才会出现队列已满

假溢出

当元素被插入到数组中下标最大的位置之后，队列空间已经用尽，尽管此时数组前面还有剩余空间
这时候循环队列就出场了，后面满了，就再从头开始
循环队列可以使用数组实现，且各项接口能够优化到O(1)的时间复杂度

循环的核心就是在添加元素时利用公式 (front+size)%elements.length 得到队列尾端索引（真实索引），这个公式实质是取模时相当于将数组的长度抵消掉，抵消掉这部分长度后形成了“循环”

普通循环队列

关键部分说明：

private int front;  
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;

front：头指针在添加和删除过程中不断发生变化
size:元素数量
elements:队列所利用的当前数组
以及默认容量设置为10

int size();
boolean isEmpty();
void clear();
void ensureCapacity();

上述接口方法实现参照数组的方式实现

真实索引优化

取余复习

算 5/7 取余的步骤如下：
将 5 除以 7： 5 ÷ 7 = 0.7142857142857143
取得商的整数部分： 0
计算余数： 5 - 0 × 7 = 5

private int index( int index) {
    return ( front + index) % elements.length;
}
//优化
private int index(int index) {
    index += front;
    return index - (index >= elements.length ? elements.length : 0);
}

当添加的索引超过数组长度时返回 front+index-elements.length
当添加的索引在数组长度内时返回 index

扩容

private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity ) return;

    //新容量为旧容量的1.5倍
    int newCapacity = oldCapacity +(oldCapacity >>1);
    E[] newElements = (E[]) new object[ newCapacity];
    for ( int i = 0; i < size; i++){
        newElements[i] =elements[(i + front) % elements.length;
    }
    elements = newElements;
    //重置front
    front = 0;
}

与数组扩容逻辑一样，只是旧数组元素给到新数组时注意旧数组的元素取值时要用真实索引

队尾添加元素方法

public void enQueue(E element) {
    ensureCapacity(size + 1);
    
    elements[index(size)] = element;
    size++;
}

拿到真实索引后，添加与删除方法与数组一样对elements[index]赋值即可

队首删除元素方法

public E deQueue() {
    E frontElement = elements[front];
    elements[front] = null;
    front = index(1);
    size--;
    return frontElement;
}

数据结构之Queue解析