队列

/ 数据结构与算法 / 0 条评论 / 216浏览

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

队列(queue)是一种先进先出(FIFO)的线性数据结构。

允许插入的一端称为队尾,允许删除的一端称为队头。

栈有两种基本实现: 顺序结构链式结构

队列的顺序结构实现

这里基于动态数组实现队列:

Interface Queue <----- ArrayQueue

实现

这里我使用自己封装的泛型动态数组来实现顺序结构的队列。

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

    private Array<E> array;

    public ArrayQueue() {
        array = new Array<>();
    }

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

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

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

    @Override
    public int getSize() {
        return array.getSize();
    }

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

时间复杂度分析

执行出队操作后,需要将除队首元素之外的其他元素前移,所以 dequeue() 方法时间复杂度为 O(n),为了使该方法时间复杂度为 O(1),我们不将剩余元素前移,引出下面的循环队列:

循环队列

队列头尾相接的顺序存储结构称为循环队列。

循环队列使得数组队列出队操作(dequeue)的时间复杂度降为 O(1) , 其实这是均摊时间复杂度

循环队列的实现

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

    private E[] data;
    private int front; // point to first element in queue
    private int tail;  // point to last element'next space in queue
    private int size;

    public LoopQueue(int capacity) {
        // waste a space for judge queue full or not
        data = (E[]) new Object[capacity + 1];
    }

    public LoopQueue() {
        this(10);
    }

    @Override
    public void enqueue(E e) {
        // expand the capacity if queue is full
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {
        if (this.isEmpty()) {
            throw new IllegalArgumentException("can`t dequeue from an empty Queue");
        }

        E ret = data[front];
        data[front] = null;
        // maintenance the front point
        front = (front + 1) % data.length;

        // reduce the capacity to save space
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

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

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

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

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            // it`s convenient to index newData from zero,and data may have offset
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        // maintenance the front and tail points
        front = 0;
        tail = size;
    }

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

时间复杂度分析

队列的链式结构实现

public class LinkedListQueue<E> implements Queue<E> {
    private class Node {
        E e;
        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; // point first node
    private Node tail; // point last node
    private int size;

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

    @Override
    public void enqueue(E e) {
        // queue empty,both head and tail is null
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("cannot dequeue from an element queue");
        }

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        // if queue only have one element
        if (head == null) {
            tail = null; // tail shouldn't not point retNode
        }
        size--;

        return retNode.e;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        return head.e;
    }

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

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}

复杂度分析

即使存在尾指针,基于链表实现的队列在进行出队操作时,复杂度依然是O(n),对于这种情况我们使用双链表来。

三种队列比较

在完成数组队列和循环队列的编码后,我们测试这两种线性数据结构的性能

这里我们产生随机数并让随机数入队和出队。

import org.junit.Test;
import java.util.Random;

public class CompareQueueTest {

    public static double testQueue(Queue<Integer> queue, int opCount) {
        Random random = new Random();

        long startTime = System.nanoTime();

        // enqueue and dequeue
        for (int i = 0; i < opCount; i++) {
            queue.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            queue.dequeue();
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    @Test
    public void arrayAndLoopAndLinkedListQueueCompare() {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        System.out.println("ArrayQueue time: " + testQueue(arrayQueue, opCount) + "s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        System.out.println("LoopQueue time: " + testQueue(loopQueue, opCount) + "s");

        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        System.out.println("LinkedListQueue time: " + testQueue(linkedListQueue, opCount) + "s");
    }

}

结果

ArrayQueue time: 3.803667585s
LoopQueue time: 0.011321989s
LinkedListQueue time: 0.008049417s

数组队列出队时出队首元素外其余元素需要向前移动,故更耗时

循环队列和链式队列时间复杂度相似,具体时间差异取决于本机配置、JVM以及实现中方法其他语句等等

提示 : 完整代码放在了我的 gitee 上面