[数据结构与算法]数据结构与算法 --- 第二章(3) 队列(顺序结构)

队列(顺序结构)

1. 队列的定义

??大家好，还是先感谢大家能来看我的文章。今天，我们又要学习一种新的数据结构 - 队列。队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。它是一种先进先出的线性表，简称 FIFO 。我们把允许删除的一端称为队首 front ，插入的一端成为队尾 rear ，不含任何元素的队列称为空队列。队列本身也是一个线性表，其数据元素具有线性关系，只不过是一种特殊的线性表而已。队列插入元素的操作叫入队，删除元素的操作叫出队。

??队列，在生活中的许多场景下我们都能见到队列。受疫情影响我们要经常进行核酸检测，我们去核酸检测的时候就需要排队，刚来的人就要排在队伍最后边，而队首检测完一个则走一个人，这其实就是一个典型的队列。

2. Queue 接口的定义

??由于队列本身就是一个特殊的线性表，那么看过我之前文章的朋友都知道，我们讨论了线性表的顺序存储和链式存储，对于队列来说也是同样适用的。队列也可以通过顺序存储或链式存储结构来实现，所以我们依然可以对两种不同的实现方式抽取其中相同的操作，将这些方法定义在 Queue 接口中，至于方法如何实现，我们交给各自的实体类即可。因此我们需要定义 Queue 接口，接下来我们具体分析一下该接口需要实现哪些功能？
Queue 接口的实现：
??首先我们来声明 Queue 接口，由于我们并不知道存入队列中的元素是什么类型的，所以我们让该接口支持泛型。然后要使队列支持迭代功能，所以我们让 Queue 继承 Iterable 接口。

public interface Queue<E> extends Iterable<E> {
	......
}

??那么接下来我们分析 Queue 接口都需要哪些功能，首先我们要有入队的方法，用来向队尾添加一个元素；然后需要有出队的方法，用来从队首删除一个元素。

public void offer(E element);   //入队
public E poll();                //出队

??接下来还需要有能查看队首元素、判断当前队列是否为空、清空当前队列中的元素、获取当前队列有效元素个数等这些方法。

public E element();        //查看队首元素
public boolean isEmpty();  //判空
public void clear();       //清空
public int size();         //有效元素个数

??至此，一个完整的 Queue 接口定义完成，我们来看一下完整的 Queue 接口。

public interface Queue<E> extends Iterable<E> {
    public void offer(E element);   //入队
    public E poll();    //出队
    public E element();    //查看队首元素
    public boolean isEmpty();
    public void clear();
    public int size();
}

3. 队列的顺序存储结构

??既然上文说到，队列是一种特殊的线性表，那么队列的顺序存储结构也就是线性表的顺序存储结构的特殊情况，我们可以将其称为顺序队列。既然栈是一种特殊的线性表，那我们完全可以使用线性表来实现一个队列，如下：

3.1 ArrayQueue 的实现

??因为队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。那我们完全可以将 ArrayList 再封装成 ArrayQueue，既然要实现队列这个结构，我们应该让 ArrayQueue 实现 Queue 接口，接下来我们看一下 ArrayQueue 类的定义。

public class ArrayQueue<E> implements Queue<E> {
	......
}

3.1.1 ArrayQueue 的属性

??既然我们是将 ArrayList 再封装成 ArrayQueue，那我们属性定义一个线性表即可。如下：

private ArrayList<E> list;

3.1.2 ArrayQueue 的构造器

??这里我们创建一个默认容量的 ArrayList 即可，当然也可以有其他构造器，按情况定义即可。

public ArrayQueue() {
    list = new ArrayList<>();
}

3.1.3 入队的方法 offer()

??该方法是向队列中插入一个元素，因为队列是在队尾进行插入操作，因此我们直接在构造的 list 的表尾添加一个元素即可。

public void offer(E element) {
    list.add(list.size(), element);
}

3.1.4 出队的方法 poll()

??该方法是从队列中删除一个元素，因为队列是在队首进行删除操作，因此我们直接在构造的 list 的表头删除一个元素即可。

public E poll() {
    return list.remove(0);
}

3.1.5 查看队首元素的方法 element()

??该方法是用来查看当前队首元素，实际上就是查看 list 的表头元素，所以我们直接获取 list 的表头元素即可。

