DS03:队列

基本特性

特性

与栈相反，队列的基本特性为先入先出（FIFO）。

其与栈相同，也是一种线性表，允许在队尾插入元素，在队头删除元素。

用处

首先想到的就是操作系统中的进程调度方法？还有当然就是广度优先遍历了。

需要实现的基本内容

实现队列可以构建相应的接口，其需要实现的方法如下：

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);	// 入队列
    E dequeue();	// 出队列
    E getFront();	// 获取队首元素
}

队列有三种实现方法，分别是线性存储（底层数据结构为动态数组，根据实现思路区别可分为顺序队列与循环队列），链式存储（底层数据结构为链表）

顺序队列

与栈的相应实现方法相同。

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

    private 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 e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

}

循环队列

实现思路

顺序队列有一个弊端，就是当出队列操作后，动态数组的前面会产生很大的空隙，造成内存的浪费。为了解决这个问题，提出了循环队列的思想，其核心思想就是分别使用front和tail记录队列的队头和队尾，具体思路见如下示意图（图来源于网上）。

其中，为避免队列为空与队列为满产生的条件判断重叠（即都为front==tail），我们可以将队列满的条件设置为tail+1==front（即留出一个空间不进行使用）。

除此之外，由于是“循环”队列，因此tail可能小于front，因此需要使用(tail) % (data.length)的形式对相关逻辑进行判断

具体实现

具体实现如下

public class LoopQueue<E> implements Queue<E> {

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

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

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return data.length - 1;
    }


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

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

    @Override
    public void enqueue(E e) {
    	// 判断队列满了的条件
        if((tail+1)%data.length == front) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;	// 对tail进行更新
        size++;
    }

    @Override
    public E dequeue() {
        if(isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        E res = data[front];
        data[front] = null;
        front = (front+1) % data.length;
        size--;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return res;
    }

    @Override
    public E getFront() {
        return data[front];
    }

    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i=0;i<size;i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }
}

链式队列

实现分析

需要记录队列的队首head与队尾tail。其中队首对应链表头（删除方便），队尾对应链表尾。

具体实现

1、类中基础属性

public class LinkedListQueue<E> implements Queue<E> {

	// 定义链表的节点，作为内部类
    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }
    }

    private Node head, tail;
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }
}

2、入队列

@Override
public void enqueue(E e) {
    if(tail==null) {
        tail = new Node(e);
        head = tail;
    }
    else {
        tail.next = new Node(e);
        tail = tail.next;
    }
    size++;
}

3、出队列

@Override
public E dequeue() {
    if(isEmpty()) {
        throw new IllegalArgumentException("Can not");
    }
    Node res = head;
    head = head.next;
    res.next = null;
    if(head == null) {
        tail = null;
    }
    size--;
    return res.e;
}

其余方法略

复杂度分析与测试

复杂度分析

不同队列实现方式的差距主要体现在出队中。

其中顺序队列的出队的时间复杂度为O(n)，而循环队列与链接队列出队的时间复杂度为O(1)。

复杂度测试

import java.util.Random;

public class Main {

	// 用于计算运行时间
    private static double testQueue(Queue<Integer> q, int opCount) 	   {
        long startTime = System.nanoTime();

        Random random = new Random();
        for(int i=0; i<opCount;i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for(int i=0; i<opCount;i++) {
            q.dequeue();
        }

        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {
        int opCount = 100000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue,opCount);
        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue,opCount);
        System.out.println("ArrayQueue: "+time1+" s");
        System.out.println("LoopQueue: "+time2+" s");
        System.out.println("LinkListQueue: "+time3+" s");
    }
}
///////////////////////////////////////////
ArrayQueue: 45.9780233 s
LoopQueue: 0.0132119 s
LinkListQueue: 0.0092766 s

由此可以看出，当操作数达到一定级别时，顺序队列的实现方式的速度要远小于其他两种实现方法。这与之前的分析是吻合的。

Donate