玩转数据结构（八）循环队列

我不是女神ヾ 2022-05-21 08:40 171阅读 0赞

### 1、为什么要循环队列？ ###

可以看看这篇文章：[静态队列为什么必须是循环队列][Link 1]

### 2、循环队列要点 ###

![70][]

判空队列为空的条件：head == tail

判断队列已满的条件： (head + 1) % 数组长度 == tail

入队后维护tail:  tail = (tail + 1） % 数组长度

出队后维护front:  front = (front + 1） % 数组长度

***注意：需要浪费一个空间来区分判空和盘满的条件***

### 3、队列接口 ###

public interface Queue<E> {
        int getSize();
        void enqueue(E e);
        E dequeue();
        E getFront();
        boolean isEmpty();
    }

### 4、实现代码 ###

/**
     * 循环队列:
     *  判满：(tail+1) % length == front
     *  判空：tail == front
     * @param <E> 泛型
     */
    public class LoopQueue<E> implements Queue<E> {
        private E[] data;//存储数据的数组
        private int front;//尾指针
        private int tail;//头指针
        private int size;//计数
    
        //构造方法
        public LoopQueue() {
            this(10);
        }
    
        public LoopQueue(int capacity) {
            data = (E[])new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        @Override
        public int getSize() {
            return size;
        }
    
        public int getCapacity() {
            return data.length - 1;//需要浪费一个空间，以此来区分判空和判满的条件
        }
    
        @Override
        public void enqueue(E e) {
            //扩容
            if((tail + 1) % data.length == front) {
                resize(getCapacity() * 2);
            }
            //入队操作
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size++;
        }
    
        @Override
        public E dequeue() {
            if(isEmpty()) {
                throw new IllegalArgumentException("Queue is empty! cannot dequeue from an empty queue!");
            }
    
            E res = data[front];
            data[front] = null;
            front = (front + 1) % data.length;
            size--;
    
            //缩容
            if(size == getCapacity() / 4 && getCapacity() / 2 != 0) {
                resize(getCapacity() / 2);
            }
            return res;
        }
    
        /**
         * 扩容
         * @param newCapacity
         */
        private void resize(int newCapacity) {
            E[] newData = (E[])new Object[newCapacity + 1];
            for (int i = 0; i < size; i++) {
                newData[i] = data[(i + front) % data.length];
            }
    
            data = newData;
            front = 0;
            tail = size;
        }
    
        @Override
        public E getFront() {
            if(isEmpty()) {
                throw new IllegalArgumentException("Queue is empty!");
            }
    
            return data[front];
        }
    
        @Override
        public boolean isEmpty() {
            return tail == front;
        }
    
        @Override
        public String toString() {
            StringBuilder str = new StringBuilder();
            str.append(String.format("LoopQueue: size=%d, capacity=%d ", size, getCapacity()));
            str.append("front [");
            for(int i = front; i != tail; i = (i + 1) % data.length) {
                str.append(data[i]);
                if((i + 1) % data.length != tail) {
                    str.append(",");
                }
            }
            str.append("] tail");
    
            return str.toString();
        }
    }

### 5、测试代码 ###

public static void main(String[] args) {
            LoopQueue<Integer> loopQueue = new LoopQueue<Integer>();
            for (int i = 0; i < 10; i++) {
                loopQueue.enqueue(i);
                System.out.println(loopQueue);
    
                if(i % 3 == 2) {
                    loopQueue.dequeue();
                    System.out.println(loopQueue);
                }
            }
        }

### 6、结果 ###

LoopQueue: size=1, capacity=10 front [0] tail
    LoopQueue: size=2, capacity=10 front [0,1] tail
    LoopQueue: size=3, capacity=10 front [0,1,2] tail
    LoopQueue: size=2, capacity=5 front [1,2] tail
    LoopQueue: size=3, capacity=5 front [1,2,3] tail
    LoopQueue: size=4, capacity=5 front [1,2,3,4] tail
    LoopQueue: size=5, capacity=5 front [1,2,3,4,5] tail
    LoopQueue: size=4, capacity=5 front [2,3,4,5] tail
    LoopQueue: size=5, capacity=5 front [2,3,4,5,6] tail
    LoopQueue: size=6, capacity=10 front [2,3,4,5,6,7] tail
    LoopQueue: size=7, capacity=10 front [2,3,4,5,6,7,8] tail
    LoopQueue: size=6, capacity=10 front [3,4,5,6,7,8] tail
    LoopQueue: size=7, capacity=10 front [3,4,5,6,7,8,9] tail

### 6、时间复杂度分析 ###

入队时直接将数据放入tail所指向的索引处，因此时间复杂度O（1）

出队时直接从front索引的空间取数据，因此时间复杂度也是O（1）

[Link 1]: https://blog.csdn.net/qq_33804730/article/details/79062454
[70]: /images/20220521/825cc8c16db64b3abc54bc3cfc09f802.png