🧱 Unit 1 – Data Structures & Algorithms · Lesson 11
Queue and Deque
What is a queue?
A queue is a linear data structure open at both ends: items join at the rear and leave from the front. The rule is FIFO – First In, First Out.
Queues in real life
🎟️
Ticket counterThe first person in line is served first.🖨️
PrinterDocuments print in the order sent.📞
Call centreCalls are answered in arrival order.⌨️
Keyboard bufferKeys are processed in the order pressed.Queue operations
| Operation | Meaning | Python |
|---|---|---|
| ENQUEUE | Add at rear | q.append(x) |
| DEQUEUE | Remove from front | q.pop(0) |
| PEEK | See front item | q[0] |
| isEmpty / size | Check / count | len(q) |
Queue with a list
Python
queue = []
queue.append('Asha') # enqueue at REAR
queue.append('Ravi')
queue.append('Neha')
print('Queue:', queue, '| front =', queue[0], '| rear =', queue[-1])
print('Served:', queue.pop(0)) # dequeue from FRONT
print('Queue now:', queue)Queue: ['Asha', 'Ravi', 'Neha'] | front = Asha | rear = Neha
Served: Asha
Queue now: ['Ravi', 'Neha']
Queue with functions
Python
def isEmpty(q):
return len(q) == 0
def enqueue(q, item):
q.append(item)
def dequeue(q):
if isEmpty(q):
return 'Underflow'
return q.pop(0)
def peek(q):
return 'Underflow' if isEmpty(q) else q[0]
def size(q):
return len(q)
tickets = []
for t in [101, 102, 103]:
enqueue(tickets, t)
print('Size:', size(tickets), '| next:', peek(tickets))
print(dequeue(tickets), dequeue(tickets), dequeue(tickets))
print('Again:', dequeue(tickets))Size: 3 | next: 101
101 102 103
Again: Underflow
Printer queue simulation
Python
# Simulating a printer queue
jobs = []
for doc in ['notes.pdf', 'marks.xlsx', 'photo.png']:
jobs.append(doc)
print('Added', doc, '->', jobs)
while jobs:
print('Printing', jobs.pop(0), '| waiting:', len(jobs))Added notes.pdf -> ['notes.pdf']
Added marks.xlsx -> ['notes.pdf', 'marks.xlsx']
Added photo.png -> ['notes.pdf', 'marks.xlsx', 'photo.png']
Printing notes.pdf | waiting: 2
Printing marks.xlsx | waiting: 1
Printing photo.png | waiting: 0
What is a deque?
A deque (pronounced “deck”, double-ended queue) allows insertion and deletion at both ends. It can work as a stack or as a queue.
Deque in Python
Python
dq = []
dq.append(20) # insert at rear
dq.insert(0, 10) # insert at front
dq.append(30)
print('Deque:', dq)
print('Remove front:', dq.pop(0))
print('Remove rear :', dq.pop())
print('Left:', dq)Deque: [10, 20, 30]
Remove front: 10
Remove rear : 30
Left: [20]
The collections.deque class is faster for large data because removing from the front of a list shifts every element.
Python
from collections import deque
d = deque()
d.append('B'); d.appendleft('A'); d.append('C')
print(d)
print(d.popleft(), d.pop(), list(d))deque(['A', 'B', 'C'])
A C ['B']
Palindrome using deque
Python
def is_palindrome(word):
dq = list(word.lower())
while len(dq) > 1:
if dq.pop(0) != dq.pop(): # compare front with rear
return False
return True
for w in ['Madam', 'Level', 'Python']:
print(w, is_palindrome(w))Madam True
Level True
Python False
Stack vs Queue vs Deque
| Stack | Queue | Deque | |
|---|---|---|---|
| Rule | LIFO | FIFO | Both ends |
| Insert | top: append() | rear: append() | append() / insert(0,x) |
| Delete | top: pop() | front: pop(0) | pop() / pop(0) |
| Example | Undo | Ticket counter | Browser history, palindrome |
Frequently Asked Questions
What does FIFO mean?
First In, First Out: the item that joins the queue first is served first.
Where are items added and removed in a queue?
Added at the REAR (enqueue) and removed from the FRONT (dequeue).
What is a deque?
A double-ended queue where insertion and deletion are allowed at both the front and the rear.
