数据结构与算法（第一季）：队列

一、队列

• 队列是一种特殊的线性表, 只能在头尾两端操作
• 队尾(rear): 只能从队尾添加元素, 一般叫做enQueue, 入队
• 对头(front): 只能从对头移除元素, 一般叫做deQueue, 出队

image

<figcaption></figcaption>

二、接口设计

int size();
boolean isEmpty();
void clear();
void enQueue(E element);
E deQueue();
E fornt();
复制代码

• 队列的内部实现可以用动态数组或链表实现, 链表优先使用双向链表

三、队列实现

public class Queue<E> {
    private LinkedList<E> list;

    public Queue() {
        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 fornt() {
        return list.get(0);
    }
}
复制代码

四、双端队列

• 双端队列是能在头尾两端添加、删除的队列

1、接口设计

// 元素的数量
int size();
// 是否为空
boolean isEmpty();
// 清空
void clear();
// 从队尾入队
void enQueueRear(E element);
// 从对头出队
E deQueueFront();
// 从对头入队
void enQueueFront(E element);
// 从队尾出队
E deQueueRear();
// 获取队列的头元素
E fornt();
// 获取队列的尾元素
E rear();
复制代码

2、双端队列实现

public class Deque<E> {
    private LinkedList<E> list;

    public Deque() {
        list = new LinkedList<>();
    }

    // 元素的数量
    int size() {
        return list.size();
    }
    // 是否为空
    boolean isEmpty() {
        return list.isEmpty();
    }
    // 清空
    void clear() {
        list.clear();
    }
    // 从队尾入队
    void enQueueRear(E element) {
        list.add(element);
    }
    // 从对头出队
    E deQueueFront() {
        return list.remove(0);
    }
    // 从对头入队
    void enQueueFront(E element) {
        list.add(0, element);
    }
    // 从队尾出队
    E deQueueRear() {
        return list.remove(list.size() - 1);
    }
    // 获取队列的头元素
    E fornt() {
        return list.get(0);
    }
    // 获取队列的尾元素
    E rear() {
        return list.get(list.size() - 1);
    }
}
复制代码

五、循环队列

• 队列内部实现也可以用动态数组实现, 并且将各项接口优化到O(1)的时间复杂度, 这个用数组实现并优化之后的队列就叫做: 循环队列
• 使用一个索引变量front控制第0个元素所在位置, 每一次出栈, 就将front位置的元素取出并删除, 然后front向后+1
• 每一次入栈, 都根据front和当前元素数量计算出入栈元素应该存入的索引, 然后将元素存入到数组对应索引的位置上

1、接口设计

int size();
boolean isEmpty();
void clear();
void enQueue(E element);
E deQueue();
E fornt();
复制代码

2、代码实现

public class CircleQueue<E> {
    // 记录第0个元素的索引
    private int front;
    // 当前队列存储的元素个数
    private int size;
    // 用来存储元素的数组
    private E[] elements;
    // elements默认容量
    private static final int DEFAULT_CAPACITY = 10;
    // 初始化
    public CircleQueue() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    // 当前队列存储的元素数量
    public int size() {
        return size;
    }
    // 当前队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    // 入队
    public void enQueue(E element) {
        // 扩容
        ensureCapacity(size + 1);
        // 计算新元素应该添加的位置: (front + size) % elements.length
        elements[(front + size) % elements.length] = element;
        // 数量+1
        size++;
    }
    // 扩充容量
    private void ensureCapacity(int capacity) {
        if (capacity <= elements.length) return;
        capacity = capacity + (capacity >> 1);
        E[] newElements = (E[]) new Object[capacity];

        for (int i = 0; i < size; i++) {
            // 计算元素在旧数组的位置 (i + front) % elements.length
            // 取出元素添加到新数组
            newElements[i] = elements[(i + front) % elements.length];
        }
        elements = newElements;
        front = 0;
    }
    // 出队
    public E deQueue() {
        // 取出元素
        E element = elements[front];
        // 删除元素
        elements[front] = null;
        // front向后移动一位
        front = (front + 1) % elements.length;
        // 数量-1
        size--;
        return element;
    }
    // 查看第0个元素
    public E fornt() {
        // 取出front位置的元素
        return elements[front];
    }
    // 清空队列
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
        front = 0;
    }
}
复制代码