队列的应用

队列也是一种线性结构，只能从一端（队尾）添加元素，只能从另一端（队首）取出元素

先进先出（First In First Out）

数组队列

数组队列的实现

enqueue()、dequeue()、getFront()、getSize()、isEmpty()方法就足够操作队列了

public class Algorithm {

    public static void main(String[] args) {

        ArrayQueue<Integer> queue = new ArrayQueue<>(20);

        for (int i = 0; i < 5; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }

        System.out.println(queue.getSize());
        System.out.println(queue.getFront());
        System.out.println(queue);

        queue.dequeue();
        System.out.println(queue);

        System.out.println(queue.isEmpty());
    }
}

/**
 * 创建队列接口，定义抽象方法
 */
interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E element);
    E dequeue();
    E getFront();
}

/**
 * 实现队列接口，创建数组队列类
 */
class ArrayQueue<E> implements Queue<E>{

    /**
     * 使用动态数组实现队列
     */
    Array<E> array;

    public ArrayQueue(int capacity){

        array = new Array<>(capacity);
    }

    public ArrayQueue(){

        array = new Array<>();
    }

    /**
     * 重写队列接口的方法
     */
    @Override
    public int getSize() {

        return array.getSize();
    }

    @Override
    public boolean isEmpty() {

        return array.isEmpty();
    }

    @Override
    public void enqueue(E element) {

        array.addLast(element);
    }

    @Override
    public E dequeue() {

        return array.removeFirst();
    }

    /**
     * getFront()方法查看队首元素
     */
    @Override
    public E getFront() {

        return array.getFirst();
    }

    /**
     * 重写toString()方法打印队列的信息，如果调用array.toString()方法，打印的是动态数组的信息
     */
    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append("Queue: front [");

        for (int i = 0; i < array.getSize(); i++) {

            str.append(array.get(i));

            if (i != array.getSize() - 1){
                str.append(", ");
            }
        }
        str.append("] tail");

        return str.toString();
    }
}

class Array<E> {

    private E[] data;
    private int size;

    public Array(int capacity){

        data = (E[]) new Object[capacity];
        size = 0;
    }

    public Array(){

        this(10);
    }

    public void add(int index, E element){

        if (index < 0 || index > size){
            throw new IllegalArgumentException("索引值非法");
        }

        if (size == data.length){
            resize(2 * data.length);
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        data[index] = element;
        size++;
    }

    public void addLast(E element){

        add(size, element);
    }

    public void remove(int index){

        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("索引值非法");
        }

        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }

        size--;
        data[size] = null;

        if (size == data.length / 2 && data.length / 2 != 0){
            resize(data.length / 2);
        }
    }

    public E removeFirst(){

        if (size == 0) {
            throw new IllegalArgumentException("索引值非法");
        }

        E tem = data[0];

        remove(0);

        return tem;
    }

    public int getSize(){

        return size;
    }

    public E get(int index){

        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("索引值非法");
        }

        return data[index];
    }

    public E getFirst(){

        return get(0);
    }

    private void resize(int newCapacity){

        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }

        data = newData;
    }

    public boolean isEmpty(){

        return size == 0;
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append(String.format("数组的容量为%d，元素个数为%d\n", data.length, size));
        str.append("[");

        for (int i = 0; i < size; i++) {

            str.append(data[i]);
            if (i != size - 1){
                str.append(", ");
            }
        }

        str.append("]");

        return str.toString();
    }
}

数组队列的复杂度分析

getFront()、getSize()、isEmpty()方法的时间复杂度为O(1)

enqueue()方法的均摊复杂度为O(1)

dequeue()方法的时间复杂度是O(n)，因为每次出队时，后面的所有元素都要往前移一位

循环队列

循环队列的实现

循环队列在队首元素出队时，只是将front标志位加一，而不进行所有元素的移动。当元素填满后面的位置时，如果front标志位不为零，就将tail标志位设为零，将元素添加进前部的空间

当元素刚好填满队列时，front == 0，tail == length - 1（tail取不到length）；或者使用了前部的空间时满了，front == tail + 1（留一个空位）

综合两种情况，front == (tail + 1) % length代表队列满了，而front == tail代表队列空了

public class Algorithm {

    public static void main(String[] args) {

        LoopQueue<Integer> queue = new LoopQueue<>(5);

        for (int i = 0; i < 6; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }

        System.out.println(queue.getSize());
        System.out.println(queue.getFront());

        queue.dequeue();
        System.out.println(queue);

        System.out.println(queue.isEmpty());
    }
}

