【数据结构】队列实现的5种方式及时间复杂度对比分析

1. 使用数组实现一个简单的队列

/**
 *           ===========================
 * 队列首部   00000000000000000000000000   队列尾部
 *           ===========================
 */
public class ArrayQueue<Element> implements Queue<Element>{
 
    // 通过内部的array来实现
    private Array<Element> array;
    // 构造函数
    public ArrayQueue(int capacity){
        this.array = new Array<>(capacity);
    }
    // 默认的构造函数
    public ArrayQueue(){
        this.array = new Array<>();
    }
 
    @Override
    public int getSize() {
        return this.array.getSize();
    }
 
    @Override
    public boolean isEmpty() {
        return this.array.isEmpty();
    }
 
    public int getCapacity(){
        return this.array.getCapacity();
    }
 
    @Override
    public void enqueue(Element element) {
        // 进入队列(数组的末尾来添加元素)
        this.array.addLast(element);
    }
 
    @Override
    public Element dequeue() {
        // 出队列(删除最后一个元素)，数组的第一个元素
        return this.array.removeFirst();
    }
 
    @Override
    public Element getFront() {
        // 获取第一个元素(对首部的第一个元素)
        return this.array.getFirst();
    }
 
 
    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        // 使用自定义的方式实现数组的输出
        stringBuilder.append("Queue:");
        // 开始实现数组元素的查询
        stringBuilder.append("front [");
        for (int i = 0; i < this.array.getSize(); i++) {
            stringBuilder.append(this.array.get(i));
            // 开始实现数组元素的回显(只要下表不是最后一个元素的话，就直接输出这个元素)
            if (i != this.array.getSize()-1)
                stringBuilder.append(", ");
        }
        stringBuilder.append("] tail");
        // 实现数组元素的输出
        return stringBuilder.toString();
    }
}

2. 使用数组实现一个循环队列（维护一个size变量）

/**
 * 循环队列的几个要点：
 * 1. tail = head 说明队列就是满的
 * 2. 循环队列需要空出来一个位置
 */
public class LoopQueue<E> implements Queue {
    private E[] data;
    private int head;               // 首部指针
    private int tail;               // 尾部指针
    private int size;           // 可以通过head以及tail的位置情况去计算size的大小【注意是不能直接使用getCapacity的】
 
 
    // 实现循环队列
    public LoopQueue() {
        // 设置一个队列的默认的大小
        this(10);
    }
 
    // 循环队列的实现
    public LoopQueue(int capacity) {
        this.data = (E[]) new Object[capacity + 1];
        // 需要多出来一个
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }
 
    @Override
    public int getSize() {
        // 计算容量大小
        return this.size;
    }
 
 
    // capacity表示的这个队列中最大可以容纳的元素个数【这是一个固定值】
    @Override
    public int getCapacity() {
        // 由于队列默认占了一个空的位置，因此sizt = this.length-1
        return this.data.length - 1;
    }
 
 
    // 当head和tail的值相同的时候队列满了
    public boolean isEmpty() {
        return head == tail;
    }
 
 
    @Override
    public void enqueue(Object value) {
        // 1. 开始判断队列有没有充满, 因为数组的下表是不会改变的，所以这里需要以数组的下标为一个参考点， 而不是this.data.length-14
        if ((tail + 1) % this.data.length == head) {
            // 2. 开始进行扩容, 原来的二倍, 由于默认的时候已经白白浪费了一个空间，因此这里就直接扩容为原来的二倍即可
            resize(2 * getCapacity());
        }
 
        // 2. 如果没有满的话，就开始添加元素
        this.data[tail] = (E) value;
        // 3. 添加完毕之后(tail是一个循环的位置，不可以直接相加)
//        this.tail = 2;
        this.tail = (this.tail+1) % data.length;  // data.length对于数组的下标
//        int i = (this.tail + 1) % data.length;
        // 4. 队里的长度
        this.size++;
    }
 
 
    /**
     * 开始resize数组元素
     *
     * @param capacity
     */
    private void resize(int capacity) {
        // 开始进行数组的扩容
        // 1. 创建一个新的容器(默认多一个位置)
        E[] newData = (E[]) new Object[capacity + 1];
        // 2. 开始转移元素到新的容器
        for (int i = 0; i < size; i++) {
            int index = (head + i) % data.length;
            newData[i] = data[index];
        }
 
        // 添加完毕之后，开始回收之前的data，data里面的数据一直是最新的数据
        this.data = newData;        // jvm的垃圾回收机制会自动回收内存data
 
        // 3. 添加完毕
        this.head = 0;
        // 4. 指向尾部
        this.tail = size;
    }
 
 
    @Override
    public Object dequeue() {
        // 1. 先来看下队列中有没有元素数据
        if (this.size == 0)
            throw new IllegalArgumentException("Empty queue cannot dequeue!");
        // 2. 开始看一下内存的大小
        Object ret = this.data[head];
        // 3. 开始删除数据
        this.data[head] = null;
 
 
 
        // TODO 注意点：直接使用+1而不是使用++
        // 4. 开始向后移动， 为了防止出错，尽量使用 this.head+1来进行操作，而不是使用 this.haad++, 否则可能会出现死循环的情况【特别注意！！！！！！！！！！！！】
        this.head = (this.head+1) %  data.length;
 
        // 5. 计算新的容量大小
        this.size--;
 
 
        // 6. 开始进行缩容操作， d当容量为1， size为0的时候，就不需要缩小容量、、
        if (this.size == this.getCapacity() / 4)
            // 缩小为原来的一半大小的容量
            resize(this.getCapacity() / 2);
 
        // 获取出队列的元素
        return ret;
    }
 
 
    @Override
    public Object getFront() {
        // 由于front的位置一直是队列的第一个元素，直接返回即可
        if (this.size == 0)
            throw new IllegalArgumentException("Empty queue cannot get element!");
        return this.data[head];
    }
 
 
 
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("Array : size=%d, capacity=%d; ", size, getCapacity()));
        stringBuilder.append("LoopQueue head [");
 
 
        // 第一个元素在head的位置，最后一个元素在tail-1的位置
        // 注意循环队列的遍历方式，是一个循环
        for (int i = this.head; i != tail; i = (i+1) % data.length) {
            stringBuilder.append(data[i]);
            // 只要不是最后一个元素的话, 由于循环条件中已经规定了i!=tail, 因此这里是不能直接这样来判断的
            if ((i+1)%data.length == this.tail) {
                // 此时就是最后一个元素
            } else {
                stringBuilder.append(", ");
            }
 
        }
 
 
        stringBuilder.append("] tail");
        return stringBuilder.toString();
    }
}

