LECTURE # 11
QUEUES in DATA STRUCTURES
Instructors:
[Link]-e-Shawar Agha
ROAD MAP
Introduction to Queue
Operations in Queue
Types of Queue
Queue
o Queue is also an abstract data type or a linear data structure, just like
stack data structures, in which the first element is inserted from one end
called the REAR(also called tail), and the removal of existing element
takes place from the other end called as FRONT(also called head).
o This makes queue as FIFO(First in First Out) data structure, which
means that
element inserted first will be removed first.
o The difference between stacks and queues is in removing. In a stack we
remove the item the most recently added; in a queue, we remove the
item the least recently added.
Representation of Queue
As we now understand that in queue, we access both ends for different reasons.
The following diagram given below tries to explain queue representation as data
structure −
As in stacks, a queue can also be implemented using Arrays, Linked-lists,
Pointers and Structures. For the sake of simplicity, we shall implement queues
using one-dimensional array.
Real world examples of Queue
o Queue, as the name suggests is used whenever we need to manage any group
of objects in an order in which the first one coming in, also gets out first while the
others wait for their turn, like in the following scenarios:
o Serving requests on a single shared resource, like a printer, CPU task scheduling
etc.
o In real life scenario, Call Center phone systems uses Queues to hold people
calling them
in an order, until a service representative is free.
o A real-world example of queue can be a single-lane one-way road, where the
vehicle enters first, exits first.
Applications of Queue
o Every I/O device has their own queue to collect requests from different
application or processing (Print line of a document)
o Shared resources usage (CPU, Memory etc)
o Operating system may keep a queue of processes that are waiting to
run on the CPU.
o Job Scheduling (Round Robin, First-Come-First-Serve)
Basic operations on Queue
Queue operations may involve initializing or defining the queue, utilizing it,
and then completely erasing it from the memory. Here we shall try to
understand the basic operations associated with queues.
• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue
Status of Queue
o Few more functions are required to make the above-mentioned
queue operation efficient.
• peek(): Gets the element at the front of the queue without
removing it.
• isfull() : Checks if the queue is full.
• isempty() : Checks if the queue is empty.
o In queue, we always dequeue (or access) data, pointed by front pointer
and while enqueing (or storing) data in the queue we take help of rear
pointer.
Enqueue operation algorithm
procedure enqueue(data)
if queue is full
return overflow
end if
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Dequeue operation algorithm
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
Example
Consider the following queue (linear queue). Rear = 4 and Front = 1
and N = 7
(1) Insert 20. Now Rear = 4 and Front = 0
10 50 30 40 20
(2) Delete Front Element. Now Rear = 4 and Front = 1
50 30 40 20
(3) Delete Front Element. Now Rear = 4 and Front = 2
30 40 20
(4) Insert 60. Now Rear = 5 and Front = 2
30 40 20 60
Limitation of Linear Queue
•Once the queue is full, even though few elements from the front are
deleted and some occupied space is relieved, it is not possible to add
anymore new elements, as the rear has already reached the Queue’s
rear most position.
Circular Queue
o This queue is not linear but circular.
o Its structure can be like the given figure
o In circular queue, once the Queue is full the "First" element of the Queue
becomes the "Rear" most element, if and only if the "Front" has moved forward.
otherwise it will again be a "Queue overflow" state.
Figure: Circular Queue having
Rear = 5 and Front = 0
DEQUE (Double Ended Queue)
o It is also a homogeneous list of elements in which insertion and
deletion
operations are performed from both the ends.
o That is, we can insert elements from the rear end or from the front
ends.
o Hence it is called double-ended queue. It is commonly referred as
a
Deque.
o There are two types of Deque. These two types are due to the
restrictions put to perform either the insertions or deletions only at
one end.
SUMMARY
Introduction to Queue
Operations in Queue
Types of Queue