/**
 * 创建队列接口，定义抽象方法
 */
interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E element);
    E dequeue();
    E getFront();
}

/**
 * 实现队列接口，创建循环队列类
 */
class LoopQueue<E> implements Queue<E>{

    /**
     * 使用动态数组实现循环队列
     */
    private E[] data;
    private int front, tail, size;

    public LoopQueue(int capacity){

        /**
         * 因为循环队列会浪费一个空间，为了确保能存储capacity个元素，初始化时加1
         */
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){

        this(5);
    }

    /**
     * 重写循环队列接口的方法
     */
    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {

        /**
         * front == tail时，说明队列没有元素
         */
        return front == tail;
    }

    @Override
    public void enqueue(E element) {

        /**
         * 入队判断是否满了
         * front == (tail + 1) % data.length时，说明队列元素满了，需要扩容
         * 如果front == 0，此时tail是等于data.length - 1的，然后就会扩容，所以取不到data.length
         */
        if (front == (tail + 1) % data.length){
            resize(2 * (data.length - 1));
        }

        data[tail] = element;

        /**
         * tail不能直接加1，因为可能等于data.length - 1，因此加1后对长度取余，循环取值
         */
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {

        /**
         * 出队判断是否为空，空了只能抛出异常
         */
        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }

        E tem = data[front];

        /**
         * 因为该元素为引用，所以在不需要时将其赋值为null，避免空间泄露
         */
        data[front] = null;
        front = (front + 1) % data.length;
        size--;

        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return tem;
    }

    public void resize(int newCapacity){

        E[] newData = (E[]) new Object[newCapacity + 1];

        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * getFront()方法查看队首元素
     */
    @Override
    public E getFront() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }
        return data[front];
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length - 1, size));

        for (int i = 0; i < size; i++) {

            str.append(data[(front + i) % data.length]);

            /**
             * 此处不能写(front + i) % data.length != tail - 1
             * 因为如果tail为0，就出现负索引了
             */
            if ((front + i + 1) % data.length != tail){
                str.append(", ");
            }
        }

        str.append("] tail");

        return str.toString();
    }
}

循环队列的复杂度分析

dequeue()方法的均摊复杂度降为了O(1)

数组队列和循环队列的性能比较

import java.util.Random;

public class Algorithm {

    public static void main(String[] args) {

        int count = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        System.out.println("数组队列用时：" + test(arrayQueue, count) + "秒");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        System.out.println("循环队列用时：" + test(loopQueue, count) + "秒");
    }

    /**
     * 多态性可以让接口接收不同的实现接口的类对象
     */
    public static double test(Queue<Integer> name, int count){

        Random random = new Random();

        long startTime = System.nanoTime();

        for (int i = 0; i < count; i++) {
            name.enqueue(random.nextInt(count));
        }

        for (int i = 0; i < count; i++) {
            name.dequeue();
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }
}

interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E element);
    E dequeue();
    E getFront();
}

class LoopQueue<E> implements Queue<E>{

    private E[] data;
    private int front, tail, size;

    public LoopQueue(int capacity){

        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){

        this(5);
    }

    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {

        return front == tail;
    }

    @Override
    public void enqueue(E element) {

        if (front == (tail + 1) % data.length){
            resize(2 * (data.length - 1));
        }

        data[tail] = element;

        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }

        E tem = data[front];

        data[front] = null;
        front = (front + 1) % data.length;
        size--;

        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return tem;
    }

    public void resize(int newCapacity){

        E[] newData = (E[]) new Object[newCapacity + 1];

        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E getFront() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }
        return data[front];
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length - 1, size));

        for (int i = 0; i < size; i++) {

            str.append(data[(front + i) % data.length]);

            if ((front + i + 1) % data.length != tail){
                str.append(", ");
            }
        }

        str.append("] tail");

        return str.toString();
    }
}

class ArrayQueue<E> implements Queue<E>{

    Array<E> array;

    public ArrayQueue(int capacity){

        array = new Array<>(capacity);
    }

    public ArrayQueue(){

        array = new Array<>();
    }

    @Override
    public int getSize() {

        return array.getSize();
    }

    @Override
    public boolean isEmpty() {

        return array.isEmpty();
    }

