II PUC 2025-26 (New syllabus) Computer Science Chapter 4 Queue
Chapter 4 Queue
Introduction to Queue
Queue is an ordered linear list of elements, having different ends for adding and removing elements in it.
Example:
1) Jobs waiting in a queue to be executed by CPU.
2) Students standing in a queue for morning assembly,
First In First Out (FIFO)
Queue follows the principle of First In First Out (FIFO).
This means the element entering first in the queue will be the first one to come out of it.
It is also known as a First Come First Served (FCFS) approach.
Rear end:
It is the end in the queue where new objects/items are added to the queue.
It is also known as tail of queue.
Front end
It is the end in the queue where objects/items are removed from the queue.
It is also known as head of queue.
Applications of Queue
a) Applications in real-life:
Waiting list queue in train ticket booking.
Customer waiting queue in IVRS (Interactive Voice Response System) system in customer service center.
Vehicle queue in a single lane road.
Vehicle queue in a toll tax booth on highways.
Customers forming a queue at the cash counter in a bank.
b) Application of queue in computer science:
A web-server hosting a web site to declare exam result uses queue to serve thousands of user requests.
As processor can handle only one task at a time, multitasking operating systems use queue to execute jobs.
When multiple print commands are generated in shared printer, the OS puts these print requests in a queue and sends them
to the printer one by one on a FIFO basis.
Scheduling algorithms in OS like FCFC, SJF, RR, priority scheduling are implemented using queues.
Queues are used in network protocols like TCP and UDP to manage the flow of data packets.
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 1
II PUC 2025-26 (New syllabus) Computer Science Chapter 4 Queue
Operations on Queue
ENQUEUE:
It is the operation to insert a new element to the queue at the rear end.
User can insert elements in the queue until there is space in the queue.
Inserting elements beyond capacity of the queue will result in an exception called as Overflow.
DEQUEUE:
It is the operation to remove one element at a time from the front of the queue.
We can delete elements from a queue until it is empty.
Deleting an element from an empty queue will result in exception called as Underflow.
IS EMPTY :
It is the operation to check whether the queue has any element or not.
It is used to avoid Underflow exception while performing dequeue operation.
IS FULL:
Used to check whether any more elements can be added to the queue or not.
This is used to avoid Overflow exceptions while performing enqueue operation.
PEEK: Used to view elements at the front of the queue, without removing it from the queue.
Implementation of Queue using Python
One way to implement queue is using the list data type of Python.
While using a list to implement queue, we can designate either end of the list as Front or Rear of the queue. But we have to fix
either of the ends index [0] or index [n-1] as Front and fix the opposite end as Rear.
Following functions are used in implementing queue
1) Function to create a queue structure using empty list
myQueue = list( )
Here myQueue is name of queue.
2) enqueue ( ) function:
This function inserts a new element at the rear end of queue.
The function has two parameters - name of the queue and element to be inserted.
append() function always adds an element at the end of the list (Rear of queue).
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 2
II PUC 2025-26 (New syllabus) Computer Science Chapter 4 Queue
def enqueue(myQueue, element):
myQueue.append(element)
3) isempty ( ) function:
This function checks, if the queue has an element or not.
This can be done by checking the length of the queue. If length is 0, then queue is empty.
The function has one parameter name of the queue.
This function returns True if the queue is empty, and returns False if queue in not empty.
def isEmpty(myQueue):
if len(myQueue)==0:
return True
else:
return False
4) dequeue ( ) function:
This function deletes an element from the front of the queue.
It has one parameter - name of the queue.
This function returns the deleted element.
The function first checks if the queue is empty or not, for successful deletion.
def dequeue(myQueue):
if not (isEmpty(myQueue)):
return myQueue.pop(0)
else :
print(“Queue is empty”)
Here, The pop() function with index[0] will delete the element from the beginning of the list.
5) size( ) function:
This function returns the number of elements in the queue.
len ( ) function of Python’s list is used to find the number of elements in the queue.
The function has one parameter - name of the queue
def size(myQueue):
return len(myQueue)
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 3
II PUC 2025-26 (New syllabus) Computer Science Chapter 4 Queue
6) peek ( ) function:
This function is used to read the element at the front end of the queue, but does not delete it.
This function reads the element at index [0] of the queue/list.
This function has one parameter - name of the queue.
This function returns the element at Front end if queue is not empty and none otherwise.
def peek(myQueue):
if isEmpty(myQueue):
print('Queue is empty')
return None
else:
return myQueue[0]
Note:
No need to implement function for Is Full, as Python is a dynamic language.
Python does not ask for the creation of list having fixed size.
Hence, user never encounter a situation when the queue is full.
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 4
II PUC 2025-26 (New syllabus) Computer Science Chapter 4 Queue
Deque queue
It is queue/data structure in which addition and removal of elements can be done from any end, i.e. head/front or tail/rear.
There is no restriction on the side from which addition/removal of elements should happen.
It can be used to implement stack or queue in the program.
It is also known as Double ended queue, because it permits insertion, deletion operations from any end.
Applications of Deque in real life
In a train ticket counter a passenger have the privilege to join the queue from the front, after they purchased a ticket.
A highway toll tax booth has multiple queues, if one queue is empty, then vehicles form other queue can join the vacant queue
by exiting from the back of the queue.
Applications of Deque in computer science
To maintain browser history (URL) in a web browser.
Do and Undo option in any text editor.
To check whether a given string is palindrome or not.
Operations on Deque
INSERTFRONT: This operation is used to insert a new element at the front of the deque.
INSERTREAR: This operation is the same as a normal queue, i.e. insert a new element at the rear of the deque.
DELETIONFRONT: This operation is the same as normal queue, i.e. to remove an element from the front of the deque.
DELETIONREAR: This operation is used to remove one element at a time from the rear of the deque.
To perform above operations on a deque, user needs all supporting operations used in normal queue like Is Empty, Peek, Size.
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 5
II PUC 2025-26 (New syllabus) Computer Science Chapter 4 Queue
Algorithm to check a string is palindrome or not using deque queue.
Step1: Start traversing string (madam) from left side, one character at a time.
Step 2: Insert the character in deque as normal queue using INSERTREAR.
Step 3: Repeat Step 1 and Step 2 for all characters of string (madam)
Step 4: Remove one character from the front and one character from the rear end of deque using DELETIONFRONT and
DELETIONREAR.
Step 5: Match these two removed characters.
Step 6: If they are same then repeat Step 4 and 5 till deque is empty or left with only one character,
Step 7: if there in only one character deque then string is palindrome, else string is not palindrome
Implementation of Deque Using Python
Python list data type is used to create deque in program.
The program should have the following functions/ statement(s) defined in it.
1) A statement to create deque, with name myDeque.
myDeque = list( )
2) insertFront () function:
This function is used insert an element at the front of deque.
This function has two parameters - name of deque and element to be inserted.
As the element is to be inserted in the beginning, we will use insert ( ) function with index 0 for it.
def insertFront(myDeque, element):
myDeque.insert(0,element)
3) insertRear() function:
This function inserts an element at the rear of deque.
Its implementation will be the same as enqueue ( ) of normal queue.
This function requires two parameters name of deque and element to be inserted.
4) isEmpty( ) function:
This function checks whether there are elements in deque or not.
This can be done by checking the length of the deque. If length is 0, then deque is empty.
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 6
II PUC 2025-26 (New syllabus) Computer Science Chapter 4 Queue
5) deletionRear( ) function:
This function deletes an element from the rear of the deque.
It requires the name of deque and returns the deleted element.
pop() function without parameter is used to delete the last element of the deque.
def deletionRear(myDeque):
if not (isEmpty()):
return myDeque.pop() # removing data from end of list
else :
print(“Deque empty”)
6) deletionFront( ): This function deletes an element from the front of deque.
7) getFront( ) function
This function reads value from the front of deque, without removing it when the queue is not empty.
It accepts the name of deque as parameter and returns a copy of value.
def getFront(mydeque):
if not (isEmpty()):
return mydeque[0]
else :
print(“ Queue empty”)
8) getRear( ) function:
This function reads a value from the rear of the deque, without removing it from the deque.
The function accepts deque as argument and returns a copy of value, when the queue is not empty.
def getRear(mydeque):
if not (isempty()):
return mydeque[len(mydeque)-1]
else :
print(“ Deque empty”)
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 7
