同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如有问题,欢迎指正(评论区留言即可)

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


在这里插入图片描述

  • 队列是一种只允许在一端进行插入,另一端进行删除先进先出线性表
  • 和栈有相似之处(只许在一端插入删除,先进后出),可以进行对比的理解和记忆
  • 关于队列来说,一般有以下规定

    • 队尾(rear): 只能从队尾添加元素, 一般叫做enQueue, 入队
    • 队头(front): 只能从队头移除元素, 一般叫做deQueue, 出队
  • 同样的,可以通过动态数组或双向链表来实现队列(推荐双向链表,因为队主要是在头尾进行操作,使用没有优化过的动态数组的话时间复杂度可能会比较高)
  • 常用的队列分为以下几类

    • 普通队列
    • 双端队列
    • 循环队列
    • 循环双端队列
循环队列和循环双端队列使用并不多,但是可以学到新的思路以及动态数组的一些优化方法

队列

接口设计

  • 队列(Queue)除了基本的sizeisEmptyclear等方法,主要就是入队(enQueue)和出队(deQueue)操作了
public class Queue<E> {

    // 使用双向链表实现队列
    private List<E> list = new DoubleLinkedList<>();
  
    // 元素的数量
    public int size();
  
    // 是否为空
    public boolean isEmpty();
  
    // 入队
    public void enQueue(E element);
  
    // 出队
    public E deQueue();
  
    // 获取队列的头元素
    public E front();
  
    // 清空队列
    public void clear();
}

代码实现

实现思路和栈很相似,将(双向)链表作为队的成员变量,调用链表的方法实现队列
package top.hellocode.Queue;

import java.util.LinkedList;
import java.util.List;

/**
 * @author HelloCode
 * @site https://www.hellocode.top
 * @date 2022年05月25日 20:14
 */

public class Queue<E> {

    // 使用双向链表实现队列
    private List<E> list = new LinkedList<>();

    // 元素的数量
    public int size(){
        return list.size();
    }

    // 是否为空
    public boolean isEmpty(){
        return list.isEmpty();
    }

    // 入队
    public void enQueue(E element){
        list.add(element);      // 链表默认添加到队尾
    }

    // 出队
    public E deQueue(){
        return list.remove(0);      // 删除表头元素并返回
    }

    // 获取队列的头元素
    public E front(){
        return list.get(0);
    }

    // 清空队列
    public void clear(){
        list.clear();
    }
}

双端队列

  • 双端队列(Deque)主要操作和队列一样,就是入队和出队
  • 不过通过名字也可以看出来,双端队列是在队头队尾都能够添加和删除
  • 整体实现思路还是一样,只不过部分地方小改即可

接口设计

public class Deque<E> {
    private List<E> list = new DoubleLinkedList<>();

    // 元素的数量
    public int size();

    // 队列是否为空
    public boolean isEmpty();

    // 从队尾入队
    public void enQueueRear(E element);

    // 从队头出队
    public E deQueueFront();

    // 从队头入队
    public void enQueueFront(E element);

    // 从队尾出队
    public E deQueueRear();

    // 获取队列的头元素
    public E front();

    // 获取队列的尾元素
    public E rear();
  
    // 清空队列
    public void clear();
}

代码实现

package top.hellocode.Queue;


import top.hellocode.List.LinkedList;
import top.hellocode.List.List;

/**
 * @author HelloCode
 * @site https://www.hellocode.top
 * @date 2022年05月25日 20:20
 */
public class Deque<E> {
    private List<E> list = new LinkedList<>();

    // 元素的数量
    public int size() {
        return list.size();
    }

    // 队列是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 从队尾入队
    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);
    }
  
    // 清空队列
    public void clear(){
        list.clear();
    }
}

循环队列

在这里插入图片描述

  • 循环队列使用数组实现,是对动态数组的优化,具体优化方案可以查看【动态数组】一文中最后的优化说明部分
  • 这里加入了front指针,用来记录队列的队头位置
这里只有队头指针front,并没有队尾指针rear,是因为队尾可以通过front + size - 1计算出来,没必要浪费多余的空间来记录队尾

接口设计