    @Override
    public void enqueue(E element) {

        array.addLast(element);
    }

    @Override
    public E dequeue() {

        return array.removeFirst();
    }

    @Override
    public E getFront() {

        return array.getFirst();
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append("Queue: front [");

        for (int i = 0; i < array.getSize(); i++) {

            str.append(array.get(i));

            if (i != array.getSize() - 1){
                str.append(", ");
            }
        }
        str.append("] tail");

        return str.toString();
    }
}

class Array<E> {

    private E[] data;
    private int size;

    public Array(int capacity){

        data = (E[]) new Object[capacity];
        size = 0;
    }

    public Array(){

        this(10);
    }

    public void add(int index, E element){

        if (index < 0 || index > size){
            throw new IllegalArgumentException("索引值非法");
        }

        if (size == data.length){
            resize(2 * data.length);
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        data[index] = element;
        size++;
    }

    public void addLast(E element){

        add(size, element);
    }

    public void remove(int index){

        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("索引值非法");
        }

        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }

        size--;
        data[size] = null;

        if (size == data.length / 2 && data.length / 2 != 0){
            resize(data.length / 2);
        }
    }

    public E removeFirst(){

        if (size == 0) {
            throw new IllegalArgumentException("索引值非法");
        }

        E tem = data[0];

        remove(0);

        return tem;
    }

    public int getSize(){

        return size;
    }

    public E get(int index){

        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("索引值非法");
        }

        return data[index];
    }

    public E getFirst(){

        return get(0);
    }

    private void resize(int newCapacity){

        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }

        data = newData;
    }

    public boolean isEmpty(){

        return size == 0;
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append(String.format("数组的容量为%d，元素个数为%d\n", data.length, size));
        str.append("[");

        for (int i = 0; i < size; i++) {

            str.append(data[i]);
            if (i != size - 1){
                str.append(", ");
            }
        }

        str.append("]");

        return str.toString();
    }
}

作业1：浪费一个空间，不使用size变量

public class Algorithm {

    public static void main(String[] args) {

        LoopQueue<Integer> queue = new LoopQueue<>(5);

        for (int i = 0; i < 6; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }

        System.out.println(queue.getSize());
        System.out.println(queue.getFront());

        queue.dequeue();
        System.out.println(queue);

        System.out.println(queue.isEmpty());
    }
}

interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E element);
    E dequeue();
    E getFront();
}

class LoopQueue<E> implements Queue<E>{

    private E[] data;
    private int front, tail;

    public LoopQueue(int capacity){

        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
    }

    public LoopQueue(){

        this(5);
    }

    @Override
    public int getSize() {

        /**
         * 比较front和tail的前后顺序就可以算出队列大小
         */
        if (front <= tail) {
            return tail - front;
        }
        else {
            return tail + data.length - front;
        }
    }

    @Override
    public boolean isEmpty() {

        return front == tail;
    }

    @Override
    public void enqueue(E element) {

        if (front == (tail + 1) % data.length){
            resize(2 * (data.length - 1));
        }

        data[tail] = element;

        tail = (tail + 1) % data.length;
    }

    @Override
    public E dequeue() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }

        E tem = data[front];

        data[front] = null;
        front = (front + 1) % data.length;

        if (getSize() == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return tem;
    }

    public void resize(int newCapacity){

        E[] newData = (E[]) new Object[newCapacity + 1];

        for (int i = 0; i < getSize(); i++) {
            newData[i] = data[(front + i) % data.length];
        }

        data = newData;
        front = 0;
        tail = getSize();
    }

    @Override
    public E getFront() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }
        return data[front];
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length - 1, getSize()));

        for (int i = 0; i < getSize(); i++) {

            str.append(data[(front + i) % data.length]);

            if ((front + i + 1) % data.length != tail){
                str.append(", ");
            }
        }

        str.append("] tail");

        return str.toString();
    }
}

作业2：使用size变量，不浪费一个空间

public class Algorithm {

    public static void main(String[] args) {

        LoopQueue<Integer> queue = new LoopQueue<>(5);

        for (int i = 0; i < 6; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }

        System.out.println(queue.getSize());
        System.out.println(queue.getFront());

        queue.dequeue();
        System.out.println(queue);

        System.out.println(queue.isEmpty());
    }
}

interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E element);
    E dequeue();
    E getFront();
}

class LoopQueue<E> implements Queue<E>{

