第4章. 队列(Queue)

队列(Queue)

一、队列的基本概念

• 队列是一种特殊的线性表，只能在头尾两端进行操作
• 队尾(rear)：只能从队尾添加元素，一般叫做enQueue，入队
• 队头(front)：只能从队头移除元素，一般叫做deQueue，出队
• 先进先出的原则，FIRST IN FIRST OUT，FIFO

二、队列的接口设计

• int size()； // 元素的数量
• boolean isEmpty()； // 队列是否为空
• void clear()； // 清空
• void enQueue(E element)； // 入队
• E deQueue()； // 出队
• E front()； // 获取队列的头元素

• 队列的内部实现可以直接用以前学过的数据结构：动态数组，链表
• 优先使用双向链表，因为队列主要是往头尾操作元素

方法一：继承之前写的ArrayList或DoubleLinkedList

用动态数组效率低，推荐使用双向链表。

package DataStructure._05队列;

import DataStructure._01动态数组.ArrayList;

/**
 * @author keyongkang
 * @date 2022-07-22-20:03
 */
public class Queue<E> extends ArrayList<E> {

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

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

    // 清空
    public void clear() {
        super.clear();
    }

    // 入队
    public void enQueue(E element) {
        add(0, element);
    }

    // 出队
    public E deQueue() {
        return remove(size() - 1);
    }

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

方法二：把Java内置的LinkedList作为Stack的成员变量

package DataStructure._05队列;

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

/**
 * @author keyongkang
 * @date 2022-07-22-20:03
 */
public class Queue<E>  {
    private List<E> list = new LinkedList<>(); // 索引0的位置记作队头，最后的位置记作队尾

    // 元素的数量
    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);
    }
}

三、Java官方Queue实现

Java中LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue使用

• Queue< String > queue = new LinkedList<>()；

常用的操作：

• peek()：返回队头
• size()：返回队长
• poll()：获取并移除此队头，如果为空，则返回null
• remove()：获取并移除此队列的头
• offer(E e)：队尾添加。添加成功返回true，添加失败返回false
• add(E e)：队尾添加。如果容量允许将会返回true，否则抛异常

双端队列(Deque—double ended queue)

• 双端队列是能再头尾两端添加、删除的队列(队头、队尾都可以入队和出队)
• 英文deque是Double ended queue的简称

四、双端队列的接口设计

• int size()：元素的数量
• boolean isEmpty()：是否为空
• void enQueueRear(E element)：从队尾入队
• void enQueueFront(E element)：从队头入队
• E deQueueFront()：从队头出队
• E deQueueRear()： 从队尾出队
• E front()：获取队列的头元素
• E rear()：获取队列的尾元素
• void clear()：清空队列的所有元素

由于双端队列需要在头尾进行插入和删除操作，所以我们使用双向链表来实现

方法一：继承之前写的DoubleLinkedList(省略)

方法二：把Java内置的LinkedList作为Deque的成员变量

package DataStructure._05队列;

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

/**
 * @author keyongkang
 * @date 2022-07-23-9:45
 */
public class Deque<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 enQueueRear(E element) {
        list.add(element);
        //list.add(list.size(), element);
    }

    // 从队头入队
    public void enQueueFront(E element) {
        list.add(0, element);
    }

    // 从队头出队
    public E deQueueFront() {
        return list.remove(0);
    }

    // 从队尾出队
    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);
    }
}

五、Java官方Deque实现

Java官方用LinkedList实现了Deque接口

• Deque< Integer > deque = new LinkedList<>();

循环队列(Circle Queue)

• 循环队列底层使用数组来实现

其实队列的底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度，这个用数组实现并且优化之后的队列叫做：循环队列。

入队/出队：

扩容：

从对头开始，依次把所有元素放在新数组中，然后将front置位0。

循环双端队列(Circle Deque)

循环双端队列：可以进行两端添加、删除操作的循环队列。