Queue
Home * Programming * Data * Queue
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:
- Enqueue the root node.
- 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.
- If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
- Repeat from Step 2.
See also
Publications
- Maged M. Michael, Michael L. Scott (1996). Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Department of Computer Science, University of Rochester, pdf
- Donald Knuth (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Third Edition), Addison-Wesley, ISBN 0-201-89683-4, 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
- Richard P. Stanley (2005). Queue Problems Revisited. pdf, Chess problem related [4]
- William N. Scherer III, Doug Lea, Michael L. Scott (2009). Scalable Synchronous Queues. Communications of the ACM, Vol. 52. No. 5, pdf
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). Introduction to Algorithms, 3rd Edition. ISBN 0-262-03384-4. 10.1: Stacks and queues
External Links
- Queue (abstract data type) from Wikipedia
- queue from Dictionary of Algorithms and Data Structures by Paul E. Black, National Institute of Standards and Technology
- FIFO from Wikipedia
- Double-ended queue from Wikipedia
- Named pipe from Wikipedia
- Queueing theory from Wikipedia
- Hartmann pipeline from Wikipedia
- Circular buffer from Wikipedia
C
C++
- C++ Reference : STL Containers : queue
- queue<T, Sequence> from Standard Template Library Programmer's Guide
- Qt 4.6: QQueue Class Reference
- Boost Graph Library: Breadth-First Search
Java
Perl
Python
Ruby
Tcl
.NET
Middleware
- Advanced Message Queuing Protocol from Wikipedia
- Advanced Message Queuing Protocol - Website
- Java Message Service
- Open Message Queue from Wikipedia
- Open Message Queue : Open Source Java Message Service (JMS)
- Apache ActiveMQ from Wikipedia
- Apache ActiveMQ - Index
- JORAM from Wikipedia
- JBoss Messaging from Wikipedia
- JBossMessaging - JBoss Community
- Oracle Advanced Queuing from Wikipedia
- IBM WebSphere MQ from Wikipedia
References
- ↑ Queue (abstract data type) from Wikipedia
- ↑ Serial UART, an in depth tutorial
- ↑ Technische Spezifikation des 232-Protokolls, rgcc, January 8, 1997
- ↑ Chess Problems
- ↑ CHESS - Microsoft Research a tool for finding and reproducing Heisenbugs in concurrent programs