Queue of Java data structure (power node Java College)

Definition of queue:

A queue is a linear table that allows insertion at one end and deletion at the other end.

(1) The end that allows deletion is called the front.

(2) The end that allows insertion is called the end of the queue.

(3) When there are no elements in the queue, it is called an empty queue.

(4) Queues are also called first in first out linear tables, or FIFO tables for short.

Queue modification is based on the first in first out principle. New members always join the end of the team, and the members who leave each time are always at the head of the queue (leaving the team halfway is not allowed).

Storage structure and implementation of queue

Sequential storage structure of queue

(1) Definition of sequential queue:

The sequential storage structure of queue is called sequential queue. In fact, sequential queue is a sequential table with limited operation.

(2) Representation of sequential queues:

Like a sequence table, a sequence queue uses a continuous memory space in memory to store the elements in the current queue.

Since the positions of the queue head and tail change, set two pointers front and rear to indicate the queue head element and tail element respectively, and their initial values should be set to 0 during queue initialization.

(3) Basic operation of sequential queue

When joining the team: insert the new element into the last bit of the position indicated by the rear.

When leaving the queue: delete the element referred to by front, then add 1 to front and return the deleted element.

(4) Overflow of sequence table

① "Underflow" phenomenon

When the queue is empty, the overflow phenomenon caused by queue operation is made. "Underflow" is a normal phenomenon, which is often used as a condition for program control transfer.

② "True overflow" phenomenon

When the queue is full, the stack operation will cause space overflow. "True overflow" is an error state and should be avoided.

③ "False overflow" phenomenon

Because the head and tail pointers only increase but not decrease in the queue in and out operations, the space of deleted elements can never be reused. When the actual number of elements in the queue is far less than the allocated space in memory, the queue operation may not be performed because the tail pointer has exceeded the upper bound of the vector space. This phenomenon is called "false overflow". As shown below

Circular queue:

As shown in the figure above, this sequential storage structure with head to tail is called circular queue.

Several important issues needing attention in circular queue:

① The judgment condition of team air, the condition of team air is front = rear;

② Queue full decision condition, (rear + 1)% queuesize = front. Queuesize is the initial space size of the queue.

Java implementation code of circular queue

The above is the queue of Java data structure (power node Java college sorting) introduced by Xiaobian. I hope it will be helpful to you. If you have any questions, please leave me a message, and Xiaobian will reply to you in time. Thank you very much for your support for the programming tips website!