3.使用数组实现一个循环队列（不维护size变量）

/**
 * 使用数组实现一个循环队列的数据结构
 */
public class WithoutSizeLoopQueue<E> implements Queue<E> {
    private E[] data;
    private int head;
    private int tail;
 
    public WithoutSizeLoopQueue(int capacity) {
        // 泛型不能直接被实例化， 由于循环队列默认会空出来一个位置，这里需要注意
        this.data = (E[]) new Object[capacity + 1];
        this.head = 0;
        this.tail = 0;
    }
 
    public WithoutSizeLoopQueue() {
        this(10);
    }
 
 
    @Override
    public int getSize() {
        // 计算数组的元素个数
        if (tail >= head) {
            return tail - head;
        } else {
            int offSet = head - tail;
            return this.data.length - offSet;
        }
    }
 
    @Override
    public int getCapacity() {
        return data.length - 1;
    }
 
    @Override
    public void enqueue(E value) {
        // 开始进入队列
        // 1. 先来看下队列有没有满
        if ((tail + 1) % data.length == head)
            // 开始扩大容量
            resize(2 * getCapacity());
        // 2. 开始进入队列
        data[tail] = value;
        // 3. 开始移动下标
        tail++;
        // 4. 开始更新容量【没必要】
    }
 
    public void resize(int newCapacity) {
        // 1.  更新为新的容量
        E[] newData = (E[]) new Object[newCapacity + 1];
        // 2. 开始转移数据到新的数组中去
        for (int i = 0; i < getSize(); i++) {
            newData[i] = data[(i + head) % data.length];
        }
        // 3. 销毁原来的数据信息
        data = newData;
 
 
        // 【错误警告】bug：移动到新的这个数组里面之后，需要重新改变head和tail的位置【bug】
        tail = getSize();           // 尾部节点始终指向最后一个元素的后面一个位置，  此时如果直接使用getSize实际上获取到的是上一次的元素的个数，而不是最新的元素的个数信息（需要放在前面，否在获取到的size就不是同一个了，特别重要）
        head = 0;                   // 头节点指向的是第一个元素
 
 
        // 4. 直接销毁
        newData = null;
    }
 
    @Override
    public E dequeue() {
        // 1.先来看下队列是否为空
        if (getSize() == 0)
            throw new IllegalArgumentException("Empty queue cannot dequeue!");
        // 2.开始出head位置的元素
        E value = data[head];
        // 3. 删除元素
        data[head] = null;
        // 4. 移动head
        head = (head+1) % data.length;
 
        // 此时需要进行一次判断
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
 
 
        // 如果数组缩小容量之后，这里的
 
        return value;
    }
 
    @Override
    public E getFront() {
        return dequeue();
    }
 
 
    @Override
    public String toString(){
        // 开始遍历输出队列的元素
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("LoopQueue: size = %d, capacity = %d\n", getSize(), getCapacity()));
        stringBuilder.append("front ");
        // 从head位置开始遍历
        for (int i = head; i != tail ; i = (i+1) % data.length) {
            stringBuilder.append(data[i]);
            if ((i + 1) % data.length != tail)
                stringBuilder.append(", ");
        }
        return stringBuilder.append(" tail").toString();
    }
 
}

