/
Queue
A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. Elements are added at the rear and removed from the front, just like a real-world queue of people waiting in line.
Data Structure
O(1)
How Queue Works
A queue is an abstract data type that operates on the FIFO (First-In, First-Out) principle. The element that is inserted first is the one that gets removed first. Think of it like a line at a ticket counter: the first person in line is the first person served.
A queue supports two primary operations:
- Enqueue — Adds an element to the rear (back) of the queue. This is an O(1) operation.
- Dequeue — Removes and returns the element at the front of the queue. This is an O(1) operation.
Additional operations commonly provided:
- Peek (or Front) — Returns the front element without removing it. O(1) time.
- isEmpty — Checks whether the queue has no elements. O(1) time.
- Size — Returns the number of elements currently in the queue. O(1) time.
Queues can be implemented using arrays, linked lists, or circular buffers. The array-based implementation is simple but may waste space unless a circular approach is used. The linked-list implementation allows the queue to grow dynamically without wasted capacity.
Common real-world applications of queues include:
- Task scheduling — Operating systems use queues to manage processes waiting for CPU time.
- Breadth-First Search (BFS) — Graph traversal algorithms rely on queues to explore nodes level by level.
- Print spooling — Print jobs are queued and processed in order.
- Message buffers — Asynchronous communication systems use queues to buffer messages between producers and consumers.
- Rate limiting — Request queues help manage traffic to web services.
Interactive Visualization
Experiment with the queue below. Enter a value and click an operation button to see how it works step by step. Use the playback controls to step through or auto-play the animation.
Queue: [15, 42, 8, 23, 7]. Use the operation buttons below.
Code Implementation
Below is a complete queue implementation with enqueue, dequeue, peek, and isEmpty operations in three languages.
from collections import deque
class Queue:
def __init__(self):
"""Initialize an empty queue using a deque for O(1) operations."""
self._data = deque()
def enqueue(self, value):
"""Add an element to the rear of the queue. O(1)"""
self._data.append(value)
def dequeue(self):
"""Remove and return the front element. O(1)
Raises IndexError if the queue is empty.
"""
if self.is_empty():
raise IndexError("Dequeue from an empty queue")
return self._data.popleft()
def peek(self):
"""Return the front element without removing it. O(1)
Raises IndexError if the queue is empty.
"""
if self.is_empty():
raise IndexError("Peek from an empty queue")
return self._data[0]
def is_empty(self):
"""Check whether the queue is empty. O(1)"""
return len(self._data) == 0
def size(self):
"""Return the number of elements in the queue. O(1)"""
return len(self._data)
def __str__(self):
"""Return a string representation (front on the left)."""
return "Queue([" + ", ".join(str(x) for x in self._data) + "])"
# Example usage
q = Queue()
for val in [15, 42, 8, 23, 7]:
q.enqueue(val)
print(q) # Queue([15, 42, 8, 23, 7])
print(q.peek()) # 15
print(q.dequeue()) # 15
print(q.dequeue()) # 42
print(q) # Queue([8, 23, 7])
print(q.is_empty()) # False
print(q.size()) # 3
import java.util.LinkedList;
import java.util.NoSuchElementException;
public class Queue<T> {
private final LinkedList<T> data;
public Queue() {
this.data = new LinkedList<>();
}
/** Add an element to the rear of the queue. O(1) */
public void enqueue(T value) {
data.addLast(value);
}
/** Remove and return the front element. O(1) */
public T dequeue() {
if (isEmpty())
throw new NoSuchElementException("Dequeue from an empty queue");
return data.removeFirst();
}
/** Return the front element without removing it. O(1) */
public T peek() {
if (isEmpty())
throw new NoSuchElementException("Peek from an empty queue");
return data.getFirst();
}
/** Check whether the queue is empty. O(1) */
public boolean isEmpty() {
return data.isEmpty();
}
/** Return the number of elements in the queue. O(1) */
public int size() {
return data.size();
}
@Override
public String toString() {
return "Queue(" + data.toString() + ")";
}
public static void main(String[] args) {
Queue<Integer> q = new Queue<>();
int[] values = {15, 42, 8, 23, 7};
for (int val : values) {
q.enqueue(val);
}
System.out.println(q); // Queue([15, 42, 8, 23, 7])
System.out.println(q.peek()); // 15
System.out.println(q.dequeue()); // 15
System.out.println(q.dequeue()); // 42
System.out.println(q); // Queue([8, 23, 7])
System.out.println(q.isEmpty()); // false
System.out.println(q.size()); // 3
}
}
#include <iostream>
#include <queue>
#include <stdexcept>
using namespace std;
template <typename T>
class Queue {
private:
queue<T> data;
public:
// Add an element to the rear of the queue. O(1)
void enqueue(T value) {
data.push(value);
}
// Remove and return the front element. O(1)
T dequeue() {
if (isEmpty())
throw runtime_error("Dequeue from an empty queue");
T front = data.front();
data.pop();
return front;
}
// Return the front element without removing it. O(1)
T peek() const {
if (isEmpty())
throw runtime_error("Peek from an empty queue");
return data.front();
}
// Check whether the queue is empty. O(1)
bool isEmpty() const {
return data.empty();
}
// Return the number of elements in the queue. O(1)
size_t size() const {
return data.size();
}
// Print the queue contents (front to rear)
void print() const {
queue<T> copy = data;
cout << "Queue([";
bool first = true;
while (!copy.empty()) {
if (!first) cout << ", ";
cout << copy.front();
copy.pop();
first = false;
}
cout << "])" << endl;
}
};
int main() {
Queue<int> q;
int values[] = {15, 42, 8, 23, 7};
for (int val : values) {
q.enqueue(val);
}
q.print(); // Queue([15, 42, 8, 23, 7])
cout << q.peek() << endl; // 15
cout << q.dequeue() << endl; // 15
cout << q.dequeue() << endl; // 42
q.print(); // Queue([8, 23, 7])
cout << boolalpha << q.isEmpty() << endl; // false
cout << q.size() << endl; // 3
return 0;
}
Complexity Analysis
The table below summarizes the time and space complexities for common queue operations.
| Operation | Time Complexity | Notes |
|---|---|---|
| Enqueue | O(1) | Element is added at the rear; no shifting needed |
| Dequeue | O(1) | Element is removed from the front (amortized O(1) for array-based) |
| Peek | O(1) | Direct access to the front element |
| isEmpty | O(1) | Simple check on the size or pointer comparison |
| Search | O(n) | Must scan from front to rear; not a standard queue operation |
| Space | O(n) | Proportional to the number of elements stored |
Quiz
Q1. What principle does a queue follow?
A queue follows the FIFO principle: the first element added (enqueued) is the first one removed (dequeued), just like a real-world line of people.
Q2. What is the time complexity of the enqueue operation?
Enqueue adds an element at the rear of the queue. With a linked-list or circular buffer implementation, this is done in constant time O(1) since we maintain a rear pointer.
Q3. If you enqueue 10, 20, 30 (in that order) and then dequeue once, which element is returned?
Since a queue is FIFO, the first element enqueued (10) is the first one dequeued. After dequeue, the queue contains [20, 30].
Q4. Which algorithm relies on a queue for its traversal order?
BFS uses a queue to explore all neighbors at the current depth level before moving to nodes at the next depth level. DFS, in contrast, uses a stack (or recursion).
Q5. What does the peek operation do on a queue?
Peek returns the element at the front of the queue without modifying the queue. It allows you to inspect the next element that would be dequeued, which is useful for conditional logic before committing to a dequeue.