CHAPTER 4
QUEUE
Introduction to Queue
A Queue is an ordered linear data structure that follows the FIFO (First In
First Out) principle.
In Queue, new items are inserted at one end called rear and removed from
the other end called front.
10 20 30 40
FRONT REAR
Real-life Examples: Bank queues, toll booths, queue at petrol pump
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
A processor can handle only one task at a time. Therefore, in a multitasking
operating system, jobs are queued and then given access to the processor
according to FIFO basis.
3. Printer Queue Management
If multiple print requests are sent to a shared printer: The first print command
sent is executed first and remaining ones wait in the print queue.
Operations on Queue
enqueue() Inserts an element at the rear end
If the Queue is full, it results in Overflow Exception.
dequeue() Removes an element from the front of the queue.
Deleting an element from an empty Queue results in Underflow
Exception.
isEmpty() Check if queue is empty.
to avoid Underflow exception while performing dequeue operation.
isFull() Check if queue is full (not required in Python list-based queue).
peek() View the front item of the Queue
Implementation of Queue using Python
1. Create a Queue by assigning an empty list
q = list()
2. enqueue
append() function adds an element to the rear end of the queue.
def enqueue():
queue.append(element)
3. dequeue() function is used to delete an element from the front of the queue.
pop() function with index[0] will delete the element from the beginning of the
list (front of queue ).
def dequeue():
if q == []:
print(“Queue is empty”)
else :
print(“Queue is empty” , queue.pop(0))
4. size() - It returns the Queue size
def size(queue):
return len(queue)
5. peek()
The peek function is to read the element at the front end of the queue.
def peek():
if q == [] :
print('Queue is empty')
else:
print(“peak element is ”,q[0])
6. Display all elements (from TOP to bottom)
def display_queue():
if q == []:
print("Queue is empty.")
else:
print("Queue elements are :", q)
Deque (Double Ended Queue)
A Deque is a data structure that allows for adding and removing elements from
both ends.
It 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
Re-entry at Ticket Counter, Toll Booth Queue Redirection
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
But to manage multiple undo/redo and limited memory, deque provides
efficient handling.
3. Palindrome Checking – Deque can be used to check if a word is in palindrome
or not.
Operations on DeQue
INSERTFRONT() insert a new element at the front of the queue
DELETIONFRONT( removes an element from the front of the queue.
)
INSERTREAR() insert a new element at the rear of the queue
DELETIONREAR() removes an element at the rear of the queue
Implementation of Deque using Python
1. Create a Queue by assigning an empty list
myDeque = list()
2. insertFront function is used to insert a new element at the front of queue.
It has two parameters - name of the queue and element to be inserted.
insert() function is used to add element in the begining
def insertFront(myDeque, element):
myQue.insert(0,element)
3. insertRear() - is used to insert an element at the rear of the deque. Its
implementation is same as enQueue()
def insertRear(myDeque, element):
myDeque.append(element)
4. isEmpty() – This function is used to check, if the queue has an element or not.
This can be done by checking the length of the queue.
It has a parameter - name of the queue.
It returns True if the queue is empty otherwise it returns False.
def isEmpty(myDeque):
if len(myDeque)==0:
return True
else:
return False
5. deleteRear() - This function is used to delete an element from the rear of the
deque.
It only requires the name of deque and returns the deleted element.
pop() without parameter deletes the last element of the deque.
def deleteRear(myDeque):
if isEmpty(myDeque):
print("Deque empty")
else:
return myDeque.pop()
6. deleteFront() - This function is used to delete an element from the front of the
deque.
It only requires the name of deque and returns the deleted element.
pop() without parameter deletes the first element of the deque.
def deleteFront(myDeque):
if isEmpty(myDeque):
print("Deque empty")
else:
return myDeque.pop(0)
7. getFront() – This function has one parameter name of the queue and returns the
element at the front of the queue if queue is not empty.
def getFront(myDeque):
if isEmpty(myDeque):
print("Queue empty")
else:
return myDeque[0]
8. getRear() – This function has one parameter name of the queue and returns the
element at the rear end of the queue if queue is not empty.
def getRear(myDeque):
if isEmpty(myDeque):
print("Queue empty")
else:
return myDeque[-1]