public class CircleQueue<E> {
    // 记录第0个元素的索引
    private int front;
    // 当前队列存储的元素个数
    private int size;
    // 用来存储元素的数组
    private E[] elements;
    // 当前队列存储的元素数量
    public int size();
    // 当前队列是否为空
    public boolean isEmpty();
    // 入队
    public void enQueue(E element);
    // 出队
    public E deQueue();
    // 查看索引为0的元素
    public E front();
}

代码实现

  • 使用数组实现循环队列,主要操作就是入队和出队操作,这里需要扩容,和动态数组的扩容类似
  • 除了出入队操作,还需要注意循环队列中元素索引位置的计算以及front指针的控制

构造方法

public class CircleQueue<E> {
    // 记录第0个元素的索引
    private int front;
    // 当前队列存储的元素个数
    private int size;
    // 用来存储元素的容器
    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;     // 数组默认容量

    public CircleQueue(){       // 构造方法,使用默认容量为数组开辟空间
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
}
使用数组作为容器,构造方法中为数组开辟空间,默认容量为10

入队

  • 入队时,涉及到索引计算问题,因为是循环队列(环形)
  • 入队是从队尾入队,因此每次需要计算出队尾在数组中的索引
  • 和动态数组一样,为了使容量能够动态增加,在入队时,我们需要判断是否需要自动扩容,不了解的话可以参考【动态数组】一文

自动扩容

在这里插入图片描述

  • 和之前一样,我们还是开辟一个指定倍数的新数组,将元素移进新数组,改变elements的指向,释放旧数组内存
  • 和之前不同的是,我们在移动元素时,有可能不是按照原数组中的顺序,而是从front指向的元素开始
  • 例如,上图移动到新数组后0索引开始元素依次为:44,55,66,而不是66,44,55
  • 我们在移动完数组后,需要将front重置(指向0索引)
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;      // 旧容量
    if(oldCapacity >= capacity) return;     // 不需要扩容就返回

    // 计算新容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);     // 扩容为1.5倍,不理解这个算法可以查看动态数组文章
    E[] newElements = (E[]) new Object[newCapacity];        // 创建新数组
    for (int i = 0; i < size; i++) {        // 移动元素
        newElements[i] = elements[index(i)];
    }
    elements = newElements;

    // 重置front
    front = 0;
}

索引计算

  • 计算公式:(front + index) % elements.length
  • 在运算中,加减效率肯定高于乘除、取模运算,因此,除了上面的计算公式,针对本题,我们可以有下面的优化思路

    • 预期入队索引 = 第0个元素索引 + 当前队列元素个数
    • 如果预期入队索引大于等于数组长度实际入队索引 = 预期入队索引 - 数组长度
    • 如果预期入队索引小于数组长度实际入队索引 = 预期入队索引
  • 通过上面的优化思路,就把取模运算转化为了基本的加减运算,提高了执行效率
// 索引计算
private int index(int index) {
    // return (front + index) % elements.length;
    // 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
    index += front;
    return index - (index >= elements.length ? elements.length : 0);
}

入队

// 入队
public void enQueue(E element) {
    // 扩容
    ensureCapacity(size + 1);
    elements[index(size)] = element;
    size++;     // size自增
}

出队

在这里插入图片描述

  • 在循环队列中,因为有front指针,那么每次出队就是将front位置的元素置空
  • 并且将front指针后移(在末尾时又重新指向0索引处)
  • size--
// 出队
public E deQueue() {
    // 获取出队元素
    E frontElement = elements[front];
    // 将front位置元素置空
    elements[front] = null;
    // 更新front
    front = index(1);
    size--;
    return frontElement;
}

完整代码

package top.hellocode.Queue;

/**
 * @author HelloCode
 * @site https://www.hellocode.top
 * @date 2022年05月25日 20:26
 */
