QUEUE

Visit for more Learning Resources

Free Powerpoint Templates

Page 1
 Queue

Free Powerpoint Templates

Page 2
 Queue
• Ordered collection of homogeneous elements
• Non-primitive linear data structure.
• A new element is added at one end called rear end and the
existing elements are deleted from the other end called
front end.
• This mechanism is called First-In-First-Out (FIFO).

e.g. People standing in Queue for Movie Ticket

Free Powerpoint Templates

Page 3
Fig: Model of a Queue

Free Powerpoint Templates

Page 4
Queue as ADT(abstract data type.)

• Queue is a data structure which allows a programmer to

insert an element at one end known as “Rear” and to
delete an element at other end known as “Front”.
• Queue is an abstract data type because it not only allows
storing a elements but also allows to perform certain
operation on these elements.

Free Powerpoint Templates

Page 5
Queue as ADT(abstract data type.)

• These operations are as follows.

– Initialize()
– enqueue()
– dequeue()
– Isempty()
– Isfull()
– Display()

• Elements of queue:-
– Front
– Rear
– array

Free Powerpoint Templates

Page 6
 Elements of queue:-
• Front: -
– This end is used for deleting an element from a queue.
Initially front end is set to -1. Front end is incremented
by one when a new element has to be deleted from
queue.
Rear: -
This end is used for inserting an element in a
queue. Initially rear end is set to -1. rear end is incremented
by one when a new element has to be inserted in queue.

Free Powerpoint Templates

Page 7
Algorithm to insert element
(enqueue Operation)
• Step 1: [check queue full condition]
if rear = max -1 then write “queue is full”
otherwise go to step 2
• Step 2: [increment rear point]
rear = rear + 1
• Step 3: [insert element]
q [rear] = Data
• Step 4: [check front pointer]
if front = -1 then assign front =0
• Step 5: End

Free Powerpoint Templates

Page 8
Algorithm to delete element
(dequeue Operation)
• Step 1: [check queue empty condition]
if front = -1 then write “queue is empty”
otherwise go to step 2
• Step 2: [copy data]
Data = q[front]
• Step 3: [check front and rear pointer]
if front = rear then
front = rear = -1
otherwise
front = front + 1
• Step 4: end

Free Powerpoint Templates

Page 9
Front=-1 Front=1
Queue is empty Delete

1 5 B C
0 1 2 3 4 0 1 2 3 4
Rear=-1 Rear=2
Insert A Delete
Front=0 Front=2

2 A 6 C
0 1 2 3 4 0 1 2 3 4
Rear=0 Rear=2
Front=0 Insert B Front=3 Delete

3 A B 7

0 1 2 3 4 0 1 2 3 4
Rear=1 Rear=2 Queue is empty
Front=0 Insert C
Entry point is called Rear &
4 A B C
Exit point is called Front
0 1 2 3 4
Rear=2 10
‘Queue Full(Overflow)’ Condition
• Queue Full(Overflow):
– Inserting an element in a queue which is already full is known as
Queue Full condition (Rear = Max-1).
– When the queue is fully occupied and enqueue() operation is called
queue overflow occurs.

• Example: Queue Full:

– Before inserting an element in queue 1 st check whether space is
available for new element in queue. This can be done by checking
position of rear end. Array begins with 0th index position & ends
with max-1 position. If numbers of elements in queue are equal to
size of queue i.e. if rear end position is equal to max-1 then queue is
said to be full. Size of queue = 4

Free Powerpoint Templates

Page 11
‘Queue Empty(Underflow)’ Condition

• Queue Empty:
– Deleting an element from queue which is already empty is known
as Queue Empty condition (Front = Rear = -1)
– When the queue is fully empty and dequeue() operation is called
queue underflow occurs.

–
• Queue Empty:
– Before deleting any element from queue check whether there is an
element in the queue. If no element is present inside a queue &
front & rear is set to -1 then queue is said to be empty.
– Size of queue = 4
– Front = Rear = -1

Free Powerpoint Templates

Page 12
Disadvantages of linear queue

• On deletion of an element from existing

queue, front pointer is shifted to next
position.
• This results into virtual deletion of an
element.
• By doing so memory space which was
occupied by deleted element is wasted
and hence inefficient memory utilization
is occur.

Free Powerpoint Templates

Page 13
Overcome disadvantage of linear queue:

• To overcome disadvantage of linear queue,

circular queue is use.
• We can solve this problem by joining the front
and rear end of a queue to make the queue as a
circular queue .
• Circular queue is a linear data structure. It
follows FIFO principle.
• In circular queue the last node is connected back
to the first node to make a circle.

Free Powerpoint Templates

Page 14
Overcome disadvantage of linear queue:
• It is also called as “Ring buffer”.
• Items can inserted and deleted from a queue
in O(1) time.