public E element() {
    return list.get(0);
}

3.1.6 判空 isEmpty()

??该方法是用来看当前队列是否为空，那么直接查看 list 是否为空即可。

public boolean isEmpty() {
    return list.isEmpty();
}

3.1.7 清空队列中元素 clear()

??该方法用来清空当前队列，那么直接清空 list 即可。

public void clear() {
    list.clear();
}

3.1.8 获取有效元素个数 size()

??该方法是用来获取当前队列中的有效元素个数，那么直接获取 list 中的有效元素个数即可。

public int size() {
    return list.size();
}

3.1.9 ArrayQueue 的 equals()

??该方法是用来比较 ArrayQueue 对象的内容是否相同，首先我们判断传入对象 o 是否为空，然后再判断传入对象是否为自己，再判断 o 是否为 ArrayStack 类型的对象，如果是，我们直接调用彼此底层的 list 的 equals() 方法进行比较。这些条件都不满足的话，直接返回 false。

public boolean equals(Object o) {
    if (o == null) {
        return false;
    }
    if (this == o) {
        return true;
    }
    if (o instanceof ArrayQueue) {
        ArrayQueue other = (ArrayQueue) o;
        return list.equals(other.list);
    }
    return false;
}

3.1.10 ArrayQueue 的 toString()

??该方法是用来输出当前 ArrayQueue 对象存储的信息，我们直接使用 list 的 toString() 即可。

public String toString() {
    return list.toString();
}

3.1.11 获取迭代器 iterator()

??该方法用来获取 ArrayQueue 的迭代器，可以让该类型支持 foreach 循环，可以迭代遍历队列中存储的元素，我们直接使用 list 的迭代器即可。

public Iterator<E> iterator() {
    return list.iterator();
}

3.2 队列顺序存储的不足

3.2.1 优化一

??我们上面使用顺序存储结构实现了队列，但是这种定义方式有很大的优化空间。我们假设一个队列中有 n 个元素，以我们上面的定义，则需要建立一个大于 n 的数组，并把队列所有的元素存在数组的前 n 个单元，数组下标为 0 的一端是队首，另一端则是队尾。如果是入队操作，那么就是在队尾追加一个元素，不需要移动元素，因此时间复杂度为 O(1) 。但是出队操作呢？出队操作是从数组下标为 0 的位置删除一个元素，然后让剩余的元素依次往前移动一位，保证下标为 0 的位置也就是队首不为空，这样的话我们出队操作的时间复杂度为 O(n) 。
??那么问题来了，我们能否让出队操作的时间复杂度也为 O(1) 呢？如果可以的话，出队操作的性能就会提升很多。我们可以让队首指针和队尾指针一样随着数据元素的变化而移动。如下：

??但是这样又会面临新的问题，当队尾指针 rear 到数组的最后一个位置后不能继续往后，并且队首指针前面的空间产生了浪费，那么如何处理呢，请看优化二 。

3.2.2 优化二

??既然我们优化一中出现了空间浪费，那我们可以在队尾或队首指针到达尾部时，如需后移，可重新指向表头。其实大家将它想象成一个圈就很好理解，尾巴和头相连。如下：

相当于：

??如上所示，这样就解决了空间浪费的问题，但是我们如何判断队列是否已经满了，又如何判断队列是否为空呢？我们来演示一下。
??首先，我们来看队列已满的情况，当 (Rear + 1) % n 的值等于 Front 的值时，也就是队尾指针的下一个位置是队首指针时，队列已满。注：由于队列已经有了循环的效果，因此我们在计算指针位置的时候要根据情况对数组的长度进行取余操作。如图：

??然后，我们来看队列为空的情况，当 (Rear + 1) % n 的值等于 Front 的值时，也就是队尾指针的下一个位置是队首指针时，队列为空。如图：

??可见，判断队列为空或者已满的条件是一样的，这样会使我们的代码产生二义性，因此我们还需要继续进行优化，我们接着来看优化三 。

3.2.3 优化三

??由于优化二中，判断队列为空或者已满的条件相同，使我们的判断条件产生了二义性，那我们该怎么进行优化呢？既然如此，我们将一个空间预留出来不存任何元素，尾指针始终指向这个 null 空间。注：该 null 是理论上为空，因为即便里面存了某个元素，但它并不在我们的有效元素范围内，因此不需要担心。如下：

