JAVA从零开始实现数据结构七：循环队列

循环队列难点在于处理front与rear之间的大小关系，通过使用取余操作可以灵活处理出队、遍历
完整的MyCircularQueue类

import java.util.Arrays;

/**
 * Created by FireFlies on 2018/4/4.
 * 普通队列：底层使用数组实现
 * clearQueue(): 将队列清空。
 * isQueueEmpty(): 若队列为空， 返回true， 否则返回false。
 * getHead(): 若队列存在且非空， 用o返回队列的队头元素。
 * enQueue(Object o): 若队列存在， 插入新元素o到队列中并成为队尾元素
 * deQueue(): 删除队列中队头元素， 并用o返回其值。
 * queueLength(): 返回队列Q的元素个数
 */
public class MyCircularQueue {
    Object[] data = null;
    int capacity;
    int front;
    int rear;
    public MyCircularQueue(){this(10);}
    public MyCircularQueue(int initialSize){
        data = new Object[initialSize];
        capacity = initialSize;
        front = 0;
        rear = 0;
    }

    /**
     * 入队操作
     * 在数组最末尾插入元素
     */
    public boolean enQueue(Object o){
        ensureCapacity();
        data[rear++] = o;
        rear = (rear==capacity)? 0:rear; //若rear到头则转向
        return true;
    }

    /**
     * 出队操作
     * 读取对头元素
     */

    public Object deQueue(){
        if(this.isQueueEmpty()){
            throw new RuntimeException("empty queue");
        }
        Object temp = data[front];
        data[front++] = null;
        front = (front == capacity)?0:front;
        return temp;
    }

    /**
     * 清空队列
     */
    public void clearQueue(){
        Arrays.fill(data,null);
        rear = 0;
        front = 0;
    }

    /**
     * 判断队列是否为空
     */
    public boolean isQueueEmpty(){
        if(front==rear && data[front]==null)
            return true;
        return false;
    }

    /**
     * 获取队头元素
     */
    public Object getHead(){
        if(this.isQueueEmpty()){
            throw new RuntimeException("empty queue");
        }
        return data[front];
    }

    /**
     * 获取队列元素数目
     */
    public int queueLength(){
        if (this.isQueueEmpty())
            return 0;
        return rear>front?rear-front:capacity-(front-rear);
    }

    /**
     * 动态扩充容量
     */
    public void ensureCapacity(){
        if(rear == front && data[front]!=null){
            throw new RuntimeException("Queue is full!");
        }
    }

    /**
     * 验证index有效性
     */
    public void validate(int index){
        if(index<0||index>capacity){
            throw new RuntimeException("index error: "+index);
        }
    }

    /**
     * 打印队列全部元素
     */
    public void print(){
        System.out.print("[");
        for(int i=front; i<((rear>front)?rear:rear+capacity);i++){
            System.out.print(data[i%capacity].toString()+" ");
        }
        System.out.println("]");
    }

}

测试类

/**
 * Created by FireFlies on 2018/4/4.
 */
public class MyCircularQueueTest {
    public static void main(String[] args) {
        MyCircularQueue myCircularQueue = new MyCircularQueue(5);

        //测试入队操作
        System.out.println("测试入队操作：");
        System.out.println(myCircularQueue.isQueueEmpty());
        myCircularQueue.enQueue(new Integer(1));
        myCircularQueue.enQueue(new Integer(2));
        myCircularQueue.enQueue(new Integer(3));
        myCircularQueue.enQueue(new Integer(4));
        myCircularQueue.enQueue(new Integer(5));
        myCircularQueue.print();

        //测试读取队头
        System.out.println("Head: "+myCircularQueue.getHead());

        //测试出队操作
        System.out.println("测试出队操作：");
        myCircularQueue.deQueue();
        myCircularQueue.print();
        myCircularQueue.deQueue();
        myCircularQueue.print();
        myCircularQueue.deQueue();
        myCircularQueue.print();

        //再次测试入队
        System.out.println("再次测试入队操作：");
        myCircularQueue.enQueue(new Integer(6));
        myCircularQueue.enQueue(new Integer(7));
        myCircularQueue.enQueue(new Integer(8));
        myCircularQueue.print();

        //再次出队测试
        myCircularQueue.deQueue();
        myCircularQueue.print();
        myCircularQueue.deQueue();
        myCircularQueue.print();
        myCircularQueue.deQueue();
        myCircularQueue.print();

        //再再次入队测试
        System.out.println("再再次测试入队操作：");
        myCircularQueue.enQueue(new Integer(9));
        myCircularQueue.enQueue(new Integer(10));
        myCircularQueue.enQueue(new Integer(11));
        myCircularQueue.print();
    }
}

测试结果