What data structure is a queue?

Queue is a linear data structure. The queue only allows deletion operations at the front end of the table, and insertion operations at the back end of the table. Like the stack, the queue is a linear table with restricted operations; the end where the insertion operation is performed is called the end of the queue, and the deletion operation is performed The end is called the head of the team.

#The operating environment of this article: windows10 system, thinkpad t480 computer.

Queue is a linear data structure.

The queue is a special linear table. The special thing is that it only allows deletion operations at the front end of the table (front), and insertion operations at the back end (rear) of the table. Just like the stack, A queue is a linear list with restricted operations. The end that performs the insertion operation is called the tail of the queue, and the end that performs the deletion operation is called the head of the queue. When there are no elements in the queue, it is called an empty queue.

The data elements of the queue are also called queue elements. Inserting a queue element into the queue is called enqueuing, and deleting a queue element from the queue is called dequeuing. Because the queue only allows insertion at one end and deletion at the other end, only the element that enters the queue earliest can be deleted from the queue first, so the queue is also called a first-in-first-out (FIFO—first in first out) linear list.

Sequential queue

To establish a sequential queue structure, you must statically allocate or dynamically apply for a continuous storage space, and set two pointers for management. One is the head pointer front, which points to the head element; the other is the tail pointer rear, which points to the storage location of the next element in the queue, as shown in the figure

Every time an element is inserted at the end of the queue, rear increases by 1; every time an element is deleted at the head of the queue, front increases by 1. As the insertion and deletion operations proceed, the number of queue elements continues to change, and the storage space occupied by the queue also moves in the continuous space allocated for the queue structure. When front=rear, there are no elements in the queue, which is called an empty queue. When rear increases beyond the continuous space that points to the allocation, the queue can no longer insert new elements, but there is often a large amount of available space that is not occupied at this time. These spaces are storage units that have been occupied by queue elements that have been dequeued.

Overflow phenomenon in the sequential queue:

(1) "Underflow" phenomenon: When the queue is empty, the overflow phenomenon caused by the queue operation. "Underflow" is a normal phenomenon and is often used as a condition for program control transfer.

(2) "True overflow" phenomenon: When the queue is full, a push operation on the stack will cause space overflow. "True overflow" is an error condition and should be avoided.

(3) "False overflow" phenomenon: Since the head and tail pointers only increase but do not decrease during the enqueue and dequeue operations, the space of the deleted element can never be reused. When the actual number of elements in the queue is far smaller than the size of the vector space, the queue operation may not be possible because the tail pointer has exceeded the upper bound of the vector space. This phenomenon is called "false overflow".

Circular queue

When actually using the queue, in order to make the queue space reusable, the method of using the queue is often slightly improved: regardless of insertion or deletion, once When the rear pointer is incremented by 1 or the front pointer is incremented by 1 and exceeds the allocated queue space, let it point to the starting position of this continuous space. If you really change from MaxSize-1 by 1 to 0, you can use the remainder operations rear%MaxSize and front%MaxSize to achieve it. This actually imagines the queue space as a circular space, and the storage units in the circular space are used cyclically. The queue managed in this way is also called a circular queue. In addition to some simple applications, the really practical queue is the circular queue.

In a circular queue, when the queue is empty, there is front=rear, and when all the queue space is full, there is also front=rear. In order to distinguish between the two situations, it is stipulated that the circular queue can only have MaxSize-1 queue elements at most. When there is only one empty storage unit left in the circular queue, the queue is full. Therefore, the condition for the queue to be empty is front=rear, and the condition for the queue to be full is front=(rear 1)%MaxSize. The situation of empty and full queues is as shown in the figure:

Recommendation: " Programming Video"

The above is the detailed content of What data structure is a queue?. For more information, please follow other related articles on the PHP Chinese website!