Queue

From Chessprogramming wiki
Revision as of 16:10, 3 June 2018 by GerdIsenberg (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Home * Programming * Data * Queue

Queue [1]

A Queue is a linear data structure to collect data entities in first in, first out order (FIFO). The only operations are the addition of entries to the rear terminal position (enqueue) and removal of entries from the front terminal position (dequeue). Queues may be instantiated from (shared) main memory, and therefor accessed with low latency from various processes or threads, otherwise their hard- and low-level software implementation is hidden by Middleware layers. Various free and commercial programming language libraries provide queue implementations. Queuing devices like pipes and sockets are likely associated with a stream or file descriptor. However, in memory, a queue might be implemented with an array (likely fixed sized circular buffer) or linked list.

Applications

While there are algorithmic applications within one thread, most queue application are related to inter-process- or inter-thread communication, and buffering within hard- and software.

Buffering

A buffer is used to temporarily keep data while it is being moved from one place to another. A buffer often adjusts timing by implementing a queue or FIFO algorithm in memory, simultaneously writing data into the queue at one rate and reading it at another rate.

Within a physical layer, for instance the RS-232 (V.24) serial port and their electronic circuits, namely universal asynchronous receiver/transmitter (UART), FIFOs [2] in hardware are used to relax polling or interrupt request handling data link layer from time constrains, which may otherwise yield in possible data overruns and exception handling. Those FIFOs consists of a set of read and write "pointers", sequential control logic with appropriate storage, likely a set of flip-flops or latches.

One application of RS-232 in computer chess is Chrilly Donninger's Auto232 Interface to play automatic matches between chess programs on different computers [3].

Message Queue

A message queue is used for inter-process communication, or for inter-thread communication within the same process. Many implementations of message queues work internally within an operating system and its graphical user interface like Windows, i.e. to pass hardware events such as mouse and keyboard inputs to an application. Since events may have different priorities, i.e. keyboard event and paint event as request to re-paint a window, message queues of most often implemented as priority queues.

Other queue implementations allow the passing of messages between different computer systems, connecting multiple applications and multiple operating systems.

These message queuing systems typically provide enhanced resilience functionality and protocols to ensure that messages do not get "lost" in the event of a system failure. It is applied by a message-oriented middleware, i. e. remote direct memory access of MPI queues.

Pipeline

One related application of a thread safe queue for inter-process communication is the pipeline. The concept is mentioned as pipes and filters design pattern. The information that flows in these pipelines is a stream of records, bytes or bits.

In computer chess protocols like the Chess Engine Communication Protocol or the Universal Chess Interface, the communication between engine and the graphical user interface is likely based on pipelines, redirected from standard streams.

Algorithms

The informal breadth-first algorithm requires a queue to traverse all nodes of a tree:

  1. Enqueue the root node.
  2. Dequeue a node and examine it.
If the element sought is found in this node, quit the search and return a result.
Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
  1. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
  2. Repeat from Step 2.

See also

Publications

External Links

Ring buffer.svg

C

C++

Boost C++ Libraries - boost/pending/queue.hpp
Boost C++ Libraries - libs/graph/example/dave.cpp

Java

Perl

Python

Ruby

Tcl

.NET

Middleware

References

Up one Level