Java implements circular queue

Advantages of circular queue

Ordinary queue dequeuing operations are expensive: during dequeuing operations, all elements after index 0 , all need to be moved forward by one position. The more elements there are, the more time is consumed, and the time complexity is O(N).

The logic of the circular queue:

1. When there are few elements (the tail position is behind the front), the circular queue has the same queuing operation as a normal queue. The element of the queue will be placed at the tail position, and then the tail operation will be performed; when the element is dequeued, the element at the front position will be set to null, and then the front operation will be performed; at this time, the tail position can still be maintained behind the front, as follows As shown in the figure:

#2. When elements continue to be added, the last element will be placed at index 7. At this time, the tail position will move to the index in front of the head of the queue. At the position of 0, the index of tail in the array becomes: (tail 1)% capacity as shown in the figure below:

3. When elements continue to be added , the element will be added at the tail position, and the tail will continue to move backward, as shown in the following figure:

#4. Continue to add elements when the tail and front are still one unit apart. At this time, that is, there is still a free storage space in the array, but the current array can no longer implement the insertion operation of the circular queue, because the condition for the circular queue to judge that the queue is empty is front == tail, so expansion operation is required at this time; So there is a conscious waste of space here.

It can be deduced here that the condition for the circular queue element to be full is: tail 1 == front (preliminary conclusion, it will be improved to (tail 1) % capacity == front)

5 . Under appropriate circumstances, if the dequeue operation continues, the position of front will also jump from the right end of the array to the left end of the array. At this time, the index of front in the array becomes: (front 1)% capacity

Code implementation: (Related video tutorial sharing: java video tutorial)

package dataStructure.chapter3;

/**
 * @Author: zjtMeng
 * @Date: 2019/12/28 20:13
 * @Version 1.0
 */
public class LoopQueue<E> implements Queue<E> {

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

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

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    /**
     * 循环队列入队操作
     * @param e
     */
    @Override
    public void enqueue(E e) {
        //循环队列元素满的判断条件,如果满了就进行扩容操作，扩大两倍
        if ((tail+1)%data.length == front)
            resize(2 * getCapacity());
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;

    }

    /**
     * 循环队列扩容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity+1];
        //循环队列第一种遍历方式
        for (int i = 0 ; i < size ; i++ ){
//newData[]中的元素与data[]中的元素，一方面存在着front的偏移量，另一方面，data[]中的元素，
//可能在有部分处于front前面，因此此处采用对数组长度取余，来判断元素的位置
            newData[i] = data[(i+front)%data.length];
        }
        data = newData;
        front =0;
        tail = size;

    }

    @Override
    public E dequeue() {
        //首先判断队列是否为空，如果为空则抛出异常
        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        E ret = data[front];
        //引用地址需要置空，否则JVM不能及时回收空间，从而可能会出现OOM异常
        data[front] = null;
        front = (front + 1 )% data.length;
        size--;
        //如果元素数量达到队列容积的1/4，且队列容积/2 不等于0时，进行缩容操作
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0 )
            resize(getCapacity() / 2);
        return ret;
    }

    /**
     * 查看队首元素
     * @return
     */
    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

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

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: 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 + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

Recommended related articles and tutorials: java introductory tutorial

The above is the detailed content of Java implements circular queue. For more information, please follow other related articles on the PHP Chinese website!