循环队列：解决数组队列出队的时间复杂度

package com.dapeng.Queue;
/**
 * @author gdp
 * @date 2020/4/5 23:06
 */
public class LoopQueueimplements Queue {
    private E[] data;
    private int  front, tail; //数据首位   front==tail的时候空数组 但是也代表数组满了 所以我们设计为tail+1 为数组满了有意的浪费一个空间来做出区分
    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 boolean  isEmpty(){ return front == tail;}

    @Override
    public   int getSize(){ return size;}
    @Override
    public void enqueue(E e){
         //最后一个元素+1  取模
        if( (tail + 1) % data.length == front )
            resize(this.getCapacity() * 2 );

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

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

    @Override
    public E getFront(){
        if(isEmpty()) throw new IllegalArgumentException("  Queue is empty !.");
        return data[front];
    }

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

    @Override
    public String toString()
    {
        StringBuilder res   = new StringBuilder();
        res.append(String.format("Queen: size = %d, capacity = %d\n",size,getCapacity()));
        res.append("front [");
        for(int i = front; i != tail; i = (i+1) % data.length)
        {
            res.append(data[i]);
            if(i!=size-1)
                res.append(",");
        }
        res.append("]tail");
        return res.toString();
    }



    public static void main(String[] args) {
        LoopQueue queue = new LoopQueue();
        for(int i = 0 ; i  ){
            queue.enqueue(i);

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


}

package com.dapeng.Queue;
import java.util.Random;
/**
 * @author gdp
 * @date 2020/4/6 18:41
 */
public class queueTest {
   private static double test(Queue queue, int opCount){
       long startTime = System.nanoTime();
       Random random = new Random();
       for (int i = 0; i) queue.enqueue(random.nextInt(Integer.MAX_VALUE));
       for (int i = 0; i)  queue.dequeue();
       long endTime = System.nanoTime();

       return (endTime - startTime) / 100000000.0;
   }

    public static void main(String[] args) {
        int     opCount = 1000000;
        ArrayQueue arrayQueue = new ArrayQueue();
        double time1 = test(arrayQueue, opCount);
        System.out.println("ArrayQueue, time:" +time1+"  s");

        LoopQueue LoopQueue = new LoopQueue();
        double time2 = test(LoopQueue, opCount);
        System.out.println("LoopQueue, time:" +time2+"  s");
    }

}