A queue is a linear data structure that follows the First In, First Out (FIFO) principle. The element that enters the queue first is the first one to leave. Real-world queues model a line at a ticket counter, a printer queue, or customers waiting for service in a bank. The person who arrives earliest is served first, and newcomers join at the end of the line.
In a queue, insertion takes place at the rear (also called back or tail) and deletion takes place at the front (also called head). The operation that adds an element to the rear is called enqueue, and the operation that removes an element from the front is called dequeue. This is exactly the opposite discipline of a stack, which uses a single end for both operations.
This chapter explains the queue concept, its terminology and operations, and how to implement a queue in Python using a list. It also covers the circular queue, a refined version that reuses the space freed by dequeue operations, and the deque (double-ended queue) available in Python's collections module. Applications of queues include print spooling, CPU and disk scheduling, and breadth-first traversal. Queue questions in the board examination frequently combine concept recall with short trace-based or implementation questions.
A queue provides two fundamental operations. Enqueue inserts a new element at the rear of the queue. Dequeue removes and returns the element at the front of the queue. Two supporting operations are usually provided: front returns the front element without removing it, and isEmpty checks whether the queue is empty. Attempting to dequeue from an empty queue causes underflow, while enqueuing into a full fixed-capacity queue causes overflow.
queue = []
queue.append(10) # enqueue 10
queue.append(20) # enqueue 20
front_item = queue.pop(0) # dequeue -> 10
print(front_item, queue) # 10 [20]
Because pop(0) removes the first element of a Python list, it performs the dequeue operation, though it is less efficient than append and pop for stacks.
A straightforward list-based queue stores new elements at the end and removes from the front. The append() method serves as enqueue and pop(0) serves as dequeue. A class wrapper makes the behaviour clear.
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.isEmpty():
return self.items.pop(0)
else:
return None
def front(self):
if not self.isEmpty():
return self.items[0]
else:
return None
def size(self):
return len(self.items)
def display(self):
print(self.items)
Using the class:
q = Queue()
q.enqueue(5)
q.enqueue(10)
q.enqueue(15)
q.display() # [5, 10, 15]
print(q.dequeue()) # 5
print(q.front()) # 10
print(q.size()) # 2
The first element of the list is the front of the queue, and the last element is the rear.
Using pop(0) is O(n) because all remaining elements shift left. For efficiency, Python offers collections.deque, a double-ended queue whose popleft() and append() operations both run in O(1). Examination implementations, however, usually rely on the simple list version above.
In a fixed-capacity linear queue, every dequeue frees space at the front, but the freed positions are not reused unless elements are shifted, leading to a false "queue full" condition. The circular queue solves this by connecting the rear to the front logically, wrapping around the array. Two indices, front and rear, move circularly, and the queue is full when (rear + 1) % size == front and empty when front == rear.
class CircularQueue:
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.front = 0
self.rear = 0
def isEmpty(self):
return self.front == self.rear
def isFull(self):
return (self.rear + 1) % self.size == self.front
def enqueue(self, item):
if self.isFull():
print("Queue Overflow")
else:
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.size
def dequeue(self):
if self.isEmpty():
print("Queue Underflow")
return None
item = self.queue[self.front]
self.front = (self.front + 1) % self.size
return item
The modulus operation % size wraps the indices, reusing the empty positions at the front.
A deque allows insertion and deletion at both ends. Python's collections.deque provides append(), appendleft(), pop(), and popleft(). A deque is useful when a data structure must act as both a stack and a queue, or for sliding-window problems.
from collections import deque
d = deque([10, 20, 30])
d.appendleft(5) # [5, 10, 20, 30]
d.append(40) # [5, 10, 20, 30, 40]
d.popleft() # removes 5
d.pop() # removes 40
print(d) # deque([10, 20, 30])
When multiple users send documents to a shared printer, the print jobs are queued. The job that arrives first is printed first, so the printer follows FIFO discipline. This prevents long waits for later jobs and guarantees fairness.
Operating systems use queues to schedule processes and disk requests. Ready queues hold processes waiting for the CPU, and I/O queues hold processes waiting for input/output. Round-robin scheduling serves each process from the front of the queue for a fixed time slice.
Breadth-first search explores a graph level by level using a queue. Nodes are enqueued when discovered and dequeued when visited, ensuring that nodes closer to the source are processed before more distant ones.
Keyboard buffers and message-passing systems store events in a queue so that the oldest event is processed first, preserving the chronological order of events.
| Operation | What It Does | End Used |
|---|---|---|
| enqueue(item) | Add item to the rear | Rear |
| dequeue() | Remove and return front item | Front |
| front() | Return front item without removing | Front |
| isEmpty() | Check if queue is empty | - |
| size() | Return number of elements | - |
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO | FIFO |
| Insertion end | Top | Rear |
| Deletion end | Top | Front |
| Insert operation | push | enqueue |
| Delete operation | pop | dequeue |
| Example | Undo feature | Printer queue |
(rear + 1) % size == front must be used; rear == front alone means empty, not full.The queue brings fairness and order to computing through its first-in-first-out discipline. Enqueue and dequeue operate at opposite ends, and the structure naturally models everything from printer jobs to process scheduling. A simple list-based implementation is easy to understand, while the circular queue shows how careful index management with modulo arithmetic can make efficient use of fixed memory. The deque extends the idea to both ends, giving maximum flexibility. Because the queue underpins operating-system scheduling and graph traversal, mastering it is essential. In the next chapter, we move from linear structures to sorting algorithms, learning to arrange data into a meaningful order.