How to implement a circular queue in java

1. What are the problems with ordinary queues?

Everyone knows that the queue has several important attributes:

• rear: points to the tail of the queue, that is, the position of the last element, the initial value It is -1

• front: points to the previous position of the head of the queue, and the initial value is also -1

• capacity: the capacity of the queue

The rear and front of an empty queue are both equal to -1. When joining the queue, the front does not move and rear. When rear == capacity - 1, the queue has Full; when dequeuing, rear does not move, front, when front == rear, the queue is empty. It looks perfect, but there's actually something wrong with it. If a queue capacity = 3, three elements are enqueued, then front = -1; rear = 2, and then all three elements are dequeued, at this timefront = 2, rear = 2. At this time, the queue is obviously empty, but no more elements can be added to the queue, because rear = capacity - 1 is satisfied, which means that the queue is one-time and cannot be used again after it is used. , even if it is empty, it cannot be added to the queue, causing a waste of space, so the circular queue appears.

2. Ring queue implementation ideas:

Several important attributes in the ring queue:

• rear: points to the queue The position after the tail, the initial value is 0

• front: points to the head of the queue, that is, the position of the first element, the initial value is 0

• capacity: the capacity of the queue

The following are some algorithms for ring queues:

• When the queue is empty: front == rear

• When the queue is full: (rear 1) % capacity == front

• Get the number of queue elements: (rear capacity - front) % capacity

• When joining the queue: rear = (rear 1) % capacity

• When dequeuing: front = (front 1) % capacity;

Determining whether the queue is full is the most important and difficult to understand part of the ring queue. If there is a queue capacity = 3, the enqueue operation is as follows:

• The first element is enqueued: ​ front = 0, because (rear 1) % capacity = 1 % 3 != front, so the element can be enqueued. After the element is enqueued rear = 1；

• The second element is added to the queue: ​ front = 0, because (rear 1) % capacity = 2 % 3 != front, so the element can be enqueued. After the element is enqueued rear = 2；

• The third element is added to the queue: ​ front = 0, because (rear 1) % capacity = 3 % 3 == front, so the element cannot be added to the queue, and the queue is full;

The queue capacity is obviously 3, and only the queue can be added. Tell me that the queue is full after queuing two elements? Yes, this algorithm for determining whether the queue is full requires sacrificing a space in the array.

Now perform the dequeue operation:

• The first element is dequeued: ​ front = 1, ​ rear = 2， ​ (rear 1) % capacity = 3 % 3 = 0 != front.

It can be found that when an element is dequeued, it meets the conditions for entering the queue, so the array space can be reused.

3. Code practice:

<code>public class CircleQueue<E> {<br>    private int capacity;<br>    private int front;<br>    private int rear;<br>    private Object[] arr;<br><br>    public CircleQueue(int capacity){<br>        this.capacity = capacity;<br>        this.arr = new Object[capacity];<br>        this.front = 0;<br>        this.rear = 0;<br>    }<br><br>    public boolean isFull(){<br>        return (rear + 1) % capacity == front;<br>    }<br><br>    public boolean isEmpty(){<br>        return rear == front;<br>    }<br><br>    public void addQueue(E e){<br>        if (isFull()){<br>            throw new RuntimeException("队列已满，入队失败");<br>        }<br>        arr[rear] = e;<br>        // rear指针后移<br>        rear = (rear + 1) % capacity;<br>    }<br><br>    public E getQueue(){<br>        if (isEmpty()){<br>            throw new RuntimeException("队列为空，出队失败");<br>        }<br>        E val = (E) arr[front];<br>        front = (front + 1) % capacity;<br>        return val;<br>    }<br><br><br>    public int getSize(){<br>        return (rear + capacity - front) % capacity;<br>    }<br><br>    // 遍历<br>    public void showQueue(){<br>        if (isEmpty()){<br>            return;<br>        }<br>        for (int i = front; i < front + getSize(); i++) {<br/>            System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);<br/>        }<br/>    }<br/><br/>    public static void main(String[] args){<br/>        CircleQueue<Integer> queue = new CircleQueue<>(3);<br>        queue.addQueue(1);<br>        queue.addQueue(2);<br>        queue.showQueue();<br>        //queue.addQueue(3);<br>        System.out.println(queue.getSize());<br>        System.out.println(queue.getQueue());;<br>        queue.addQueue(3);<br>        queue.showQueue();<br>    }<br>}</code>

The above is the detailed content of How to implement a circular queue in java. For more information, please follow other related articles on the PHP Chinese website!