4. 使用链表实现一个队列

/**
 * 使用链表实现的队列
 */
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);
        }
 
        @Override
        public String toString() {
            return e.toString();
        }
    }
 
 
    // 定义队列需要的参数
    private Node head, tail;
    private int size;
 
    public LinkedListQueue(){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
 
 
 
    @Override
    public int getSize() {
        return this.size;
    }
 
    public boolean isEmpty(){
        return this.size == 0;
    }
 
 
    @Override
    public int getCapacity() {
        return 0;
    }
 
 
    /**
     *  入队
     * @param value
     */
    @Override
    public void enqueue(E value) {
        // 入队从尾部开始
        if (tail == null){
            // 1. 如果此时没有元素的话
            tail = new Node(value);
            head = tail;
        }
        else {
             // 2. 如果已经存在了元素，那么队列尾部肯定是不为空的，而是指向了一个空节点
            tail.next = new Node(value);
            // 移动尾节点
            tail = tail.next;
        }
        size++;
    }
 
 
    /**
     * 出队
     * @return
     */
    @Override
    public E dequeue() {
        if (isEmpty())
            throw new IllegalArgumentException("Empty queue cannot dequeue!");
        // 1. 存储出队的元素
        Node retNode = head;
        // 2.head节点下移动
        head = head.next;
        // 3.删除原来的头节点
        retNode.next = null;        // 实际上删除的是这个节点的数据域
 
 
        // 如果删除了最后一个元素之后
        if (head == null)
            tail = null;
 
        size--;
        return retNode.e;
    }
 
    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Empty queue cannot dequeue!");
        return head.e;
    }
 
 
 
    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        Node cur = head;
        stringBuilder.append("head:");
        //  1.  第一种循环遍历的方式,  注意这里判断的是每一次的cur是否为空， 而不是判断cur.next， 否则第一个元素是不能打印输出的
        while (cur != null) {
            stringBuilder.append(cur + "->");
            // 继续向后移动节点
            cur = cur.next;
        }
        stringBuilder.append("NULL tail");
        return stringBuilder.toString();
    }
}

5. 使用一个带有虚拟头结点的链表实现一个队列

/**
 * 带有虚拟头结点的链表实现的队列
 */
public class DummyHeadLinkedListQueue<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);
        }
 
        @Override
        public String toString() {
            return e.toString();
        }
    }
    // 定义一个虚拟头结点
    private Node dummyHead, tail;
    private int size;
 
    public DummyHeadLinkedListQueue(){
        this.dummyHead = new Node(null, null);
        this.tail = null;
        this.size = 0;
    }
 
    @Override
    public int getSize() {
        return this.size;
    }
 
    public Boolean isEmpty(){
        return this.size == 0;
    }
 
    @Override
    public int getCapacity() {
        throw new IllegalArgumentException("LinkedList cannot getCapacity!");
    }
 
    @Override
    public void enqueue(E value) {
        //  开始入队列(从队列的尾部进行入队列)
        // 1. 构造插入的节点
        Node node  = new Node(value);
        // 2. 尾部插入节点        //bug : 由于默认的时候 tail为null，此时如果直接访问tail.next 是错误的
        if (tail == null) {
            dummyHead.next = node;
            // 说明此时队列为空的
            tail = node;
        } else {
            tail.next = node;
            // 3. 尾部节点向后移动
            tail = tail.next;
        }
        // 4. 队列长度增加
        size++;
 
    }
 
 
    @Override
    public E dequeue() {
        // 元素出队列从链表的头部出去
        // 1. 获取头结点的位置
        Node head = dummyHead.next;
        // 缓存出队的元素
        Node retNode = head;
        // 2. 移动节点
        dummyHead.next = head.next;
        // 4. 更新容量
        size--;
 
        head = null;
        if (isEmpty())
            tail = null;            // bug修复
 
        return (E) retNode;
    }
 
 
    @Override
    public E getFront() {
        return null;
    }
 
 
    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("Queue head:");
        Node cur = dummyHead.next;
        while (cur != null){
            stringBuilder.append(cur + "->");
            cur = cur.next;
        }
        return stringBuilder.append("null tail").toString();
    }
}

　　

以上就是创建队列实现的5中方式，每种方式都有各自的特点，就做个简单总结吧！　　

队列的时间复杂度分析：

　

+ 队列Queue[数组队列]
    void enqueue(E)     O(1)   均摊复杂度
    E dequeue()         O(n)   移出队列首部的元素，需要其他元素向前补齐
    E getFront()        O(1)   
    void dequeue()      O(1)
    Int getSize()       O(1)
    bool isEmpty()      O(1)
+ 循环队列
     void enqueue(E)     O(1)   均摊复杂度
    E dequeue()         O(1)   
    E getFront()        O(1)   
    void dequeue()      O(1)
    Int getSize()       O(1)
    bool isEmpty()      O(1)

以上就是对于队列实现的几种方式的总结了。