CHAPTER 4 : QUEUE
INTRODUCTION TO QUEUE
Queue is an ordered linear list of elements, having different
ends for adding and removing elements in it.
First In First Out (FIFO)
Queue follows the principle of First In First Out (FIFO),
since 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.
Queue is an arrangement in which new items always
get added at one end, usually called the REAR. REAR
is also known as TAIL.
In Queue, items always get removed from the other
end, usually called the FRONT of the queue. FRONT is
also known as HEAD.
Applications of Queue in real life
Sometimes on calling a customer service centre, the
Interactive Voice Response System (IVRS) tells us to wait
till a support person is available. Here the call is put into a
queue of customers waiting to be serviced.
People will wait in queue at ATM to withdraw/deposit
money.
Vehicles are in queue at vehicle service station for servicing.
Applications of Queue in computer
Printer queue: As multiple users request for a printer, then all
the requests are kept in a queue and service is based on First
In First Out Order.
Web Server: Web Server use queue to manage incoming
requests from clients.
Task Scheduling: Queue can be used to schedule tasks based
on priority or the order in which they were received.
Resource Allocation : Queue can be used to manage and
allocate resources, such as printers or CPU processing time.
Operating System : Operating System often use queue to
manage processes and resources.
OPERATIONS ON QUEUE
ENQUEUE: is used to insert a new element to the queue at the rear
end. Inserting elements beyond capacity of the queue will result in
an exception - known as Overflow.
DEQUEUE: is used to remove one element at a time from the front
of the queue. We can delete elements from a queue until it is empty,
trying to delete an element from an empty queue will result in
exception - known as Underflow.
IS EMPTY: used to check whether the queue has any element or
not, as to avoid Underflow exception.
PEEK: used to view elements at the front 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, to avoid Overflow exceptions.
IMPLEMENTATION OF QUEUE USING PYTHON
Queues can be implemented in a computer program, one way is
using the list data type of Python.
Let’s create a queue named Queue.
Queue = list()
A function (enqueue) to insert a new element at the end
of queue. The function has two parameters- name of the queue
and element which is to be inserted in the queue.
def enqueue(Queue, element):
Queue.append(element)
Note: append() function always adds an element at the end of the
list, hence Rear of queue.
We don’t need to implement Is Full, as Python being a
dynamic structure. Thus,there is no situation when the queue
is full.
A function (isEmpty) to check, if the queue has an element or
not. This can be done by checking the length of the queue.
The function has a parameter - name of the queue and
returns True if the queue is empty False otherwise.
def isEmpty(Queue):
if len(Queue)==0:
return True
else:
return False
• A function (dequeue) to delete an element from the front of the
queue. It has one parameter - name of the queue and returns
the deleted element. The function first checks if the queue is
empty or not, for successful deletion.
def dequeue(Queue):
if not (isEmpty(Queue)):
return Queue.pop(0)
else:
print(“Queue is empty”)
Note: The pop() function with index[0] will delete the element from the
beginning of the list, hence Front of queue.
A function (size) to get the number of elements in the queue.
We can use the len() is to find the number of elements in the
queue. The function has one parameter - name of the queue
and returns the number of elements in the queue.
def size(Queue):
return len(Queue)
A function (peek) is to read,the element at the front end of
the queue. For this, we can read the element at index[0] of
the queue. The function has one parameter - name of the
queue and returns the value of element at Front if queue is not
empty, None otherwise.
def peek(Queue):
if isEmpty(Queue):
print('Queue is empty')
return None
else:
return Queue[0]
INTRODUCTION TO DEQUE
Deque (pronounced as “deck”) is an arrangement in which
addition and removal of element(s) can happen from any end,
i.e. head/front or tail/rear.
It is also known as Double ended queue, because it permits
insertion, deletion operations from any end.
Applications of Deque
Storing a web brower’s history.
Undo/Redo 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 an
element from the front of the deque.
INSERT REAR: This operation is used to insert a new
element at the rear of the deque.
DELETION FRONT: This operation is used to delete
an element from the front of the deque.
DELETION REAR: This operation is us e d t o delete
an element from the rear of the deque.
Algorithm to check whether a string is a palindrome or not
using a deque.
Step1: Start traversing string (madam) from left side, a
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
a n d D E L E T I O N R E A R w e c a n do it.
Step 5: Match these two removed characters.
Step 6: If they are same then,
Then repeat steps 4 and 5 till deque is empty
or left with only one character, eventually string is a
palindrome.
Else
Stop as string is not a palindrome.
IMPLEMENTATION OF DEQUE USING PYTHON
Like queue, deque is also an ordered linear list, hence we use
list data type to create deque in our program.
A statement to create deque, with name Deque.
Deque = list()
A function insertFront(), to insert an element at the
front of deque having two parameters - name of deque
and element to be inserted. As the element is to be
inserted in the beginning, we will use insert() with index
0 for it.
def insertFront(Deque, element):
Deque.insert(0,element)
A function insertRear(), to insert an element at the rear
of deque. It’s implementation will be the same as
enqueue() of normal queue requiring two parameters
same as insertFront().
A function isEmpty(),used to check whether deque is
empty or not.
A function deletionRear(), to delete an element from
the rear of the deque. It only requires the name of
deque and returns the deleted element. We will use
pop() without parameter(s) to delete the last element
of the deque.
def deletionRear(Deque):
if not (isEmpty()):
return myDeque.pop()
# removing data from end of list
else :
print(“Deque empty”)
A function deletionFront(), to delete an element from
the front of deque. It’s implementation will be the
same as dequeue() of normal queue.
A function getFront(), to read value from the front of
deque, without removing it from the queue when the
queue is not empty. It accepts the name of deque as
parameter and returns a copy of value.
def getFront(deque):
if not (isEmpty()):
return deque[0]
else:
print(“ Queue empty”)
A function getRear(), to read 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(deque):
if not (isempty()):
return deque[len(deque)-1]
else:
print(“ Deque empty”)