Free Powerpoint Templates

Page 15
 Representation Of
Queues
[Link] an array
[Link] linked list

Free Powerpoint Templates

Page 16
Types Of Queue

1. Circular Queue

2. Dequeue (Double Ended Queue)

3. Priority Queue

Free Powerpoint Templates

Page 17
 CIRCULAR QUEUE

• A queue, in which the last node is connected back to

the first node to form a cycle, is called as circular
queue.
• Circular queue are the queues implemented in circular
form rather than in a straight line.
• Circular queues overcome the problem of unutilized
space in linear queue implemented as an array.
• The main disadvantage of linear queue using array is
that when elements are deleted from the queue, new
elements cannot be added in their place in the queue,
i.e. the position cannot be reused.

Free Powerpoint Templates

Page 18
CIRCULAR QUEUE

Free Powerpoint Templates

Page 19
CIRCULAR QUEUE IMPLEMENTATION

• After rear reaches the last position, i.e. MAX-1

in order to reuse the vacant positions, we can
bring rear back to the 0th position, if it is
empty, and continue incrementing rear in same
manner as earlier.

• Thus rear will have to be incremented

circularly.

• For deletion, front will also have to be

incremented circularly..

Free Powerpoint Templates

Page 20
Enqueue(Insert) operation on
Circular Queue:
• Step 1: Check for queue full
• If rear=max–1 and front=0 or if front=rear+1
then circular queue is full and insertion operation is
not possible. otherwise go to step 2
• Step 2: Check position of rear pointer
If rear=max–1
then set rear=0 otherwise increment rear by 1.
rear=(rear+1)%MAX
• Step 3: Insert element at the position pointer by rear
pointer.
q[rear]=Data
• Step 4: Check the position of front pointer
If front=–1 then set front as 0.

Free Powerpoint Templates

Page 21
 Illustration

Empty

insert
item 1

insert
item 3 Free Powerpoint Templates
Page 22
 Illustration
rear=max–1 and front=0
Insert 5, 7 and 9

Queue FULL
rear=max–1 && front=0

Now we delete the two elements i.e. item 1 and item

3 from the queue

Free Powerpoint Templates

Page 23
 Illustration
insert or
enqueue
element
11

insert element
13 in the
circular queue

front=rear+1
front=rear+1
Free Powerpoint Templates
Page 24
Dequeue (Delete) operation on
Circular Queue:
• Step 1: Check for queue empty if (front = -1)
then circular queue is empty and deletion operation
is not possible. otherwise go to step 2
• Step 2: Check for position of front and rear pointers.
if front = rear then
Data = q[front];
set front=rear=-1
• Step 3: Check position of front
if front = Max-1
Data = q[front];
then set front=0;
otherwise
Data = q[front];
front = (front+1)%MAX

Free Powerpoint Templates

Page 25
 Applications
• CPU Scheduling: Operating system process that
requires some event to occur or for some other
processes to complete for execution is often
maintained in a circular queue so that they
execute one after the other when all the conditions
are met or when all events occur.
• Memory Management: Use of ordinary queues
wastes memory space as already mentioned in our
above discussion. Using a circular queue for
memory management is beneficial for optimum
memory usage.
• Computer Controlled Traffic Signal
System: Computerized traffic signals are often
added to a circularFree Powerpoint Templates
queue so that they repeat Page 26
PRIORITY QUEUE
• A priority Queue is a collection of elements
where each element is assigned a priority and
the order in which elements are deleted and
processed is determined from the following
rules:
• 1) An element of higher priority is processed
before any element of lower priority.
• 2) Two elements with the same priority are
processed according to the order in which they
are added to the queue.

Free Powerpoint Templates

Page 27
The priority queue implementation
• The priority queue is again implemented in two
way
1. array/sequential representation.
2. Dynamic/ linked representation.
In priority queue node is divided into three parts

Free Powerpoint Templates

Page 28
PRIORITY QUEUE
• An example where priority queue are used is in
operating systems.
• The operating system has to handle a large
number of jobs.
• These jobs have to be properly scheduled.
• The operating system assigns priorities to each
type of job.
• The jobs are placed in a queue and the job with
the highest priority will be executed first.

Free Powerpoint Templates

Page 29
PRIORITY QUEUE
• Advantages:-
– Preferences to the higher priority process are
added at the beginning.
– Keep the list sorted in increasing order.

Free Powerpoint Templates

Page 30
Applications of Queue
• Queue, as the name suggests is used whenever we
need to have any group of objects in an order in which
the first one coming in, also gets out first while the
others wait for there turn, like in the following
scenarios :
– Serving requests on a single shared resource, like a printer,
CPU task scheduling etc.
– In real life, Call Center phone systems will use Queues, to
hold people calling them in an order, until a service
representative is free.
– Handling of interrupts in real-time systems. The interrupts are
handled in the same order as they arrive, First come first
served.

