Chapter- 4
Queue
4.1 Introduction to queue
4.2 operations of queue
4.3 Implementation of queue using python
4.4 Introduction to dequeue
4.5 Implementation of deque using python
4.1 Introduction to queue
Definition: A queue is a linear data structure that stores
elements in a sequence and processes them in the FIFO (First
In, First Out) order.
✓ This means the first element inserted into the queue will
be the first one removed.
Structure of Queue: 2 marks
Real-life Examples:
✓ People waiting in line at a ticket counter.
✓ Vehicles at a toll booth.
✓ Tasks waiting to be printed in a printer queue.
Important Features:
✓ Elements are added at the rear (also called tail).
✓ Elements are removed from the front (also called head).
✓ Maintains the order of arrival.
Why use a queue?
✓ To handle tasks in the order they arrive.
✓ Useful in scheduling problems, CPU task management, and
data transfer.
Queue Characteristics:
✓ FIFO principle – First element inserted is the first
removed.
✓ Two ends – Front (deletion) and Rear (insertion).
✓ Linear structure – Elements are stored in a line.
4.2 Operations on Queue
✓ A queue supports several basic operations to manage data.
✓ It follows the FIFO rule — First In, First Out.
[Link]
[Link]
5 marks
[Link]
[Link]
5.Is_empty
6.Is_full
Enqueue operation
✓ It is used to inserting or adding an element into the
queue.
✓ The method is used to implementing a program is
[Link](x)
✓ Ex:
queue=[]
[Link](10)
[Link](20)
[Link](30)
print(queue)
output
[10,20,30]
dequeue operation
✓ It is used to deleting or removing an element from the
queue.
✓ The method is used to implementing a program is
[Link]()
✓ Ex:
queue =[]
[Link](10)
[Link](20)
[Link](30)
[Link]()
[Link]()
print(queue)
output
[10]
peek operation
✓ Display the element at the front without removing it.
✓ The method is used to implementing a program is queue[0]
✓ Ex:
queue=[]
[Link](10)
[Link](20)
[Link](30)
print(queue[0])
output
[30]
Display operation
✓ It returns all elements from the queue.
✓ The method is used to implementing a program is queue
✓ Ex:
queue=[]
[Link](10)
[Link](20)
[Link](30)
print(queue)
output
[10,20,30]
Is_empty operation
✓ Its check whether the queue is empty OR not.
✓ The method is used to implementing a program is
len(queue)==0
✓ Ex:
queue=[]
if len(queue)==0:
print (“queue is empty or underflow”)
else:
print (“queue elements:”, queue)
output
queue is empty or underflow
Is_Full operation
✓ Its check whether the queue is Full OR not.
✓ The method is used to implementing a program is
len(queue)
✓ Ex:
Size=3
queue=[]
[Link](10)
[Link](20)
[Link](30)
if len(queue)==3:
print (“queue is full or overflow”)
else:
print (“queue elements:”, queue)
output
queue is full or overflow
Implementation of queue in python
Program:
queue=[]
[Link](10) Practical
print("enqueue operation :10")
[Link](20)
print("enqueue operation :20")
[Link](30)
print("enqueue operation:30"
print("stack elements are:”, queue)
print("peek elements :", queue[0])
print("dequeue operation:”, [Link]())
print("dequeue operation:”, [Link]())
print("dequeue operation:”, [Link]())
if len(queue)==0:
print("queue is empty or underflow")
else:
print("queue elements:",queue)
output
enqueue operation : 10
enqueue operation : 20
enqueue operation : 30
queue elements are: [10, 20, 30]
peek elements : [30]
dequeue operation: [30]
dequeue operation: [20]
dequeue operation: [10]
queue is empty or underflow
4.4 Introduction to Deque
Definition: 2 marks
✓ A Deque stands for Double-Ended Queue.
✓ It is a linear data structure that allows insertion and
deletion of elements from both ends — front and rear.
Key Features:
1. Insertion at both ends: You can add elements at the front
or rear.
2. Deletion at both ends: You can remove elements from the
front or rear.
3. More flexible than a normal queue: Normal queues only allow
insertion at the rear and deletion at the front.
4. Can work as:
✓ Queue (FIFO)
✓ Stack (LIFO)
✓ Or a combination of both.
Types of Deque:
1. Input-Restricted Deque
✓ Insertion is allowed at only one end.
✓ Deletion is allowed from both ends.
2. Output-Restricted Deque
✓ Deletion is allowed at only one end.
✓ Insertion is allowed from both ends.
Real-Life Examples
✓ Browser history navigation (you can go forward and
backward).
✓ Editing playlists (add/remove songs from start or end).
✓ Undo/redo operations in text editors.
OPERATIONS OF DEQUE
1. Insertion at rear
2. Insertion at front
3. Deletion at rear
4. Deletion at front
5. Peek at front
6. Peek at rear
7. Display
Insertion at Rear
✓ Inserting an element at the rear end of the deque.
✓ The method is used for implementing a program is
[Link](x)
✓ Example:
from collections import deque
dq=deque()
[Link](10)
[Link](20)
print(dq)
output
[10,20]
Insertion at Front
✓ Inserting an element at the front end of the deque.
✓ The method is used for implementing a program is
[Link](x)
✓ Example:
from collections import deque
dq=deque()
[Link](10)
[Link](20)
print(dq)
output
[20,10]
Deletion at Rear
✓ Deleting an element from the rear end of the deque.
✓ The method is used for implementing a program is
[Link]()
✓ Example:
from collections import deque
dq=deque()
[Link](10)
[Link](20)
[Link]()
print(dq)
output
[10]
Deletion at Front
✓ Deleting an element from the front end of the deque.
✓ The method is used for implementing a program is
[Link]()
✓ Example:
from collections import deque
dq=deque()
[Link](10)
[Link](20)
[Link]()
print(dq)
output
[20]
peek at Rear
✓ It returns the rear most element of the deque.
✓ The method is used for implementing a program is dq[-1]
✓ Example:
from collections import deque
dq=deque()
[Link](10)
[Link](20)
[Link](20)
print(dq[-1])
output
[30]
peek at Front
✓ It returns the front most element of the deque.
✓ The method is used for implementing a program is dq[0]
✓ Example:
from collections import deque
dq=deque()
[Link](10)
[Link](20)
[Link](30)
print(dq[0])
output
[10]
Display
✓ It returns all the elements of the deque.
✓ The method is used for implementing a program is dq
✓ Example:
from collections import deque
dq=deque()
[Link](10)
[Link](20)
[Link](30)
print(dq)
output
[10,20,30]
4.5 Implementation of deque using python
From collections import deque
dq=deque()
[Link](10)
print("insertion :10")
[Link](20)
print("enqueue operation :20")
[Link](30)
print("enqueue operation:30"
print("stack elements are:”, queue)
print("peek elements :", queue[0])
print("dequeue operation:”, [Link]())
print("dequeue operation:”, [Link]())
print("dequeue operation:”, [Link]())
if len(queue)==0:
print("queue is empty or underflow")
else:
print("queue elements:",queue)