Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about how to achieve the circular queue in java. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article. Let's take a look at it.

1. What is the problem with the ordinary queue?

As you know about the queue, there are several important attributes:

Rear: points to the tail of the queue, that is, the location of the last element. The initial value is-1front: points to the previous position of the queue header, and the initial value is also-1capacity: the capacity of the queue.

The rear and front of the empty queue are both equal to-1. When you join the queue, front does not move, rear++, when rear = = capacity-1, the queue is full; when you leave the queue, rear does not move; front++, when front = = rear, the queue is empty. It looks perfect, but there's something wrong with it. If a queue capacity = 3, there are three elements in the queue, then front =-1; rear = 2, and then all three elements are dequeued, front = 2, rear = 2. At this time, the queue is obviously empty, but it can no longer join the queue element, because the queue is satisfied with rear = capacity-1, that is, the queue is one-time, and it can no longer be used after use, even if it is empty, resulting in a waste of space, so the circular queue appears.

2. The realization idea of ring queue:

Several important attributes in the ring queue:

Rear: points to the last position of the tail of the queue. The initial value is 0front: points to the head of the queue, where the first element is located, and the initial value is 0capacity: the capacity of the queue.

Here are some algorithms for ring queues:

When the queue is empty: front = = rear queue is full: (rear + 1)% capacity = = front get the number of queue elements: (rear + capacity-front)% capacity: rear = (rear + 1)% capacity when dequeuing: front = (front + 1)% capacity

Determining whether the queue is full is the most important and difficult part of the circular queue. If there is a queue with capacity = 3, the queuing operation is as follows:

The first element joins the team: front = 0, because (rear + 1)% capacity = 1% 3! = front, so the element can join the team, rear = 1; the second element joins the team: front = 0, because (rear + 1)% capacity = 2% 3! = front, so the element can join the team, and rear = 2 after joining the team The third element joins the queue: front = 0, because (rear + 1)% capacity = 3% 3 = = front, so the element cannot join the queue, the queue is full

The queue capacity is obviously 3, only two elements in the queue to tell me that the queue is full? Yes, this algorithm to determine whether the queue is full or not requires sacrificing a space in the array.

Now go out of the team:

The first element comes out: front = 1, rear = 2, (rear + 1)% capacity = 3% 3 = 0! = front.

It can be found that when an element is out of the queue, the conditions for joining the queue are met, so the array space can be reused.

3. Code practice:

Public class CircleQueue {

Private int capacity

Private int front

Private int rear

Private Object [] arr

Public CircleQueue (int capacity) {

This.capacity = capacity

This.arr = new Object [capacity]

This.front = 0

This.rear = 0

}

Public boolean isFull () {

Return (rear + 1)% capacity = = front

}

Public boolean isEmpty () {

Return rear = = front

}

Public void addQueue (E e) {

If (isFull ()) {

Throw new RuntimeException ("queue full, failed to join the queue")

}

Arr [rear] = e

/ / rear pointer moves backward

Rear = (rear + 1)% capacity

}

Public E getQueue () {

If (isEmpty ()) {

Throw new RuntimeException ("queue is empty, dequeue failed")

}

Eval = (E) arr [front]

Front = (front + 1)% capacity

Return val

}

Public int getSize () {

Return (rear + capacity-front)% capacity

}

/ / traversing

Public void showQueue () {

If (isEmpty ()) {

Return

}

For (int I = front; I < front + getSize ()) {

System.out.printf ("arr [% d] =% d\ n", i%capacity, arr [i%capacity])

}

}

Public static void main (String [] args) {

CircleQueue queue = new CircleQueue (3)

Queue.addQueue (1)

Queue.addQueue (2)

Queue.showQueue ()

/ / queue.addQueue (3)

System.out.println (queue.getSize ())

System.out.println (queue.getQueue ())

Queue.addQueue (3)

Queue.showQueue ()

}

} these are all the contents of the article "how to realize the Ring queue in java". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.