COMPUTER SCIENCE

Chapter 4
QUEUE
Data structure
Data structure defines a mechanism to store, organize and access data along with operations
(processing) that can be efficiently performed on the data.
Eg: String, List, set, tuple, stack, queue, Array, Linked List, Binary Trees, Heaps, Graph, Sparse
Matrix ….
A data structure in which elements are organised in a sequence is called linear data structure.

QUEUE
QUEUE is a linear data structure where an element is inserted at one end(REAR end) and an
element is deleted from the other end(FRONT end)
It follows FIFO-First In First Out or LILO-Last In Last Out principle.

APPLICATIONS OF QUEUE
Real life applications
• Train ticket is in waiting list
Train ticket in the waiting list in a queue to get confirmed will be confirmed if a
confirmed ticket is cancelled. The wL1 is removed from Front end of the queue and
confirmed.

• Customer service call centre

The interactive voice service system tell us to wait till support person is available. Here
the calls are put into a queue waiting to be served. Customers are served in FIFO
concept.

• Vehicles Queue in single lane one way road

Here the vehicle that entered first will exit first following the concept of
[Link],
• Vehicles in a highway toll tax booth
• Cars in petrol pump
• Queue of people at bank

Computer science applications

• Webserver hosting website to declare results
To serve huge number of user requests,Queue data structure is used to serve the users
in FCFS(First Come First Serve) concept

1
 COMPUTER SCIENCE

• Multitasking systems jobs are in queue waiting for processor

Here multiple jobs are required to be handled by a single [Link] jobs are lined
up and then given access to the processor according to the order of jobs arrived with
request for processor (FIFO basis)

• Print requests from multiple systems to a single printer

If the Printer is shared by multiple systems,the OS puts print requests from different
systems in a queue and sends them to the printer one by one on FIFO basis.

Operations on Queue
• ENQUEUE
Operation used to insert a new element to the rear end of the queue
Inserting elements beyond capacity of the queue will result in Overflow
exception
• DEQUEUE
Operation used to remove an element from the front end of the queue
Trying to delete an element from an empty queue will result in Underflow
exception
Note:
1. Front end is also called as Head
2. Rear end is also called as Tail

Operations required To perform enqueue and dequeue efficiently

• IS EMPTY
Used to check whether the queue has any element or not
Used to avoid Underflow exception while performing dequeue operation.
• PEEK
Used to view elements at the front end of the queue, without removing it from the queue
• IS FULL
Used to check whether any more elements can be added to the queue or not
Used to avoid Overflow exceptions while performing enqueue operation

Implementation of Queue in Python

QUEUE can be implemented using the datatype list
One side of the list can be considered as REAR to insert elements and another side of the list
can be considered as FRONT to remove elements
QUEUE can be implemented using built-in methods append() and pop() of the list

2
 COMPUTER SCIENCE

Write an algorithm to
1. Create a QUEUE
2. Check if the QUEUE is empty
3. Insert an element into the QUEUE
4. Find the number of elements in the QUEUE
5. Read the value at the front end of the QUEUE
6. Delete an element from the front end of the QUEUE
7. Show the content of the QUEUE
Q - Name of the QUEUE
n - size of the QUEUE
n-1 – index of the element at the rear end of the QUEUE

1. Create a QUEUE
It creates an empty list.
Q = list()

2. Check if the QUEUE is empty

isEmpty() returns True if the QUEUE is empty, else returns False
len(Q ) returns number of elements in the Q.
def isEmpty(Q):
if len(Q)==0:
return True
else:
return False

3. Insert an element into the rear end of the QUEUE

enqueue() inserts an element at the rear end of the QUEUE
append() to insert an element at the rear end of the QUEUE
def enqueue(Q, ele):
[Link](ele)

Note:There is no limit on size of list in Python. So the QUEUE will never be full unless
there is no space available in memory. So we will never face overflow condition for
QUEUE.

4. Find the number of elements in the QUEUE

Size() returns the number of elements in the QUEUE
len() - To find the size of the list/QUEUE
def size(Q):
return len(Q)
3
 COMPUTER SCIENCE

5. Read the value at the front end of the QUEUE

