Queue (data structure)

In computer science , a queue ( English queue [ kju ]) describes a frequently used data structure . It is used to temporarily store objects in a sequence before they are processed further.

Working principle

In contrast to the ring buffer described later, a queue can hold any number of objects and returns them in the order in which they were inserted. For this purpose, queues provide the operations

enqueue to add an object and
dequeue ready to retrieve and remove an object.

While the queue (per axiom ) accepts an infinite number of objects, the ring buffer can overflow when it is exhausted, for which processing must be agreed, see also below .

The principle of First In - First Out ( FIFO for short , German first in - first out ) is used, i.e. dequeue always returns the object from the queue which of the objects still in the queue is the first enqueue was put into it.

illustration

You can think of a queue as a queue of customers at a till. The last person to stand in line will also be served last. Conversely, the person who queued first will be served first.

With enter a new value ( 3 ) is added to the queue, and with leave the longest saved element ( 37 ) is removed. The only read access is done with front and returns the first saved element of the queue (here in example 37 , of course under the assumption that the leave operation has not yet been carried out!). ${\ displaystyle \ to}$

application

The pipe used for interprocess communication is one of the most important applications for queuing.

Queues also allow slow external devices, e.g. B. printer, decoupled from program processing. After a print job has been placed in the queue, the job is signaled to the program as "printed", but the job is actually only carried out later when the device is available.

Queues are also often used to transfer data between asynchronous processes in distributed systems , i.e. when data has to be buffered before further processing. Access is via APIs anchored in the operating system . The size of the queue is limited by the operating system.

Graphic user interfaces buffer mouse and keyboard events in a so-called "Message Queue" according to the FIFO principle, i. H. in the order of their appearance. They then forward these to the correct processes, depending on the position and input focus.

A queue can also be used for parallelization. Think of it like a post office with multiple counters for a queue. In this way, tasks can be set that will later be processed in parallel.

Implementation as a ring buffer

Ring buffer with in pointer and out pointer. Unread items are shown in green, read items in orange and emptied items in gray. The direction in which the buffer is filled is also displayed.

Queues are often implemented as ring buffers with a pointer each to the beginning (in pointer) and end (out pointer). The special feature of the ring buffer is that it has a fixed size. The in pointer points to the first free element in the array that represents the ring buffer, and the out pointer to the first occupied element in the array. In contrast to the array, the oldest contents are overwritten when the buffer is full and further elements are stored in the ring buffer. An implementation of the ring buffer should either signal a buffer overflow or provide additional storage space if the ring buffer is full . In other cases the overwriting of old elements of the queue and thus the loss of data may be deliberate.

Typically, keyboard entries on a PC are implemented using a ring buffer. Inputs are initially received asynchronously in the interrupt procedure and stored as raw data in the keyboard buffer, then called up in the program sequence using the API function. When the pointer to the end reaches the pointer to the beginning and both pointers become identical, the buffer is empty. In the opposite case, the buffer is full, the relevant input is rejected in the interrupt and signaled acoustically.

Even modern flight recorders in the aircraft are usually based on a ring buffer, so after a crash only the measured values recorded in the last few days or the voice recordings recorded in the last minutes of the flight are available.

Relationship with stacks

Queues can be thought of as stacks of books that are filled from below; accordingly, there are implementations that make no fundamental difference between stacks and queues. The read end of a queue is fixed in REXX ; PUSHEntries stored with are read according to the LIFO principle ( L ast I n - F irst O ut), entries QUEUEstored with according to the FIFO principle. Queues are particularly interesting for interprocess communication.