??那我们再来讨论队列已满和队列为空时的条件。首先，当 (Rear + 1) % n 的值等于 Front 的值时，也就是队尾指针的下一个位置是队首指针时，队列已满。如下：

??然后，我们再来看队列为空时的条件，当 Rear 的值等于 Front 的值时，也就是队首指针和队尾指针在同一位置的时候，队列为空。如下：

??至此，我们对 ArrayQueue 的优化结束。简单总结一下，我们解决了出队操作时间复杂度高的问题；解决了空间浪费的问题；解决了判空判满条件冲突的问题。那么接下来，就让我们去实现这个循环队列吧！

3.3 ArrayLoopQueue 的实现（循环队列）

3.3.1 循环队列的定义

??循环队列是指头尾相接的顺序存储结构实现的队列。具体执行过程可以结合上下文了解。

??循环队列也是线性表的一种，更是队列的一个特殊分类，但是由于操作元素的特殊性，循环队列并不能直接由 ArrayList 或 ArrayQueue 实现。所以我们还是使用动态数组结合我们优化后的思想来实现循环队列。我们将循环队列命名为 ArrayLoopQueue 并让其支持泛型，然后实现 Queue 接口，如下：

public class ArrayLoopQueue<E> implements Queue<E> {
	......
}

3.3.2 ArrayLoopQueue 的属性

??既然我们要从头开始定义该循环队列，那么首先我们需要存储数据容器，有了容器那我们还需要容量；然后我们需要队首指针和队尾指针；最后需要一个记录容器中有效元素个数的属性。如下：

private E[] data;   //存储数据的容器
private int front;  //队首指针(实际上就是数组中的索引角标)
private int rear;   //队尾指针
private int size;   //元素的个数
private static int DEFAULT_CAPACITY = 10;   //默认容量

3.3.3 ArrayLoopQueue 的构造器

??上面我们已经为 ArrayLoopQueue 定义了它的属性，下面我们需要定义它的构造方法，我们直接定义一个默认的构造方法，用来创建一个默认容量的 ArrayLoopQueue 。这里插一句，我们的默认容量为 10 ，也就是说能够存储 10 个有效元素，但是我们在优化过程中提到，需要给表尾指针预留出一个理论上为空的空间，因此我们实际创建的容器大小为默认容量加一 。（加的一代表给表尾指针预留出来的空间）。如需其他构造器，自行定义即可。

public ArrayLoopQueue() {
    data = (E[]) new Object[DEFAULT_CAPACITY + 1];
    front = 0;
    rear = 0;
    size = 0;
}

3.3.4 入队的方法 offer()

??该方法是向队列中插入一个元素，队列是在队尾进行插入操作，首先我们应该判断当前队列是否已满，如果满了则需要扩容；否则将需要入队的元素添加在当前队尾指针所指的位置，然后更新队尾指针至下一个位置，最后使有效元素个数加一即可。
??扩容问题： 当前队列已满时，我们如果需要入队一个元素，那么我们就需要对容器进行扩容，我们首先创建一个新的容器，容量为之前的二倍，注意由于我们的实际容量为队尾指针预留了一个位置，并且队尾指针仅需要预留一个位置，所以当我们对旧容器容量乘二后还需要减去一。然后将旧容器中的有效元素复制到新的容器中，然后让 data 重新指向新的容器。
??注：由于我们现在是循环队列，所以在复制旧容器中的有效元素时，我们并不需要按照旧的位置进行复制，而是从新容器的首部开始按照旧队列的顺序将元素依次复制到新容器中，然后将队首指针更新为 0 ，队尾指针更新为最后一个有效元素的下一个位置即可。具体操作请看 resize() 方法。

public void offer(E element) {
    //判断是否需要扩容
    if ((rear + 1) % data.length == front) {
        resize(data.length * 2 - 1);
    }
    data[rear] = element;
    rear = (rear + 1) % data.length;
    size++;
}

3.3.5 出队的方法 poll()

