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

This article mainly introduces the web development queue belongs to what data structure, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, the following let the editor take you to understand it.

The queue is a linear data structure; the queue only allows deletions at the front end of the table and inserts at the back end of the table. Like the stack, the queue is a linear table whose operation is limited; the end of the insert operation is called the end of the queue, and the end of the delete operation is called the head of the line.

Queue is a linear data structure.

Queue is a special linear table, which is special in that it only allows deletion at the front end of the table (front) and insert operation at the back end of the table (rear). Like the stack, queue is a linear table with limited operations. The end of the insert operation is called the end of the queue, and the end of the delete operation is called the head of the line. When there are no elements in the queue, it is called an empty queue.

The data element of a queue is also called a queue element. Inserting a queue element into the queue is called queuing, and removing a queue element from the queue is called dequeuing. Because queues are only allowed to be inserted at one end and deleted at the other end, only the earliest elements that enter the queue can be deleted from the queue first, so the queue is also known as the first-in-first-out (FIFO-first in first out) linear table.

Sequential queue

To establish a sequential queue structure, it must be statically allocated or dynamically applied for a continuous piece of storage space, and two pointers must be set for management. One is the header pointer front, which points to the queue header element, and the other is the tail pointer rear, which points to the storage location of the next queuing element, as shown in the figure

Each time an element is inserted at the end of the line, rear is incremented by 1; each time an element is deleted at the head of the line, front is incremented by 1. As the insert and delete operations proceed, the number of queue elements changes, and the storage space occupied by the queue moves in the contiguous space allocated for the queue structure. When front=rear, there are no elements in the queue, which is called an empty queue. When the rear is added beyond the contiguous space that points to the allocation, the queue can no longer insert new elements, but there is often a large amount of unoccupied free space, which is the storage unit that has been occupied by the queue elements that have been dequeued.

Overflow in sequential queues:

(1) "underflow" phenomenon: the overflow phenomenon caused by the team operation when the team is listed as empty. "underflow" is a normal phenomenon and is often used as a condition for program control transfer.

(2) the phenomenon of "true overflow": when the queue is full, the stack operation produces space overflow. "true overflow" is an error state and should be avoided.

(3) the phenomenon of "false overflow": because the head and tail pointer only increases but does not decrease in the operation of joining and leaving the team, the space of the deleted element can never be reused. 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. This phenomenon is called "false overflow" phenomenon.

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 queues are circular queues.

In a circular queue, there is front=rear when the queue is empty, and front=rear when all the queue space is full. In order to distinguish between the two cases, it is stipulated that the circular queue can only have a maximum of MaxSize-1 queue elements, and when there is only one empty storage unit in the circular queue, the queue is full. Therefore, the condition for a null queue is front=rear, and the condition for a full queue is front= (rear+1)% MaxSize. The situation of empty and full teams is shown in the figure:

Thank you for reading this article carefully. I hope the article "what is the data structure of web development squadron queue" shared by the editor will be helpful to you? at the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.