DATA STRUCTURES
UNIT-2
SELVA KUMAR S
ASSISTANT PROFESSOR
B.M.S. COLLEGE OF ENGINEERING
QUEUE -ADT
• Queue: A list or a collection with the restrictions
that insertion can be performed at one end (the
rear or tail of the queue) and deletion can be
performed at other end (the front or head of the
queue).
• A queue is a FIFO(first in, first out) data structure
– Any waiting line is a queue:
– The check-out line at a grocery store
– The cars at a stop light
– Ticket counter
Conceptual view of a Queue
Uses of Queue in computing
• For any kind of problem involving FIFO Data.
• Printer Queue
• Keyboard Input buffer
• GUI Event Queue
• Web browser request Queue
Uses of Queues in computing
• In simulation studies, where the goal is to
reduce waiting times:
– Optimize the flow of traffic at a traffic light
– Determine the number of cashiers to have on duty
at a grocery store at different times of day
• Process Scheduling
• Printer Queues in Network
Queue Operations
• Enqueue(x) or push(x): add an element to the tail of a
queue.
• Dequeue() or pop(): remove an element from the head
of a queue.
• Front() or peek(): examine the element at the head of
the queue.
• QEmpty() or IsEmpty()
• QFull() or IsFull()
• It is not legal to access the elements in the middle of
the queue!
Implementation of Queues
• Array
• Linked List
Array Implementation
C Code
C code
Circular Queue
• Why we need a circular queue, when we
already have linear queue data structure.
Circular Queue
• Circular Queue is also a linear data structure, which follows
the principle of FIFO(First In First Out), but instead of ending
the queue at the last position, it again starts from the first
position after the last, hence making the queue behave like a
circular data structure.
Circular Queue
• In a circular queue, data is not actually removed from the queue. Only
the head pointer is incremented by one position when dequeue is
executed. As the queue data is only the data between head and tail, hence
the data left outside is not a part of the queue anymore, hence removed.
Circular Queue
• The head and the tail pointer will get reinitialised to 0 every
time they reach the end of the queue.
• Current Position = i
• Next Position = (i+1)% N
• Previous Position = (i+N-1)%N
Application of Circular Queue
• Below we have some common real-world
examples where circular queues are used:
• Computer controlled Traffic Signal
System uses circular queue.
• CPU scheduling and Memory management.
Implementation of Circular Queue
Implementation of Circular Queue
C Code – Circular Queue
Double ended Queue
• Deque or Double Ended Queue is a type of queue in which insertion
and removal of elements can be performed from either from the front
or rear. Thus, it does not follow FIFO rule (First In First Out).
• Types of Deque
• Input Restricted Deque
– In this deque, input is restricted at a single end but allows deletion at both the
ends.
• Output Restricted Deque
– In this deque, output is restricted at a single end but allows insertion at both
the ends.
Applications
Algorithm
C Code
Priority Queue
• Priority Queue is an extension of queue with
following properties.
– Every item has a priority associated with it.
– An element with high priority is dequeued before
an element with low priority.
– If two elements have the same priority, they are
served according to their order in the queue.
Priority Queue
• In a queue, the first-in-first-out rule is implemented whereas,
in a priority queue, the values are removed on the basis of
priority. The element with the highest priority is removed
first.
Types of Priority Queue
• Min Priority Queue: In min priority Queue
minimum number of value gets the highest
priority and lowest number of element gets
the highest priority.
• Max Priority Queue: Max priority Queue is the
opposite of min priority Queue in it maximum
number value gets the highest priority and
minimum number of value gets the minimum
priority.
Solution
C Code
C Code
C Code
Priority Queue (Circular Q concept)