??该方法是从队列中删除一个元素，队列是在队首进行删除操作，首先我们应该判断当前队列是否为空，如果为空就没有元素需要删除；否则先记录将要删除元素的值，然后将队首指针指向将要删除的元素的下一个位置，然后将有效元素个数减一，最后应该判断删除元素后容器是否需要缩容。
??缩容操作： 当前队列中有效元素个数为容量的四分之一，并且容器当前的容量大于默认容量时，我们就需要进行缩容操作。我们首先创建一个新的容器，容量为旧容器的一半，注意由于我们的实际容量为队尾指针预留了一个位置，并且队尾指针仅需要预留一个位置，还因为这里是整型相处，所以当我们对旧容器容量除以二后还需要加上一。然后将旧容器中的有效元素复制到新的容器中，然后让 data 重新指向新的容器。
??注：由于我们现在是循环队列，所以在复制旧容器中的有效元素时，我们并不需要按照旧的位置进行复制，而是从新容器的首部开始按照旧队列的顺序将元素依次复制到新容器中，然后将队首指针更新为 0 ，队尾指针更新为最后一个有效元素的下一个位置即可。具体操作请看 resize() 方法。

public E poll() {
    //判空
    if (isEmpty()) {
        throw new IllegalArgumentException("queue is null");
    }
    E ret = data[front];
    front = (front + 1) % data.length;
    size--;
    if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
        resize(data.length / 2 + 1);
    }
    return ret;
}

3.3.6 扩缩容问题 resize()

??该方法是用来更新容器容量的，通过传入的新容量，创建出新的容器，然后将旧容器中的有效元素复制过来，用来解决扩缩容问题。首先创建出新的容器，容量为传入的新容量，然后定义 index 用来记录新容器中元素的位置，然后从新容器的首部开始按照旧队列的顺序将元素依次复制到新容器中，然后将队首指针更新为 0 ，队尾指针更新为 index 的值即可。以扩容为例，缩容同理，如下：

private void resize(int newLen) {
    E[] newData = (E[]) new Object[newLen];
    int index = 0;
    for (int i = front; i != rear; i = (i + 1) % data.length) {
        newData[index++] = data[i];
    }
    data = newData;
    front = 0;
    rear = index;
}

3.3.7 查看队首元素的方法 element()

??该方法是用来查看当前队首元素，首先需要判断当前队列是否为空，如果为空，则没有队首元素，抛出异常即可；否则直接返回队首指针 front 位置处的元素即可。

public E element() {
    if (isEmpty()) {
        throw new IllegalArgumentException("queue is null");
    }
    return data[front];
}

3.3.8 判空 isEmpty()

??该方法是用来看当前队列是否为空，由优化过程中可知，当队首指针 front 和队尾指针 rear 指向同一个位置时，队列为空。

public boolean isEmpty() {
    return front == rear;
}

3.3.9 清空队列中元素 clear()

??该方法用来清空当前队列，我们直接创建一个新的容器，然后让 data 指向该新容器，然后将有效元素个数归零，然后让队首指针 front 和队尾指针 rear 都指向 0 即可。

public void clear() {
    data = (E[]) new Object[DEFAULT_CAPACITY];
    size = 0;
    front = 0;
    rear = 0;
}

3.3.10 获取有效元素个数 size()

??该方法是用来获取当前队列中的有效元素个数，那么直接返回属性 size 的值即可。

public int size() {
    return size;
}

3.3.11 ArrayLoopQueue 的 equals()

??该方法是用来比较 ArrayLoopQueue 对象的内容是否相同，首先我们判断传入对象 o 是否为空，然后再判断传入对象是否为自己，再判断 o 是否为 ArrayLoopStack 类型的对象，如果是，那我们创建一个新的 ArrayLoopQueue 类型的对象 other 指向 o ，然后判断传入对象 o 的有效元素个数与自己的有效元素个数是否相等，如果不相等则返回 false；否则依次比较两个 ArrayLoopQueue 中存储的有效元素是否相同，如果相同则返回 true 。这些条件都不满足的话，直接返回 false 即可。

public boolean equals(Object o) {
    if (o == null) {
        return false;
    }
    if (this == o) {
        return true;
    }
    if (o instanceof ArrayLoopQueue) {
        ArrayLoopQueue<E> other = (ArrayLoopQueue<E>) o;
        if (size != other.size) {
            return false;
        }
        int i = front;
        int j = other.front;
        while (i != rear) {
            if (!data[i].equals(other.data[j])) {
                return false;
            }
            i = (i + 1) % data.length;
            j = (j + 1) % other.data.length;
        }
        return true;
    }
    return false;
}

