1 基本原理

  • 基于动态数组实现，包含头指针front，尾指针tail；
  • 当 front == tail 代表队列为空
  • 当 (tail + 1) % data.length == front 代表队列为满

2 构造方法

  1. public class LoopQueue<E> {
  3.     private E[] data;
  4.     private int front, tail;
  5.     private int size;
  7.     public LoopQueue(int capacity) {
  8.         data = (E[]) new Object[capacity + 1]; // 因为需要浪费一个空间
  9.         front = 0;
  10.         tail = 0;
  11.         size = 0;
  12.     }
  14.     public LoopQueue() {
  15.         this(10);
  16.     }
  17. }

3 基本方法

  1. /**
  2. * 获取队列的容量
  3. *
  4. * @return
  5. */
  6. public int getCapacity() {
  7.     return data.length - 1;
  8. }
  10. /**
  11. * 队列是否为空
  12. *
  13. * @return
  14. */
  15. public boolean isEmpty() {
  16.     return front == tail;
  17. }
  19. /**
  20. * 获取队列中元素的个数
  21. *
  22. * @return
  23. */
  24. public int getSize() {
  25.     return size;
  26. }

4 扩容方法

  • 新建数组，容量为原来的2倍；
  • 将数据依次复制到新数组，并将原数组的引用指向新的数组
  • 初始化front与tail指针
  1. private void resize(int newCapacity) {
  2.     E[] newData = (E[]) new Object[newCapacity + 1];
  3.     for (int i = 0; i < size; i++) {
  4.         newData[i] = data[(i + front) % data.length];
  5.     }
  6.     data = newData;
  7.     front = 0;
  8.     tail = size;
  9. }

5 入队方法

  • 先判断是否需要扩容，如果需要，则扩容为原来的2倍
  • 添加元素，移动尾指针
  • size++
  1. public void enqueue(E e) {
  2.     if ((tail + 1) % data.length == front)
  3.         resize(getCapacity() * 2);
  5.     data[tail] = e;
  6.     tail = (tail + 1) % data.length;
  7.     size++;
  8. }

6 出队方法

  • 记录出队元素并返回
  • 移动头指针
  • 维护size
  • 判断是否需要缩容，当size变为容量的1/4时，缩容为原来的1/2，是为了防止抖动
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 == getCapacity() / 4 && getCapacity() / 2 != 0)
        resize(getCapacity() / 2);

    return ret;
}

7 完整代码

public class LoopQueue<E> {

    private E[] data;
    private int front, tail;
    private int size;

    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    /**
     * 获取队列的容量
     *
     * @return
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 获取队列中元素的个数
     *
     * @return
     */
    public int getSize() {
        return size;
    }

    public void enqueue(E e) {
        if ((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

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

    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 == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);

        return ret;
    }

    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 < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }
}

8 特点分析

  • 普通队列：如果不移动元素，则会出现假队列满的情况；如果移动元素，则需要消耗大量时间；
  • 循环队列：不用移动元素，而是移动头尾指针，高效并且不会出现假队列满的情况；但是需要浪费一个额外的空间。