Shulou(Shulou.com)06/02 Report--

This article mainly introduces "what is the implementation method of Java queue data structure". In daily operation, I believe that many people have doubts about the implementation of Java queue data structure. Xiaobian consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts of "what is the implementation method of Java queue data structure?" Next, please follow the editor to study!

1. The basic concept of queues

What is a queue?

Queue is a special linear table.

It only allows deletions at the front end of the table (line header).

Insert at the back end (end of the line) of the table

A queue is an ordered table (which can be implemented with an array or a linked list)

Queue first in first out

The queue opens up a continuous space.

Overflow in sequential queues:

True overflow: the phenomenon of space overflow caused by stack operation when the queue is full.

False overflow: the space of the deleted element can never be reused because the head and tail pointer only increases but does not decrease in the operation of joining and leaving the team. When the actual number of elements in the queue is much smaller than the size of the vector space, it may not be possible to join the queue because the tail pointer has exceeded the upper bound of the vector space.

two。 Circular queue

In the actual use of the queue, in order to make the queue space can be reused, the use of the queue is often slightly improved: no matter insert or delete, once the rear pointer increases by 1 or the front pointer increases by 1, it points to the starting position of this contiguous space. If you really increase your MaxSize-1 from 1 to 0, you can use the remainder operations rear%MaxSize and front%MaxSize to achieve. In fact, this is to think of the queue space as a circular space, in which the memory units are recycled, and the queues managed in this way are also called circular queues. Except for some simple applications, the really practical queue is the circular queue.

3. Realization idea

Because of the overflow problem of ordinary queues, we use arrays to implement circular queues.

1. The first element of the front pointing to the queue is initially 0.

2. Rear points to the last position of the element at the end of the queue (a piece of space vacated as a convention) is initially 0.

3. Condition for full queue: (rear+1)% maxSize = front

4. Condition for empty queue: rear = front

5. Number of elements in the queue: (rear+maxSize-front)% maxSize

Why the condition of full queue is (rear+1)% maxSize = front

(1) assume that rear > front

Rear-front=maxSize-1

Rear+1-maxSize=front

Because rear+1 must be equal to maxSize when the rear > front queue is full

(rear+1)% maxSize = rear+1-maxSize = 0

(2) assume that front > rear

Front-rear=1

Rear+1=front

Because rear+1 must be less than maxSize when front > rear

So (rear+1)% maxSize=rear+1

(3) if the queue is full as shown above, the condition is (rear+1)% maxSize = front

The count of the number of elements is similar to this

4. Code implementation

Public class Queue {the maximum number of private int frontPoint; / / stored in the queue private int frontPoint; / / head pointer to the last data at the end of the queue private int [] array; / / array of analog queues / * initialize queue * / public Queue (int max) {maxSzie = max; frontPoint = 0 RearPoint = 0; array = new int [max];} / * determine whether the queue is empty * / public boolean isEmpty () {return frontPoint = = rearPoint;} / * determine whether the queue is full * / public boolean isFull () {return (rearPoint+1)% maxSzie = = frontPoint } / * add data to the queue * / public void add (int x) {if (isFull ()) {System.out.println ("current queue full"); return;} / / add data array [rearPoint] = x; / / tail pointer rearPoint = (rearPoint+1)% maxSzie System.out.println ("added successfully");} / * fetch the data from the queue * / public int remove () {if (isEmpty ()) {throw new RuntimeException ("the current team is listed as empty");} / / assign the value of the queue header to the temporary variable int x = array [frontPoint] / / when the pointer after removing the data needs to move backward, it points to the new queue header frontPoint = (frontPoint+1)% maxSzie; System.out.println ("removed successfully"); return x;} / * * get queue header data * / public int gethead () {if (isEmpty ()) {throw new RuntimeException ("current queue is empty") } return array [frontPoint];} / * traversal queue * / public void show () {int x = 0; for (int I = frontPoint; I

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.