p. 408 · PDF 418

1-3-2 Queue

Queue is a FIFO (First-In First-Out) data structure where data that is recorded first is read out first. You can simply think of data structure as a tube where entry and exit of data are different. A queue is also called a waiting line from the image of waiting in a line. Storing data in a queue is called enqueue (enq), and extracting data from a queue is called dequeue (deq). · 1 question

p. 409 · PDF 419

Enlarge original visual

Original source text

Figure 7-6  Image of queue 

Source visual description

The original queue drawing shows enqueue and dequeue operations on the stored data.

For implementing a queue, an HP (Head Pointer) that points at the first element and a TP (Tail Pointer) that points at the last element are used. When data is stored, it is stored at the position that is obtained by updating the value (e.g., generally +1) of pointer TP. In contrast, when data is extracted, the value of pointer HP is updated (e.g., generally +1) after data is extracted from the position of pointer HP. The process (i.e., enq) of storing data in a queue is shown as follows:

Enlarge original visual

Source visual description

Original Queue source layout. Source labels: .

When a queue is represented with an array, both pointers (HP and TP) keep increasing by one at a time. Therefore, an infinite number of array elements is required. So, in the actual process, when the value of a pointer becomes larger than the number of array elements, the concept of returning this value to 1 is used. With this concept, array elements are used in circulation, and it becomes possible to implement a queue with an array of the finite number of elements.

Enlarge original visual

Original source text

Figure 7-7  Image of circular use of array 

Source visual description

The original array row marks TP and HP positions and provides a shaded-data key.