3.3.12 ArrayLoopQueue 的 toString()

??该方法是用来输出当前 ArrayLoopQueue 对象存储的信息，首先创建 StringBuilder 对象 sb，先拼接 “[” ，然后判断队列是否为空，如果为空直接拼接 “]” 即可。如果不为空，那我们依次拼接队列中存储的有效元素，如果当前元素是最后一个有效元素，则在拼接完元素后，拼接 “]” 否则拼接 “,” 即可，最后返回 sb.toString() 的结果。

public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    if (isEmpty()) {
        sb.append(']');
        return sb.toString();
    }
    for (int i = front; i != rear; i = (i + 1) % data.length) {
        sb.append(data[i]);
        if ((i + 1) % data.length == rear) {
            sb.append(']');
        } else {
            sb.append(',');
            sb.append(' ');
        }
    }
    return sb.toString();
}

3.3.13 获取迭代器 iterator()

??该方法用来获取 ArrayLoopQueue 的迭代器，可以让该类型支持 foreach 循环，可以迭代遍历队列中存储的元素，既然要获取迭代器，那么我们还需要创建一个构造 ArrayLoopQueue 类的迭代器的类 ArrayLoopQueueIterator，实现迭代器接口 Iterator，重写 hashNext() 和 next() 方法，前者用来判断是否存在下一个元素，后者用来获取该元素。我们定义记录位置的变量 cur ，从队首指针 front 处开始依次往后即可。最后在 iterator() 方法中返回一个 ArrayLoopQueueIterator 类型的对象。

public Iterator<E> iterator() {
    return new ArrayLoopQueueIterator();
}

class ArrayLoopQueueIterator implements Iterator<E> {
    private int cur = front;

    @Override
    public boolean hasNext() {
        return cur != rear;
    }

    @Override
    public E next() {
        E ret = data[cur];
        cur = (cur + 1) % data.length;
        return ret;
    }
}

4. 总结

4.1 ArrayQueue 总结

??至此，ArrayQueue 定义完成，完整代码如下：

import 自己的 Queue 接口包名;
import java.util.Iterator;

public class ArrayQueue<E> implements Queue<E> {
    private ArrayList<E> list;
    public ArrayQueue() {
        list = new ArrayList<>();
    }

    @Override
    public void offer(E element) {
        list.add(list.size(), element);
    }

    @Override
    public E poll() {
        return list.remove(0);
    }

    @Override
    public E element() {
        return list.get(0);
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public String toString() {
        return list.toString();
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayQueue) {
            ArrayQueue other = (ArrayQueue) o;
            return list.equals(other.list);
        }
        return false;
    }
}

4.2 ArrayLoopQueue 总结

??至此，ArrayLoopQueue 定义完成，完整代码如下：

import 自己 Queue 接口所在的包;
import java.util.Iterator;
//循环队列
public class ArrayLoopQueue<E> implements Queue<E> {
    private E[] data;   //存储数据的容器
    private int front;  //队首指针(实际上就是数组中的索引角标)
    private int rear;   //队尾指针
    private int size;   //元素的个数 (f < r  r-f ; r < f  r+L-f)
    private static int DEFAULT_CAPACITY = 10;   //默认容量
    public ArrayLoopQueue() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }
    @Override
    public void offer(E element) {
        //满了没
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }
    @Override
    public E poll() {
        //空不空
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        int index = 0;
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            newData[index++] = data[i];
        }
        data = newData;
        front = 0;
        rear = index;
    }

    @Override
    public E element() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        return data[front];
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
        front = 0;
        rear = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if ((i + 1) % data.length == rear) {
                sb.append(']');
            } else {
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayLoopQueue) {
            ArrayLoopQueue<E> other = (ArrayLoopQueue<E>) o;
            if (size != other.size) {
                return false;
            }
            int i = front;
            int j = other.front;
            while (i != rear) {
                if (!data[i].equals(other.data[j])) {
                    return false;
                }
                i = (i + 1) % data.length;
                j = (j + 1) % other.data.length;
            }
            return true;
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayLoopQueueIterator();
    }

    class ArrayLoopQueueIterator implements Iterator<E> {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}