Data Structures
Queue
Neha Data Structures 1/15
Contents
Queue 3
Introduction to Queue 3
Operations on Queue 5
Implementation of queues 6
Array implementation of queues 7
Linked implementation of queues 17
Circular queues 23
Double Ended queue 43
Priority Queue 59
Data Structures 2/15
Introduction to Queue
► A Queue is a fundamental concept in computer science used
for storing and managing data in a specific order.
► It follows the principle of ”First in, First out” (FIFO), where
the first element added to the queue is the first one to be
removed.
► Queues are commonly used in various algorithms and
applications for their simplicity and efficiency in managing
data flow.
Data Structures 3/15
Figure: Structure of Queue
Data Structures 4/15
Operations on Queue
► Create - Creating the queue with initial values.
► Add - enqueue() – Insertion of elements at rear to the queue.
► Delete - dequeue() – Removal of elements at front from the
queue.
► Full - isFull() – Validates if the queue is full.
► Empty - isEmpty() – Checks if the queue is empty.
► peek() or front()- Acquires the data element available at the
front node of the queue without deleting it.
► rear() – This operation returns the element at the rear end
without removing it.
► size(): This operation returns the size of the queue i.e. the
total number of elements it contains at present.
Data Structures 5/15
Implementation of queues
► Array
► Linked List
Data Structures 6/15
Array implementation of queues
•Define a structure consisting of an array and two pointers
front and rear.
•Initialize the array with MAX_SIZE.
•Initialize both the front and rear pointers to -1.
•The insertion of elements will take place through the rear
pointer and the deletion of elements will take place through
the front pointer.
•Implement isFull, isEmpty, Enqueue, and Dequeue
functions to manipulate the elements of the queue easily.
Data Structures 7/15
//Queue using Array
Data Structures 7/15
Data Structures 7/15
Data Structures 7/15
Data Structures 7/15
Linked implementation of queues
Data Structures 7/15
Data Structures 7/15
Data Structures 7/15
Data Structures 7/15
Circular queues
► A Circular Queue is an extended version of a normal queue
where the last element of the queue is connected to the first
element of the queue forming a circle.
► The operations are performed based on FIFO (First In First
Out) principle. It is also called ‘Ring Buffer’.
► In a normal Queue, we can insert elements until queue
becomes full. But once queue becomes full, we can not insert
the next element even if there is a space in front of queue.
Data Structures 9/15
Figure: Circular Queue
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Double Ended queue
Figure: Deque
► Deque or Double Ended Queue is a generalized version of
Queue data structure that allows insert and delete at both
ends.
Data Structures 11/15
► push-front() - Inserts the element at the beginning.
► push-back() - Adds element at the end.
► pop-front() - Removes the first element from the deque.
► pop-back() - Removes the last element from the deque.
► front() - Gets the front element from the deque.
► back() - Gets the last element from the deque.
Data Structures 12/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 10/15
Data Structures 11/15
Priority Queue
► A priority queue is a type of queue that arranges elements
based on their priority values.
► Elements with higher priority values are typically retrieved or
removed before elements with lower priority values.
► Each element has a priority value associated with it.
► When we add an item, it is inserted in a position based on its
priority value.
► There are several ways to implement a priority queue,
including using an array, linked list, heap, or binary search tree.
► Binary heap being the most common method to implement.
Data Structures 13/15
► The reason for using Binary Heap is simple, in binary heaps,
we have easy access to the min (in min heap) or max (in max
heap) and binary heap being a complete binary tree are easily
implemented using arrays.
► Since we use arrays, we have cache friendliness advantage also.
► Priority queues are often used in real-time systems, where the
order in which elements are processed is not simply based on
the fact who came first (or inserted first), but based on
priority.
► Priority Queue is used in algorithms such as Dijkstra’s
algorithm, Prim’s algorithm, Kruskal’s algorithm and Huffnam
Coding.
Data Structures 14/15
Thank you
Data Structures 15/15