public class CircleQueue<E> {
    // 记录第0个元素的索引
    private int front;
    // 当前队列存储的元素个数
    private int size;
    // 用来存储元素的容器
    private E[] 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);
        elements[index(size)] = element;
        size++;     // size自增
    }

    // 自动扩容
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;      // 旧容量
        if(oldCapacity >= capacity) return;     // 不需要扩容就返回

        // 计算新容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);     // 扩容为1.5倍,不理解这个算法可以查看动态数组文章
        E[] newElements = (E[]) new Object[newCapacity];        // 创建新数组
        for (int i = 0; i < size; i++) {        // 移动元素
            newElements[i] = elements[index(i)];
        }
        elements = newElements;

        // 重置front
        front = 0;
    }

    // 索引计算
    private int index(int index) {
        // return (front + index) % elements.length;
        // 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
        index += front;
        return index - (index >= elements.length ? elements.length : 0);
    }

    // 出队
    public E deQueue() {
        // 获取出队元素
        E frontElement = elements[front];
        // 将front位置元素置空
        elements[front] = null;
        // 更新front
        front = index(1);
        size--;
        return frontElement;
    }

    // 查看索引为0的元素
    public E front() {
        return elements[front];
    }
  
    // 清空
    public void clear(){
        for (int i = 0; i < size; i++){
            elements[i] = null;
        }
        front = 0;
    }
}

循环双端队列

  • 循环双端队列就是两端都可以插入和删除的循环队列
  • 队头出队、队尾入队以及其他的基本操作都和循环队列一致
  • 需要添加的就是从队头入队、队尾出队

接口设计

public class CircleDeque<E> {
    // 存储队头(首元素)元素的下标
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public CircleDeque() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    // 元素的数量
    public int size();

    // 队列是否为空
    public boolean isEmpty();

    // 从队尾入队
    public void enQueueRear(E element);

    // 从队头出队
    public E deQueueFront();

    // 从队头入队
    public void enQueueFront(E element);

    // 从队尾出队
    public E deQueueRear();


    // 获取队列的头元素
    public E front();

    // 获取队列的尾元素
    public E rear();
}

代码实现

  • 入队时仍然可以像循环队列一样,定义一个index方法查找索引
  • 因为在队头入队,可以理解为给-1位置添加元素
  • 当index为负数时,在循环队列中的索引就应该是index + elements.length
  • 因此对比循环队列中的index方法,需要改进一下,使其支持循环双端队列的索引计算
// 索引计算
private int index(int index) {
    // return (front + index) % elements.length;
    // 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
    index += front;
    if(index < 0) return index + elements.length;
    return index - (index >= elements.length ? elements.length : 0);
}

从队头入队时,因为改变了队头位置,所以需要更新front

同理,从队尾出队时,因为没改变队头位置,所以不需要更新front

package top.hellocode.Queue;


/**
 * @author HelloCode
 * @site https://www.hellocode.top
 * @date 2022年05月25日 20:27
 */
public class CircleDeque<E> {
    // 存储队头(首元素)元素的下标
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public CircleDeque() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    // 元素的数量
    public int size(){
        return size;
    }

    // 队列是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 从队尾入队
    public void enQueueRear(E element){
        ensureCapacity(size + 1);
        elements[index(size)] = element;
        size++;
    }

    // 从队头出队
    public E deQueueFront(){
        E frontElement = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return frontElement;
    }

    // 从队头入队
    public void enQueueFront(E element){
        ensureCapacity(size + 1);
        front = index(-1);
        elements[front] = element;
        size++;
    }

    // 从队尾出队
    public E deQueueRear(){
        E rearElement = elements[size - 1];
        elements[size - 1] = null;
        size--;
        return rearElement;
    }


    // 获取队列的头元素
    public E front(){
        return elements[index(size - 1)];
    }

    // 获取队列的尾元素
    public E rear(){
        return elements[index(front)];
    }

    // 索引计算
    private int index(int index) {
        // return (front + index) % elements.length;
        // 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
        index += front;
        if(index < 0) return index + elements.length;
        return index - (index >= elements.length ? elements.length : 0);
    }

    // 自动扩容
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;      // 旧容量
        if(oldCapacity >= capacity) return;     // 不需要扩容就返回

        // 计算新容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);     // 扩容为1.5倍,不理解这个算法可以查看动态数组文章
        E[] newElements = (E[]) new Object[newCapacity];        // 创建新数组
        for (int i = 0; i < size; i++) {        // 移动元素
            newElements[i] = elements[index(i)];
        }
        elements = newElements;

        // 重置front
        front = 0;
    }
}
整体上和循环队列类似,只需要注意一下出入队操作和index索引计算方法即可
最后修改:2022 年 05 月 25 日
如果觉得我的文章对你有用,请随意赞赏