peek() is used to return the value at the front end of the QUEUE.
def peek(Q):
if isEmpty(Q):
print('Queue is empty’)
return None
else:
return Q[0]

6. Delete an element from the front end of the QUEUE

dequeue() checks whether the queue is empty or not. If it is not empty, it removes the
element present at the front end of the QUEUE
pop(0) - Removes the 0th (front end) element from the queue
def dequeue(Q):
if (isEmpty(Q)):
print(“Queue is empty”)
return None
else :
return [Link](0)

7. Show the content of the QUEUE

display() prints all the elements of the QUEUE
def display(Q):
print(“Elements of the queue”)
for ele in Q:
print (ele)

4
 COMPUTER SCIENCE

Deque(Double Ended Queue)

• It is a linear arrangement of elements, in which addition and removal of elements
can happen from any end(front/head or rear/tail)
• Pronounced as deck
• This data structure can be used to implement stack or queue

Operations on Deque
• INSERTREAR
This operation is used to insert new element at the rear of the deque, same as normal
queue
• DELETIONFRONT
This operation is used to remove an element from the front of the deque, same as normal
queue
• INSERTFRONT
This operation is used to insert new element at the front of the deque
• DELETIONREAR
This operation is used to remove an element from the rear of the deque

Operations required To perform

INSERTREAR,INSERTFRONT,DELETIONREAR,DELETIONFRONT
• ISEMPTY ()
Used to check whether the deque has any element or not
Used to avoid Underflow exception while performing dequeue operation.
• getRear()
It is used to read value from the rear of the deque, without removing it from the deque.
• getFront()
It is used to read value from the front of the deque, without removing it from the deque.
• ISFULL()
Used to check whether any more elements can be added to the dequeue or not
Used to avoid Overflow exceptions while performing enqueue operation
• SIZE()
Used to count the elements present in the deque
Implementation of Deque(Double Ended Queue)
DEQUE can be implemented using the datatype list
Addition and removal of elements can happen from any end(front/head or rear/tail)
DEQUE can be implemented using built-in methods insert(), append() and pop() of the list
5
 COMPUTER SCIENCE

Write an algorithm to
1. Create a DEQUE
2. Check if the DEQUE is empty
3. Insert an element at front end of the DEQUE
4. Delete an element from the rear end of the DEQUE
5. Insert an element at rear end of the DEQUE
6. Delete an element from the front end of the DEQUE
7. Read the value at the rear end of the DEQUE
8. Delete an element from the front end of the DEQUE
9. Find the number of elements in the DEQUE
10. Show the content of the DEQUE
DQ - Name of the DEQUE
n - size of the DEQUE
n-1 – index of the element at the rear end of the DEQUE
0 - index of the element at the front end of the DEQUE

[Link] a DEQUE
It creates an empty list.
DQ=list()

[Link] if the DEQUE is empty

isEmpty() returns True if the DEQUE is empty, else returns False
len(DQ ) returns number of elements in the DQ.

def isEmpty(DQ):
if len(DQ)==0:
return True
else:
return False

[Link] an element at front end of the DEQUE

insertFront() inserts an element at the rear end of the QUEUE
insert() to insert an element at the front end of the QUEUE

def insertFront(DQ, ele):

[Link](0,ele)

[Link] an element from the rear end of the DEQUE

deletionRear() checks whether the queue is empty or not. If it is not empty, it removes the
element present at the rear end of the QUEUE
6
 COMPUTER SCIENCE

pop() - Removes the (n-1)th (rear end) element from the queue

def deletionRear(DQ):
if (isEmpty(DQ)):
print(“Deque empty”)
else:
return [Link]()

5. Insert an element at rear end of the DEQUE

insertRear() inserts an element at the rear end of the QUEUE
append() to insert an element at the rear end of the QUEUE

def insertRear(DQ, ele):

[Link](ele)

[Link] an element from the front end of the DEQUE

deletionFront() checks whether the queue is empty or not. If it is not empty, it
removes the element present at the front end of the QUEUE
pop(0) - Removes the 0th (front end) element from the queue

def deletionFront(DQ):
if (isEmpty(DQ)):
print(“Queue is empty”)
return None
else :
return [Link](0)

7. Read the value at the rear end of the DEQUE

It is used to read value from the rear of the deque, without removing it from the deque.

def getRear(DQ):
if (isEmpty(DQ)):
print(“ Deque empty”)
else:
return DQ[len(DQ)-1]

8. Read the value at the front end of the DEQUE

It is used to read value from the front of the deque, without removing it from the deque.

7
 COMPUTER SCIENCE

def getFront(DQ):
if isEmpty(DQ):
print(“ Queue empty”)
else:
return DQ[0]

9. Find the number of elements in the DEQUE

Used to return the number of elements present in the deque

def size(DQ):
return len(DQ)

[Link] the content of the DEQUE

display() prints all the elements of the QUEUE

def display(DQ)
print(“Elements of the queue”)
for ele in DQ:
print (ele)

Applications of Deque in real life

• Re entry at train ticket purchasing counter
In a queue of people a person at the front purchased the ticket and left the counter.
After a while they return back to the counter to ask something. As he has already
purchased a ticket, he may have the privilege to join the queue from the front end of
the queue.
• Vehicles in a highway toll booth queue redirection are served following the principle
of queue. There are multiple queues if there are parallel booths at the toll gate. In case
all vehicles of a booth are served then vehicles from the other booth(s) are asked to
form a queue in front of the vacant booth. So, vehicles at the end of those queues will
leave (removed from the end from where queue was joined) current booth and join
queue at the vacant booth.
Applications of Deque in computer science
• To maintain the browser history(URL),stack is [Link] after tab is closed ctrl+shift+T
opens the recently visited URL(POP).If list of URL exceeds the limit, URL from the end
of the list(Least visited)gets deleted(dequeue)
• DO and UNDO operations in text editor
• To check whether the string is palindrome or not
• Read the characters of the string from left to right
8
 COMPUTER SCIENCE

• Insert characters in Deque from rear end

• After all the characters are inserted, remove the characters from both the
ends(one from front and one from rear end) and match them until Deque is
empty or left with only 1 character. In either case string is palindrome
•

Assignment
1. Mention the other names of the QUEUE. Give reason
2. Explain the different operations on QUEUE data structure
3. Mention the real life applications of QUEUE data structure
4. Explain the programming applications of QUEUE data structure
5. Explain the different operations on DEQUE data structure
6. Mention the real life applications of DEQUE data structure
7. Explain the programming applications of DEQUE data structure
8. Define DEQUE,DEQUEUE
9. Write an algorithm to check whether sting is palindrome or not and explain with an
example

9
 COMPUTER SCIENCE

10. Write a program to,

i. Insert an element into the QUEUE
ii. Delete an element from the QUEUE
iii. Insert an element into the front end of DEQUE
iv. Insert an element into the rear end of DEQUE
v. Delete an element from the front end of DEQUE
vi. Delete an element from the rear end of DEQUE
vii. Find the number of elements in the QUEUE
viii. Read the value of the REAR and FRONT element in the QUEUE

10