手写数据结构-基于动态数组的循环队列

1.循环队列

在基于动态数组的队列中我们发现，在移出队首元素时时间复杂度为O(n)，为了解决这个问题，我们引出了循环队列。

实现原理：双指针，多维护一个指针指向队首，当队首元素移出时，基于数组实现的队列中的元素不需要全部向前移动一个位置，只需要指向下一个元素。

2.手动实现基于动态数组的循环队列及复杂度分析（和基于动态数组的普通队列对比）

package com.tc.javabase.datastructure.array.queue;

import com.tc.javabase.datastructure.queue.Queue;

/**
 * @Classname LoopQueue
 * @Description 基于静态数组的循环队列
 *
 *   采用头指针和尾指针的方式实现基于静态数组的循环队列
 *   当队列为空时 和 队列满时 front = tail ，通过size == 0 区别两种情况
 *
 * 时间复杂度分析：
 *  入队：O(1)
 *  出队：O(1)
 *  查询队首元素:O(1)
 *
 *   对比： 在和基于动态数组实现的队列，在10w条数据入队出队的测试下
 *      基于动态数组实现的队列耗时：9s
 *      循环队列：0.06
 *
 *       所以循环队列性能优于基于动态数组实现的队列
 *
 * @Date 2020/7/17 09:39
 * @Created by zhangtianci
 */
public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int size;
    private int front;  //  指向队首的地址
    private int tail;    // 指向下一个元素存放的地址

    /**
     * 默认队列的容量为8
     */
    public LoopQueue() {
        this.data = (E[])new Object[8];
        size = 0;
        front = 0;
        tail = 0;
    }

    /**
     * @param capacity 初始化队列的容量
     */
    public LoopQueue(int capacity){
        this.data = (E[])new Object[capacity];
        size = 0;
        front = 0;
        tail = 0;
    }

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

    @Override
    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    /**
     *   入队
     *
     *   时间复杂度分析：O(1)
     *   即使在扩容的时候，入队n+1个元素，会有2n+1次操作，平均一个入队元素为2次操作，
     *   所以均摊复杂度也为O(1)
     * @param e
     */
    @Override
    public void enqueue(E e) {
        //考虑边界情况
        //1。队列的容量满了 扩容
        if (size == data.length){
            resize(data.length * 2);
        }

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

    /**
     *  扩容/缩容
     * @param capacity
     */
    private void resize(int capacity){
        E[] newdata = (E[])new Object[capacity];
        for (int i = 0;i < size;i++){
            newdata[i] = data[(front + i) % data.length];
        }

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

    /**
     * 出队
     * 时间复杂度分析：O(1)
     *
     * @return
     */
    @Override
    public E dequeue() {
        //考虑边界情况
        //队列为空 不能出队
        if (isEmpty()){
            throw new IllegalArgumentException("队列为空 不能出队！");
        }

        E e = 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 e;
    }

    /**
     * 获取队首元素
     *
     * 时间复杂度分析：O(1)
     * @return
     */
    @Override
    public E getFront() {
        return data[front];
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d
", size,data.length));
        res.append("front = " + front + " [");

        for (int i = 0;i < size;i++){
            res.append(data[(front + i) % data.length]);
            if ((front + i + 1) % data.length != tail){
                res.append(", ");
            }
        }
        res.append("] " +  "tail=" + tail);
        return res.toString();
    }

    public static void main(String[] args) {

        LoopQueue<Integer> queue = new LoopQueue<>();
        for(int i = 0 ; i < 100 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}