Queue (abstract data type)
A FIFO collection supporting enqueue, dequeue and peek operations. Queues appear in scheduling, buffering, traversal and messaging; variants include circular, blocking and priority queues.
Overview
In computer science, a queue is an abstract data type that represents a collection of elements maintained in first-in, first-out (FIFO) order. Elements are added at one end (the rear or tail) and removed from the other (the front or head). The FIFO discipline makes queues suitable for modeling sequential waiting lines and many streaming or scheduling scenarios.
Core operations and characteristics
Typical operations provided by a queue interface include:
- enqueue: insert an element at the rear.
- dequeue: remove and return the element at the front.
- peek (or front): observe the front element without removing it.
- auxiliary checks such as isEmpty and size.
Elements between the front and rear are not directly accessed; the only permitted removals are from the front. Enqueue and dequeue are commonly implemented to run in constant time (O(1)) on average.
Implementations and common forms
Queues can be realized in several ways depending on performance and memory needs. Common implementations include arrays (often as circular buffers to reuse space), singly linked lists with head and tail pointers, and wrappers around double-ended queues. Some programming environments provide blocking or bounded queue implementations for thread coordination.
Applications and examples
Queues are ubiquitous in software and systems: they form the basis of breadth-first graph search, job and task scheduling, print spooling and network packet buffering, producer–consumer message passing, and event loops in user interfaces. In each case the FIFO order preserves processing fairness or arrival order.
Variants and notable distinctions
Several variants modify the basic FIFO behavior. A priority queue associates keys or priorities with elements; removal returns the element with highest (or lowest) priority rather than the oldest. Priority queues are often implemented with heaps. A deque (double-ended queue) permits insertion and removal at both ends. Bounded and blocking queues enforce capacity limits and can suspend producers or consumers until space or items become available.
Concurrency and performance considerations
When used between threads or processes, queues require synchronization. Many libraries offer thread-safe or lock-free queue implementations to reduce contention. Choice of implementation affects memory usage, worst-case performance and suitability for real-time or high-throughput systems.
Further reading
For general theory and practical APIs, consult resources on data structures and concurrent programming; these discuss trade-offs among array-backed rings, linked representations, and priority-based variants in greater detail.
Questions and answers
Q: What is a queue in computer science?
A: A queue is a data structure used for storing items before they are processed.
Q: What are the two primary operations that can be performed on a queue?
A: The two primary operations that can be performed on a queue are Enqueue - adding the item to the back of the queue, and Dequeue - removing the item at the front of the queue.
Q: Can an operation be performed to look at the item at the front of the queue without removing it?
A: Yes, there may be an operation to look at the item at the front of the queue without removing it.
Q: Are items that are between the first and the last element of the queue directly accessible?
A: No, items that are between the first and the last element of the queue are not directly accessible.
Q: What is a priority queue?
A: A priority queue is a specialization of the queue data structure in which each item has a weight that determines its position in the queue.
Q: What does the weight of each item in a priority queue determine?
A: The weight of each item in a priority queue determines its position in the queue.
Q: Can items in a priority queue be stored in any order?
A: No, items in a priority queue are stored in order based on their weight or priority.
Related articles
Author
AlegsaOnline.com Queue (abstract data type) Leandro Alegsa
URL: https://en.alegsaonline.com/art/80523