CHAPTER 4: QUEUE

Introduction to Queue
• A Queue is an ordered linear data structure that follows the FIFO (First In First Out)
principle.
• Items are inserted at the rear (tail) and removed from the front (head).
• Real-life Examples: Bank queues, toll booths, printer tasks, IVRS systems.

FIFO Principle
• First-In-First-Out: The element added first is the one removed first.
• Implemented using two ends:

– REAR (TAIL) → for insertion

– FRONT (HEAD) → for deletion

Applications of Queue Real-Life

1. Train Ticket Waiting List

• When you book a ticket and it shows W/L1, it means your request is added to a
queue.
• If someone cancels their confirmed ticket, the one at the front of the queue (like
W/L1) gets confirmed.
• This strictly follows the First-In-First-Out (FIFO) principle.

2. Customer Care Calls (IVRS Systems)

• When you call a customer care number, you might hear: > ―Please wait while your
call is transferred…‖
• Your call is placed in a queue.
• As soon as a customer care executive is free, the first caller in the queue is attended.

3. Traffic Management (One-Way Road or Toll Booth)

• Vehicles on a one-way street or at a fuel pump/toll plaza form a queue.

• The vehicle that arrived first gets to move first.
Applications in Computer Science
1. Web Server Request Handling

• A server can handle only a limited number of simultaneous requests (say 50).
• If 1000 students try to check results at the same time, the server keeps extra
requests in a queue.
• These requests are served one by one as per FIFO.

2. CPU Task Scheduling in Operating Systems

• When multiple programs (called jobs) request CPU time, only one can run at a time.
• Jobs are queued and the CPU executes them in the order they arrive (simple job
scheduling).

3. Printer Queue Management

• If multiple print requests are sent to a shared printer:

– The first print command sent is executed first.
– Remaining ones wait in the print queue.

4.2 Operations on Queue

Operation Description

enqueue() Insert an element at rear. Exception: Overflow if full (static case).

dequeue() Remove from front. Exception: Underflow if empty.
isEmpty() Check if queue is empty.
peek() View the front item without removing.
isFull() Check if queue is full (not required in Python list-based queue).

Visual Example (Queue of alphabets):

enqueue('Z') → Z
enqueue('X') → Z X
enqueue('C') → Z X
C dequeue() → X C
enqueue('V') → X C
V
Implementation of Queue using Python

myQueue = list()

def enqueue(myQueue, element):

myQueue.append(element)

def isEmpty(myQueue):
return len(myQueue) == 0
def dequeue(myQueue):
if not isEmpty(myQueue):
return myQueue.pop(0)
else:
print("Queue is empty")
def size(myQueue):
return len(myQueue)
def peek(myQueue):
if isEmpty(myQueue):
print("Queue is empty")
return None
else:
return myQueue[0]

Program 4-1: Simulation of a Queue in a Bank

myQueue = list()

element = input("Enter person’s code to enter in queue:")

enqueue(myQueue, element)
element = input("Enter person’s code for insertion in
queue: ") enqueue(myQueue, element)

print("Person removed from queue is:", dequeue(myQueue))

print("Number of people in the queue is:", size(myQueue))

for _ in range(3):
element = input("Enter person’s code to enter in
queue: ") enqueue(myQueue, element)

print("Now removing remaining people from queue:")

while not isEmpty(myQueue):

print("Person removed from queue is", dequeue(myQueue))
Introduction to Deque (Double-Ended Queue)
• Deque allows insertion and deletion from both ends – front and rear.
• Can behave as both:

– Stack (LIFO): insertion/deletion at same end.

– Queue (FIFO): insertion/deletion at opposite ends.

Applications of Deque (Double-Ended Queue) Real-Life Applications

1. Re-entry at Ticket Counter

• A person buys a ticket, leaves, and then comes back with a query.
• Since they’ve already been served, they might get the privilege to rejoin from the
front, not the rear.
• This needs a data structure where you can insert from either end — a deque.

2. Toll Booth Queue Redirection

• Suppose multiple toll booths exist.

• If one booth clears early, vehicles from the rear of other queues might shift to the
front of the vacant booth’s queue.
• This needs both front and rear insertions/deletions, which is deque-like behavior.

Applications in Computer Science

1. Browser History Navigation

• URLs are added to a stack-like structure, but if the memory is limited, older
entries (from the rear) must be removed.
• Deque can store history and remove least-recently-used entries when full.

2. Undo/Redo in Text Editors

• Operations are stored so that the last action can be undone first, like a stack.
• But to manage multiple undo/redo and limited memory, deque provides efficient
handling.

Palindrome Checking A string is inserted character by character into a deque.

• Then characters are compared from front and rear simultaneously.
• If they match all the way, the string is a palindrome.
• Deque allows accessing both ends easily.
4.4.2 Operations on Deque

Operation Description

insertFront() Insert at front

insertRear() Insert at rear
deletionFront() Delete from front
deletionRear() Delete from rear
isEmpty() Check if deque is empty
getFront() View front without removing getRear()
View rear without removing

Algorithm 4.1: Palindrome using Deque

1. Traverse string left to right.
2. Insert each character at rear.
3. Repeat: delete character from both front and rear, compare.
4. If all pairs match → it’s a palindrome.

4.3 Implementation of Deque using Python

def insertFront(myDeque,
element): myDeque.insert(0,
element)

def insertRear(myDeque,
element):
myDeque.append(element)

def isEmpty(myDeque):
return len(myDeque) == 0

def deletionRear(myDeque):
if not isEmpty(myDeque):
return myDeque.pop()
else:
print("Deque empty")

def deletionFront(myDeque):
if not isEmpty(myDeque):
return myDeque.pop(0)
else:
print("Deque empty")
def getFront(myDeque):
if not isEmpty(myDeque):
return myDeque[0]
else:
print("Queue empty")

def getRear(myDeque):
if not isEmpty(myDeque):
return myDeque[-1]
else:
print("Deque empty")

Program 4-2: Menu-driven Deque Program

def main():
dQu = list()
choice = int(input("Enter 1 to use as queue, 2 otherwise: "))

if choice == 1:
element = input("Data for insertion at rear: ")
insertRear(dQu, element)
print("Data at front:", getFront(dQu))
element = input("Data for insertion at rear: ")
insertRear(dQu, element)
print("Removed:",
deletionFront(dQu))
print("Removed:",
deletionFront(dQu))
else:
element = input("Data for insertion at front: ")
insertFront(dQu, element)
print("Data at rear:", getRear(dQu))
element = input("Data for insertion at front: ")
insertFront(dQu, element)
print("Removed:",
deletionRear(dQu))
print("Removed:",