Queue
- In Turkish
- Kuyruk
- Pronunciation
- KYOO
In short
A queue is a data structure that stores items in first in, first out (FIFO) order, so the item that has waited longest is always the next one removed.
What is a queue data structure?
A queue is a collection where items are added at one end, called the back or rear, and removed from the other end, called the front. Adding an item is called enqueue and removing one is called dequeue. This rule is known as FIFO: first in, first out.
It works just like a line at a coffee shop: new customers join at the back, and the person at the front is served next. A well-built queue, based on a linked list, a circular buffer (a fixed-size array whose ends wrap around), or a double-ended queue, performs enqueue and dequeue in O(1) time. A common mistake is using a plain array and removing from the front with JavaScript's shift() or Python's list.pop(0), which take O(n) time because every remaining item has to move one position.
Queues are used whenever work should be handled in the order it arrives: print jobs, keyboard and mouse events, network packets waiting to be sent, and background tasks in a job system. Breadth-first search in a graph uses a queue to visit the nearest nodes first. At a larger scale, a message queue is a separate service that applies the same idea between programs, holding messages until a consumer is ready to process them.
The opposite of a queue is a stack, which removes the newest item first (LIFO). A priority queue is different too: it removes the item with the highest priority rather than the oldest one, and it is usually built on a heap. A deque (a double-ended queue, pronounced like deck) allows adding and removing at both ends, so it can act as either a queue or a stack.
At a glance
Key takeaways
- A queue follows FIFO order: first in, first out.
- Enqueue adds to the back and dequeue removes from the front, each in O(1) time when implemented well.
- In Python, use
collections.dequewithappend()andpopleft()instead oflist.pop(0). - Breadth-first search, job scheduling, and buffering all rely on queues.
- A priority queue removes the highest-priority item first, not the oldest.
Example
from collections import deque
queue = deque()
queue.append("first job") # enqueue at the back: O(1)
queue.append("second job")
queue.append("third job")
print(queue.popleft()) # dequeue from the front: O(1), prints "first job"
print(queue.popleft()) # "second job"
print(queue[0]) # peek at the next item without removing it: "third job"
# Avoid list.pop(0) for queues: it shifts every remaining item, which is O(n)Readers ask
What is the difference between a queue and a stack?
A queue removes the item that was added first (FIFO), while a stack removes the item that was added last (LIFO). Use a queue for fair, in-order processing and a stack for undo, backtracking, and nested structures.
Is array.shift() slow in JavaScript?
It can be. shift() removes the first element and moves every other element down one index, which is O(n), so draining a large array with it in a loop becomes O(n^2). For big queues, keep an index that points to the front instead of shifting, or use a dedicated queue implementation.
What is a priority queue?
A priority queue is a queue in which each item has a priority, and the highest-priority item is removed first regardless of when it arrived. It is usually implemented with a heap, which makes both inserting and removing O(log n).
Often compared
See also
- StackData Structures, p. 31A stack is a data structure that stores items in last in, first out (LIFO) order, so the most recently added item is always the first one removed.
- Linked ListData Structures, p. 22A linked list is a data structure that stores items in separate nodes, where each node holds a value and a reference to the next node in the chain.
- HeapData Structures, p. 19A heap is a tree-based data structure that keeps the smallest or largest item at its root, so you can read it in O(1) and remove it in O(log n) time.
- GraphData Structures, p. 15A graph is a data structure made of nodes, called vertices, connected by edges, and is used to model relationships such as roads, friendships, and dependencies.
- Message QueueBackend & APIs, p. 29A message queue is a component that stores messages from one service until another is ready to process them, so parts of a system can work asynchronously.
- Big O NotationProgramming Fundamentals, p. 6Big O notation describes how an algorithm's running time or memory use grows as its input gets larger, focusing on the growth rate rather than exact speed.
- DequeData Structures, p. 11A deque is a double-ended queue that lets you add and remove items at both the front and the back in constant time, so it can act as both a stack and a queue.
Spotted a mistake or something missing on this page?Suggest an edit