Introduction to Java circular queue (code example)

This article brings you an introduction to Java circular queues (code examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. .

In order to solve the problems caused by array queues, this article introduces circular queues to you.

Idea Analysis Illustration

It’s a bit long, because the author is not very good at making the posted pictures have animation effects, such as moving or deleting elements (after all This is more intuitive for everyone). Here, the author can only use static pictures to help you understand the implementation principle. I hope you won’t be offended. If anyone knows how to do it, please share your wisdom in the comment area.

Here, we declare an array with a capacity of 8 and mark the indexes 0-7, and then use front and tail respectively To represent the queue, the head and tail of the queue; in the figure below, the positions of front and tail initially point to the position of index 0, which means that when When front == tai<font color="red"></font>the queue is empty Everyone must keep this in mind in order to distinguish the queues introduced later Critical conditions when almost full

In order for everyone to better understand the following content, here, I will briefly explain it

front: Represents the head of the queue, always pointing to the first element in the queue (when the queue is empty, front points to the position with index 0)

tail: Indicates the tail of the queue, always pointing to the next position of the last element in the queue

The element is added to the queue, the position of tail is maintained, and the tail operation

Elements are dequeued, maintain the position of front, and perform front operations. As mentioned above, elements can be enqueued and dequeued in a simple manner. Maintaining the positions of tail and front is actually not rigorous. The correct position of maintaining tail should be (tail 1) % capacity. Similarly, the position of front should be (front 1 ) % capacity, which is why it is called a circular queue. Let’s know it here first. It doesn’t matter if you don’t understand it yet. I believe you will know it later.

Let’s take a look. Now if an element a joins the team, the current diagram:

We now see that element a joins the team, our The position pointed by tail has changed and the operation has been performed, but the position of front has not changed and still points to the position with index 0. Remember what the author said above, the position of front always points to the first element in the queue. , the position of the tail always points to the next position of the last element in the queue

Now, let’s add a few more elements b, c, d, and e to the queue. Let’s take a look at the Schematic diagram:

I believe everyone knows that the schematic diagram looks like this, and there doesn’t seem to be too many changes (please don’t worry, the author is here to help everyone understand what it is) What a circular queue, please forgive me O(∩_∩)O ha!)

After reading the operation of elements entering the queue, let’s take a look now, the operation of dequeuing elements is how is it like?

Element a is dequeued. The schematic diagram is as follows:

Now element a has been dequeued, and the position of front points to the index. is the position of 1, now all the elements in the array no longer need to move forward one position

