12-循环队列

package com.weyan.circle;
@SuppressWarnings("unchecked")

public class CircleQueue<E> {
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    
    public CircleQueue() {
        elements = (E[])new Object[DEFAULT_CAPACITY];
    }
    
    //元素个数
        public int size() {
            return size;
        }
        //队列是否为空
        public boolean isEmpty() {
            return size == 0;
        }
        //入队
        public void enQueue(E element) {
            elements[(front + size) % elements.length] = element;
            size ++;
        }
        //出队
        public E deQueue() {
            E frontElement = elements[front];
            elements[front] = null;
            front = (front + 1) % elements.length;
            size --;
            return frontElement;
        }
        //队头元素
        public E front() {
            return elements[front];
        }
        
        @Override
        public String toString() {
            // TODO Auto-generated method stub
            StringBuilder string = new StringBuilder();
            string.append("capacity=").append(elements.length)
            .append(",size=").append(size).append(",[");
            for (int i = 0; i < elements.length; i++) {
                if (i != 0) {
                    string.append(", ");
                }
                string.append(elements[i]);
            }
            string.append("]");
            return string.toString();
        }
}

验证结果：

//测试循环队列
    static void test2() {
        CircleQueue<Integer> queue = new CircleQueue<Integer>();
        //0 1 2 3 4 5 6 7 8 9
        for (int i = 0; i < 10; i++) {
            queue.enQueue(i);
        }
        
        //null null null null null 5 6 7 8 9
        for (int i = 0; i < 5; i++) {
            queue.deQueue();
        }
        //15 16 17 18 null 5 6 7 8 9
        for (int i = 15; i < 19; i++) {
            queue.enQueue(i);
        }
        System.out.println(queue);
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueue());
        }
    }

验证结果

循环队列动态扩容

package com.weyan.circle;
@SuppressWarnings("unchecked")

public class CircleQueue<E> {
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    
    public CircleQueue() {
        elements = (E[])new Object[DEFAULT_CAPACITY];
    }
    
    //元素个数
        public int size() {
            return size;
        }
        //队列是否为空
        public boolean isEmpty() {
            return size == 0;
        }
        //入队
        public void enQueue(E element) {
            ensureCapacity(size + 1);
            elements[(front + size) % elements.length] = element;
            size ++;
        }
        //出队
        public E deQueue() {
            E frontElement = elements[front];
            elements[front] = null;
            front = (front + 1) % elements.length;
            size --;
            return frontElement;
        }
        //队头元素
        public E front() {
            return elements[front];
        }
        
        /**
         * 保证要有capacity的容量
         * @param capacity
         */
        private void ensureCapacity(int capacity) {
            int oldCapacity = elements.length;
            if (oldCapacity >= capacity) return;
            
            // 新容量为旧容量的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[(i+front) % elements.length];
            }
            elements = newElements;
            //重置front
            front = 0;
            System.out.println(oldCapacity + "扩容为" + newCapacity);
        }
        
        @Override
        public String toString() {
            // TODO Auto-generated method stub
            StringBuilder string = new StringBuilder();
            string.append("capacity=").append(elements.length)
            .append(",size=").append(size).append(",front=").append(front).append(",[");
            for (int i = 0; i < elements.length; i++) {
                if (i != 0) {
                    string.append(", ");
                }
                string.append(elements[i]);
            }
            string.append("]");
            return string.toString();
        }
}

验证结果：

//测试循环队列
    static void test2() {
        CircleQueue<Integer> queue = new CircleQueue<Integer>();
        //0 1 2 3 4 5 6 7 8 9
        for (int i = 0; i < 10; i++) {
            queue.enQueue(i);
        }
        
        //null null null null null 5 6 7 8 9
        for (int i = 0; i < 5; i++) {
            queue.deQueue();
        }
        //15 16 17 18 null 5 6 7 8 9
        for (int i = 15; i < 23; i++) {
            queue.enQueue(i);
        }
        System.out.println(queue);
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueue());
        }
    }
-----------------------------------------------------------------------------------------------------------
10扩容为15
capacity=15,size=13,front=0,[5, 6, 7, 8, 9, 15, 16, 17, 18, 19, 20, 21, 22, null, null]
5
6
7
8
9
15
16
17
18
19
20
21
22