    private E[] data;
    private int front, tail, size;

    public LoopQueue(int capacity){

        data = (E[]) new Object[capacity];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){

        this(5);
    }

    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {

        return size == 0;
    }

    @Override
    public void enqueue(E element) {

        if (size == data.length) {
            resize(2 * data.length);
        }

        data[tail] = element;

        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }

        E tem = data[front];

        data[front] = null;
        front = (front + 1) % data.length;
        size--;

        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return tem;
    }

    public void resize(int newCapacity){

        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E getFront() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }
        return data[front];
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length, size));

        for (int i = 0; i < size; i++) {

            str.append(data[(front + i) % data.length]);

            if ((front + i + 1) % data.length != tail){
                str.append(", ");
            }
        }

        str.append("] tail");

        return str.toString();
    }
}

双端队列

双端队列，队首和队尾都可以入队和出队

队首出队和队尾入队和普通队列一样，需要新增队首入队和队尾出队的方法

public class Algorithm {

    public static void main(String[] args) {

        Deque<Integer> queue = new Deque<>(5);

        for (int i = 0; i < 10; i++) {

            /**
             * 偶数在队首入队，奇数在队尾入队
             */
            if (i % 2 == 0) {
                queue.addFront(i);
                System.out.println(queue);
            }
            else {
                queue.addLast(i);
                System.out.println(queue);
            }
        }

        for (int i = 0; i < 10; i++) {

            /**
             * 偶数在队首出队，奇数在队尾出队
             */
            if (i % 2 == 0) {
                queue.removeFront();
                System.out.println(queue);
            }
            else {
                queue.removeLast();
                System.out.println(queue);
            }
        }

        System.out.println(queue.isEmpty());
    }
}

interface Queue<E> {

    int getSize();
    boolean isEmpty();

    /**
     * 新增队首入队和队尾出队的方法
     */
    void addFront(E element);
    void addLast(E element);
    E removeFront();
    E removeLast();
    E getFront();
    E getLast();
}

class Deque<E> implements Queue<E>{

    private E[] data;
    private int front, tail, size;

    public Deque(int capacity){

        data = (E[]) new Object[capacity];
        front = 0;
        tail = 0;
        size = 0;
    }

    public Deque(){

        this(5);
    }

    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {

        return size == 0;
    }

    @Override
    public void addLast(E element) {

        if (size == data.length) {
            resize(2 * data.length);
        }

        data[tail] = element;

        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public void addFront(E element){

        if (size == data.length){
            resize(2 * data.length);
        }

        /**
         * 队首入队，需要判断front是否为0
         */
        front = front == 0 ? data.length - 1 : front - 1;
        data[front] = element;
        size++;
    }

    @Override
    public E removeFront() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }

        E tem = data[front];

        data[front] = null;
        front = (front + 1) % data.length;
        size--;

        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return tem;
    }

    @Override
    public E removeLast(){

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }

        /**
         * 队尾出队，需要判断tail是否为0
         */
        tail = tail == 0 ? data.length - 1 : tail - 1;

        E tem = data[tail];
        data[tail] = null;

        size--;

        if (size == data.length / 4 && data.length / 2 != 0){
            resize(data.length / 2);
        }

        return tem;
    }

    public void resize(int newCapacity){

        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E getFront() {

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }
        return data[front];
    }

    @Override
    public E getLast(){

        if (isEmpty()){
            throw new IllegalArgumentException("队列空了");
        }
        return data[tail == 0 ? data.length - 1 : tail - 1];
    }

    @Override
    public String toString() {

        StringBuilder str = new StringBuilder();

        str.append(String.format("Queue: 队列的容量为%d，元素个数为%d\nfront [", data.length, size));

        for (int i = 0; i < size; i++) {

            str.append(data[(front + i) % data.length]);

            /**
             * i != size - 1判断是否是最后一个元素更方便
             */
            if (i != size - 1){
                str.append(", ");
            }
        }

        str.append("] tail");

        return str.toString();
    }
}

拓展：为什么不推荐使用Stack类实现栈，而用Deque类

因为Stack类继承了Vetor类，可以使用父类的其他方法操作栈，破坏了类的封装性

而Deque作为双端队列，可以实现栈的功能。但事实上，由于其可以双端进行操作，也破坏了类的封装性

虽然Java推荐使用Deque类实现栈，但最好的方式是自己设计一个栈类