This is consistent with our array queue (our array queue requires elements to be dequeued, and subsequent elements must be moved forward (one position) is completely different. We only need to change the direction of front. From the previous O(n) operation, it becomes an O(1) operation.

We perform element b again Dequeue, the schematic diagram is as follows:

At this point, some friends may ask, why is it called a circular queue? So now let’s try it. We let elements f and g enter the queue respectively. The diagram at this time is as follows:

There is still no change after visual inspection. If at this time, we let another element h element be added to the queue, then the question arises: how should the position of our tail be pointed? The schematic diagram is as follows:

According to what we said before, the elements are enqueued: maintain the position of the tail and perform the tail operation. At this time, our tail has pointed to the position with index 7. If we now It is obviously impossible to operate tail (array out of bounds)

Careful friends will find that our queue is not full at this time, and there are two positions left (this is because after our element is dequeued, the current space, not squeezed out by subsequent elements), you can imagine our array as a ring, then the position after index 7 is index 0

How can we calculate from the position of index 7 to index 0 position, we have been talking about tail operations before. The author also pointed out at the beginning that this is not rigorous. It should be (tail 1) % capacity, so it becomes (7 1) % 8 equals 0

So if we let element h join the queue at this time, then our tail will point to the position with index 0. The diagram is as follows:

Assumption Now that a new element k has been added to the queue, the position of tail is equal to (tail 1) % capacity, which is (0 1) % 8. If it is equal to 1, it points to the position with index 1

Then the question is, can our circular queue still enqueue elements? Let's analyze it. The picture shows that we still have an empty space position with index 0, which is the position pointed by tail at this time.

According to the previous logic, assume that a new element can be put in now , our tail performs (tail 1) % capacity calculation and the result is 2 (if the element is successfully added to the queue, the queue is full at this time), at this time we will find that the front representing the head of the queue also points to the position with index 2

If the new element is successfully added to the queue, our tail is also equal to 2, then it becomes tail == front. At the beginning, we mentioned that when the queue is empty, tail == front, now, If tail is equal to front when the queue is full, then we cannot distinguish between collection when the queue is full and collection when the queue is empty.

So, in the circular queue, we always waste a space, to Distinguish between the situation when the queue is full and the situation when the queue is empty, that is, when (tail 1) % capacity == front, it means that the queue is full, and when front == tail, it means that the queue is empty.

#After understanding the implementation principle of circular queue, let’s implement it with code.

Code implementation

Interface definition: Queue

public interface Queue<e> {
    /**
     * 入队
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出队
     *
     * @return
     */
    E dequeue();

    /**
     * 获取队首元素
     *
     * @return
     */
    E getFront();

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

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty();
}</e>

Interface implementation: LoopQueue

public class LoopQueue<e> implements Queue<e> {
    /**
     * 承载队列元素的数组
     */
    private E[] data;
    /**
     * 队首的位置
     */
    private int front;
    /**
     * 队尾的位置
     */
    private int tail;
    /**
     * 队列中元素的个数
     */
    private int size;

    /**
     * 指定容量，初始化队列大小
     * (由于循环队列需要浪费一个空间，所以我们初始化队列的时候，要将用户传入的容量加1)
     *
     * @param capacity
     */
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
    }

    /**
     * 模式容量，初始化队列大小
     */
    public LoopQueue() {
        this(10);
    }


    @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("队列为空");
        }
        // 出队元素
        E element = data[front];
        // 元素出队后，将空间置为null
        data[front] = null;
        // 维护front的索引位置(循环队列)
        front = (front + 1) % data.length;
        // 维护size大小
        size--;

        // 元素出队后，可以指定条件，进行缩容
        if (size == getCapacity() / 2 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return element;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

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

    @Override
    public boolean isEmpty() {
        return front == tail;
    }


    // 队列快满时，队列扩容；元素出队操作，指定条件可以进行缩容
    private void resize(int newCapacity) {
        // 这里的加1还是因为循环队列我们在实际使用的过程中要浪费一个空间
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i <p>Test class: LoopQueueTest</p>
<pre class="brush:php;toolbar:false">public class LoopQueueTest {
    @Test
    public void testLoopQueue() {
        LoopQueue<integer> loopQueue = new LoopQueue();
        for (int i = 0; i <h5>Test results: </h5>
<pre class="brush:php;toolbar:false">原始队列: LoopQueue{【队首】data=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=0, tail=10, size=10, capacity=10}
元素0出队: LoopQueue{【队首】data=[null, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=1, tail=10, size=9, capacity=10}
元素1出队: LoopQueue{【队首】data=[null, null, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=2, tail=10, size=8, capacity=10}
元素2出队: LoopQueue{【队首】data=[null, null, null, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=3, tail=10, size=7, capacity=10}
元素3出队: LoopQueue{【队首】data=[null, null, null, null, 4, 5, 6, 7, 8, 9, null]【队尾】, front=4, tail=10, size=6, capacity=10}
元素4出队,发生缩容: LoopQueue{【队首】data=[5, 6, 7, 8, 9, null]【队尾】, front=0, tail=5, size=5, capacity=5}
队首元素：5

Full version code GitHub warehouse address: Java version data structure-queue (circular queue)

This article ends here It’s all over. For more exciting content, you can pay attention to the Java Video Tutorial column on the PHP Chinese website!

The above is the detailed content of Introduction to Java circular queue (code example). For more information, please follow other related articles on the PHP Chinese website!