Free Powerpoint Templates

Page 31
Distinguish between stack and queue

[Link] STACK QUEUE

It is LIFO(Last In First Out) data
1 It is FIFO (First In First Out) data structure.
structure

Insertion and deletion take place Insertion takes place at rear and deletion
2
at only one end called top takes place at front.

3 It has only one pointer variable It has two pointer variables.

4 No memory wastage Memory wastage in linear queue

Operations: Operations:
5
[Link]() [Link]() [Link]() [Link]()
In computer system it is used in In computer system it is used time/resource
6
procedure calls sharing

Plate counter at marriage Student standing in a line at fee counter is an

7.
reception is an example of stack example of queue.

For more
Free Powerpoint detail contact us
Templates
Page 32
 Queue Implementation
• Queue in Python can be
implemented by the following
ways:

• list
• [Link]
• [Link]

Free Powerpoint Templates

Page 33
Implementation using list
• List is a Python’s built-in data
structure that can be used as a
queue.

• Instead of enqueue() and dequeue(),

append() and pop() function is
used.

• However, lists are quite slow for this

purpose because inserting or deleting
an element at the beginning requires
shifting all of theFree
other elements by
Powerpoint Templates
one, requiring O(n) time. Page 34
# Python program to
# demonstrate queue implementation
# using list

# Initializing a queue
queue = []

# Adding elements to the queue

[Link]('a')
[Link]('b')
[Link]('c')

print("Initial queue")
print(queue)
Output:
# Removing elements from the queue
print("\nElements dequeued from queue") Initial queue
print([Link](0)) ['a', 'b', 'c’]
print([Link](0)) Elements dequeued from
print([Link](0))
queue
a
print("\nQueue after removing elements") b
print(queue)
c
Queue after removing
Free Powerpoint Templates
elements Page 35
 Implementation using [Link]

• Queue in Python can be implemented using

deque class from the collections module.
• Deque is preferred over list in the cases where we
need quicker append and pop operations from
both the ends of container, as deque provides an
O(1) time complexity for append and pop
operations as compared to list which provides
O(n) time complexity.
• Instead of enqueue and deque, append() and
popleft() functions are used.

Free Powerpoint Templates

Page 36
from collections import deque

# Initializing a queue
q = deque()

# Adding elements to a queue

[Link]('a')
[Link]('b')
[Link]('c')

print("Initial queue")
print(q)

# Removing elements from a queue Output:

print("\nElements dequeued from the
queue")
print([Link]()) Initial queue
print([Link]()) ['a', 'b', 'c’]
print([Link]()) Elements dequeued from
queue
print("\nQueue after removing elements") a
print(q) b
c
Queue after removing
Free Powerpoint Templates
elements Page 37
 Implementation using [Link]

• Queue is built-in module of Python which

is used to implement a queue.
• [Link](maxsize) initializes a
variable to a maximum size of maxsize.
• A maxsize of zero ‘0’ means a infinite
queue. This Queue follows FIFO rule.
There are various functions available in
this module:

• maxsize – Number of items allowed in the

queue. Free Powerpoint Templates
Page 38
 Implementation using [Link]
There are various functions available in this module:

• maxsize – Number of items allowed in the queue.

• empty() – Return True if the queue is empty, False otherwise.
• full() – Return True if there are maxsize items in the queue. If
the queue was initialized with maxsize=0 (the default), then
full() never returns True.
• get() – Remove and return an item from the queue. If queue is
empty, wait until an item is available.
• get_nowait() – Return an item if one is immediately available,
else raise QueueEmpty.
• put(item) – Put an item into the queue. If the queue is full,
wait until a free slot is available before adding the item.
• put_nowait(item) – Put an item into the queue without
blocking. If no free slot is immediately available, raise
QueueFull. Free Powerpoint Templates
• qsize() – Return the number of items in the queue. Page 39
from queue import Queue

q = Queue(maxsize = 3) # Initializing a queue

# qsize() give the maxsize # of the Queue

print([Link]())

# Adding of element to queue

[Link]('a')
[Link]('b')
[Link]('c')
Output:
0
# Return Boolean for Full # Queue
print("\nFull: ", [Link]())
Full: True
# Removing element from queue
print("\nElements dequeued from the queue")
print([Link]())
Elements dequeued from
print([Link]()) the queue
print([Link]()) a
b
# Return Boolean for Empty # Queue c
print("\nEmpty: ", [Link]())
Empty: True
[Link](1)
print("\nEmpty: ", [Link]())
print("Full: ", [Link]()) Free Powerpoint TemplatesEmpty: False
Full: False Page 40