Scribd
Upload
6 views62 pages

Java Queue Data Structures Guide

This document provides an overview of queues as a fundamental data structure in computer science, explaining their FIFO principle and various operations such as enqueue and dequeue. It details implementations of queues using arrays and linked lists, as well as circular queues, with accompanying Java code examples. The content is part of a course module on Data Structures using JAVA, presented by Dr. A K Yadav at the School of Computer Science and Engineering.

Uploaded by

halaplay385
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views62 pages

Java Queue Data Structures Guide

This document provides an overview of queues as a fundamental data structure in computer science, explaining their FIFO principle and various operations such as enqueue and dequeue. It details implementations of queues using arrays and linked lists, as well as circular queues, with accompanying Java code examples. The content is part of a course module on Data Structures using JAVA, presented by Dr. A K Yadav at the School of Computer Science and Engineering.

Uploaded by

halaplay385
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

School of Computer Science and Engineering

Data Structures using JAVA [R1UC303B]

Module-VII: Queue
Dr. A K Yadav

School of Computer Science and Engineering


Plat No 2, Sector 17A, Yamuna Expressway
Greater Noida, Uttar Pradesh - 203201

November 24, 2024

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 1/15


School of Computer Science and Engineering

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

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 2/15


School of Computer Science and Engineering

Introduction to Queue
I A Queue is a fundamental concept in computer science used
for storing and managing data in a specific order.
I 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.
I Queues are commonly used in various algorithms and
applications for their simplicity and efficiency in managing
data flow.

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 3/15


School of Computer Science and Engineering

Figure: Structure of Queue

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 4/15


School of Computer Science and Engineering

Operations on Queue
I Create - Creating the queue with initial values.
I Add - enqueue() – Insertion of elements at rear to the queue.
I Delete - dequeue() – Removal of elements at front from the
queue.
I Full - isFull() – Validates if the queue is full.
I Empty - isEmpty() – Checks if the queue is empty.
I peek() or front()- Acquires the data element available at the
front node of the queue without deleting it.
I rear() – This operation returns the element at the rear end
without removing it.
I size(): This operation returns the size of the queue i.e. the
total number of elements it contains at present.

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 5/15


School of Computer Science and Engineering

Implementation of queues
I Array
I Linked List

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 6/15


School of Computer Science and Engineering

Array implementation of queues

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15


School of Computer Science and Engineering
//Queue using Array

class Queue {
int queue[];
int front, rear, capacity;

Queue(int size) {
front = rear = -1;
capacity = size;
queue = new int[capacity];
}

// insert an element into the queue


void enQueue(int item) {
// check if the queue is full
if (capacity-1 == rear) {
[Link]("Queue is full");
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15
School of Computer Science and Engineering
return;
}
// insert element at the rear
else {
queue[++rear] = item;
if(front==-1) front=0;
}
return;
}

//remove an element from the queue


int deQueue() {
// check if queue is empty
if (front==-1 || rear<front) {
[Link]("Queue is empty");
return Integer.MIN_VALUE;
}
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15
School of Computer Science and Engineering
else {
int temp=queue[front++];
[Link]("Item "+temp+" is deQueued\n");
return temp;
}

public boolean isEmpty() {


return (front==-1 || rear<front);
}

public boolean isFull() {


return (rear==capacity-1);
}

// print queue elements


Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15
School of Computer Science and Engineering
void queueDisplay()
{
int i;
if (front == -1 || rear<front) {
[Link]("Queue is Empty");
return;
}

// traverse front to rear and print elements


[Link]("Elements of the Queue are: ");
for (i = front; i < rear; i++) {
[Link]("%d , ", queue[i]);
}
[Link](" %d\n", queue[i]);
return;
}

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15


School of Computer Science and Engineering
// print front of queue
void queueFront()
{
if (front == -1) {
[Link]("Queue is Empty");
return;
}
[Link]("Front Element of the queue: %d\n
return;
}
void queueRear()
{
if (front == -1) {
[Link]("Queue is Empty");
return;
}
[Link]("Rear Element of the queue: %d\n"
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15
School of Computer Science and Engineering
return;
}
int queueSize()
{
int size=0;
if (front == -1 || rear<front) return size;
if(front<=rear)
size=rear-front+1;
return size;
}
}

public class QueueArray {


public static void main(String[] args) {
// Create a queue of capacity 4
Queue q = new Queue(4);

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15


School of Computer Science and Engineering
[Link]("Initial Queue(capacity=4):");
// print Queue elements
[Link]("Display():");
[Link]();
[Link]("Size():%d\n",[Link]());

// inserting elements in the queue


[Link]("enQueue(10):");
[Link](10);
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(30):");
[Link](30);
[Link]();
[Link]("Size():%d\n",[Link]());

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15


School of Computer Science and Engineering
[Link]("enQueue(50):");
[Link](50);
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(70):");
[Link](70);
[Link]();
[Link]("Size():%d\n",[Link]());

// insert element in the queue


[Link]("enQueue(90):");
[Link](90);
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("deQueue():");
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15
School of Computer Science and Engineering
[Link]();
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("deQueue():");
[Link]();
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(100):");
[Link](100);
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(110):");
[Link](110);
[Link]();
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 7/15
School of Computer Science and Engineering
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(120):");
[Link](120);
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("Front():");
[Link]();
[Link]("Rear():");
[Link]();
}
}

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 8/15


School of Computer Science and Engineering

Linked implementation of queues

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 8/15


School of Computer Science and Engineering
//Queue using Linked List

class QueueLL {
private Node front, rear;
private int queueSize; // queue size

//linked list node


private class Node {
int data;
Node next;
}

//default constructor - initially front & rear are null; si


public QueueLL() {
front = null;
rear = null;
queueSize = 0;
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 8/15
School of Computer Science and Engineering
}
//check if the queue is empty
public boolean isEmpty() {
return (queueSize == 0);
}

//Remove item from the front of the queue.


public int dequeue() {
if (isEmpty()) {
[Link]("\nQueue is empty");
}
int data = [Link];
front = [Link];
queueSize--;
if (isEmpty()) {//queueSize is 0 after dequeue.
rear = null;
}
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 8/15
School of Computer Science and Engineering

[Link]("Element " + data+ " removed from the qu


return data;
}

//Add data at the rear of the queue.


public void enqueue(int data) {
Node New_Node=new Node();
if(New_Node==null) {
[Link]("\nQueue is full");
}
New_Node.data=data;
New_Node.next=null;

if (isEmpty()){
front = rear=New_Node;
}
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 8/15
School of Computer Science and Engineering
else {
[Link]=New_Node;
rear=New_Node;
}
queueSize++;
[Link]("Element " + data+ " added to the queue"
}
//print front and rear of the queue
public void print_frontRear() {
if(front!=null)
[Link]("Front of the queue:" + [Link]
+ "\nRear of the queue:" + [Link]);
}
}

class QueueLink{
public static void main(String a[]){
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 8/15
School of Computer Science and Engineering
QueueLL queue = new QueueLL();
[Link](6);
[Link](3);
queue.print_frontRear();
[Link](12);
[Link](24);
[Link]();
[Link]();
[Link](9);
queue.print_frontRear();
}
}

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 9/15


School of Computer Science and Engineering

Circular queues
I 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.
I The operations are performed based on FIFO (First In First
Out) principle. It is also called ‘Ring Buffer’.
I 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.

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 9/15


School of Computer Science and Engineering

Figure: Circular Queue

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15


School of Computer Science and Engineering
//Circular Queue using Array

class QueueA

{
int queue[];
int front;
int rear;
int capacity;

QueueA(int size) {
front = rear = -1;
capacity = size;
queue = new int[capacity];
}

// insert an element into the queue


Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
void enQueue(int item) {
// check if the queue is full
if (front == ((rear+1)%capacity)) {
[Link]("Queue is full");
return;
}
// insert element at the rear
else {
rear= (rear==capacity-1?0:++rear);
//rear=((rear+1)%capacity);
queue[rear] = item;
if(front==-1) front=0;
queueDisplay();
}
return;
}

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15


School of Computer Science and Engineering
//remove an element from the queue
int deQueue() {
// check if queue is empty
if (front ==-1) {
[Link]("Queue is empty");
return -1;
}
else {
int temp=queue[front];
if(front==rear)
front=rear=-1;
else
front=(front==capacity-1?0:++front);
//front=((front+1)%capacity);
[Link]("Item "+temp+" is deQueued\n");
queueDisplay();
return temp;
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
}

// print queue elements


void queueDisplay()
{
int i;
if (front == -1) {
[Link]("Queue is Empty");
return;
}

// traverse front to rear and print elements


[Link]("Queue is:");
if(front<=rear)
for (i = front; i < rear; i++)
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
[Link](" %d , ", queue[i]);
else {
for (i = front; i < rear+capacity; i++)
[Link](" %d , ", queue[i%capacity]);
//for (i = 0; i < rear; i++)
//[Link](" %d , ", queue[i]);
}
[Link](" %d \n", queue[rear]);

return;
}

// print front of queue


void queueFront()
{
if (front == -1) {
[Link]("Queue is Empty");
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
return;
}
[Link]("Front Element of the queue: %d\n
return;
}

void queueRear()
{
if (front == -1) {
[Link]("Queue is Empty");
return;
}
[Link]("Rear Element of the queue: %d\n"
return;
}

int queueSize()
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
{
int size=0;
if (front == -1) return size;

if(front<=rear)
size=rear-front+1;
else
size=capacity-(front-rear-1);
return size;
}
}

public class QueueC {


public static void main(String[] args) {
// Create a queue of capacity 4
QueueA q = new QueueA(4);

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15


School of Computer Science and Engineering
[Link]("Initial Queue(capacity=4):");
// print Queue elements
[Link]("Display():");
[Link]();
[Link]("Size():%d\n",[Link]());

// inserting elements in the queue


[Link]("enQueue(10):");
[Link](10);
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(30):");
[Link](30);
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(50):");
[Link](50);
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(70):");
[Link](70);
[Link]("Size():%d\n",[Link]());

// insert element in the queue


[Link]("enQueue(90):");
[Link](90);
[Link]("Size():%d\n",[Link]());

[Link]("deQueue():");
[Link]();
[Link]("Size():%d\n",[Link]());

[Link]("deQueue():");
[Link]();
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(100):");
[Link](100);
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(110):");
[Link](110);
[Link]("Size():%d\n",[Link]());

[Link]("enQueue(120):");
[Link](120);
[Link]("Size():%d\n",[Link]());

[Link]("Front():");
[Link]();
[Link]("Rear():");
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
[Link]();
}
}

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15


School of Computer Science and Engineering
//Circular Queue using Linked List

class QueueCLL {
private Node front, rear;
private int queueSize; // queue size

//linked list node


private class Node {
int data;
Node next;
}

//default constructor - initially front & rear are null;


//size=0; queue is empty
public QueueCLL() {
front = null;
rear = null;
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
queueSize = 0;
}
//check if the queue is empty
public boolean isEmpty() {
return (queueSize == 0);
}

//Add data at the rear of the queue.


@SuppressWarnings("unused")
public void enqueue(int data) {
Node New_Node=new Node();
if(New_Node==null) {
[Link]("Queue is full");
}
New_Node.data=data;
if (isEmpty()){
front = rear=New_Node;
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
[Link]=front;
}
else {
New_Node.next=front;
[Link]=New_Node;
rear=New_Node;
}
queueSize++;
[Link]("Element " + [Link]+ " added to the q
}

//Remove item from the front of the queue.


public int dequeue() {
if (isEmpty()) {
[Link]("Queue is empty");
}
int data = [Link];
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
front = [Link];
[Link]=front;
queueSize--;
if (isEmpty()) {//queueSize is 0 after dequeue.
front=rear = null;
}

[Link]("Element " + data+ " removed from the qu


return data;
}

//print front and rear of the queue


public void print_frontRear() {
if(front!=null)
[Link]("Front of the queue:" + [Link]
+ "\nRear of the queue:" + [Link]);
}
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
void queueDisplay()
{
Node temp;
if (front == null) {
[Link]("Queue is Empty");
return;
}

// Traverse front to rear and print elements


[Link]("Elements of the Queue: ");
for (temp = front; temp != rear; temp=[Link]) {
[Link]("%d , ", [Link]);
}
[Link](" %d\n", [Link]);
return;
}
}
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering

class QueueCirLL{
public static void main(String a[]){
QueueCLL q = new QueueCLL();
[Link]("Display():");
[Link]();
[Link]("enqueue(6):");
[Link](6);
[Link]();
[Link]("enqueue(3):");
[Link](3);
[Link]();
[Link]("enqueue(12):");
[Link](12);
[Link]();
[Link]("enqueue(24):");
[Link](24);
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 10/15
School of Computer Science and Engineering
[Link]();
[Link]("dequeue():");
[Link]();
[Link]();
[Link]("dequeue():");
[Link]();
[Link]();
[Link]("enqueue(9):");
[Link](9);
[Link]();
[Link]("frontRear():");
q.print_frontRear();
}
}

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 11/15


School of Computer Science and Engineering

Double Ended queue

Figure: Deque

I Deque or Double Ended Queue is a generalized version of


Queue data structure that allows insert and delete at both
ends.

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 11/15


School of Computer Science and Engineering

I push-front() - Inserts the element at the beginning.


I push-back() - Adds element at the end.
I pop-front() - Removes the first element from the deque.
I pop-back() - Removes the last element from the deque.
I front() - Gets the front element from the deque.
I back() - Gets the last element from the deque.

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15


School of Computer Science and Engineering
//De-queue using circular array

/*Operations on Deque:
void Push_Front(int key);
void Push_Rear(int key);
void Pop_Front();
void Pop_Rear();
bool isFull();
bool isEmpty();
int getFront();
int getRear();*/
class DequeCirArr {
static int queue[];
static int front;
static int rear;
static int capacity;

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15


School of Computer Science and Engineering
public DequeCirArr(int size)
{
front = -1;
rear = -1;
capacity = size;
queue = new int[capacity];
}

// Checks whether Deque is full or not.


boolean isFull()
{
return ((front == 0 && rear == capacity - 1)
|| front == rear + 1);
}

// Checks whether Deque is empty or not.


boolean isEmpty() { return (front == -1); }
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering

// Inserts an element at front


void Push_Front(int key)
{
// check whether Deque is full or not
if (isFull()) {
[Link]("Overflow");
return;
}

// If queue is initially empty


if (front == -1) {
front = 0;
rear = 0;
}
// front is at first position of queue
else if (front == 0)
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering
front = capacity - 1;
else // decrement front end by ’1’
front--;
// insert current element into Deque
queue[front] = key;
}

// function to insert element at rear end of Deque.


void Push_Rear(int key)
{
if (isFull()) {
[Link](" Overflow ");
return;
}

// If queue is initially empty


if (front == -1) {
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering
front = 0;
rear = 0;
}
// rear is at last position of queue
else if (rear == capacity - 1)
rear = 0;
// increment rear end by ’1’
else
rear++;
// insert current element into Deque
queue[rear] = key;
}

// Deletes element at front end of Deque


void Pop_Front()
{
// check whether Deque is empty or not
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering
if (isEmpty()) {
[Link]("Queue Underflow\n");
return;
}

// Deque has only one element


if (front == rear) {
front = -1;
rear = -1;
}
else
// back to initial position
if (front == capacity - 1)
front = 0;
else // increment front by ’1’ to remove current
// front value from Deque
front++;
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering
}

// Delete element at rear end of Deque


void Pop_Rear()
{
if (isEmpty()) {
[Link](" Underflow");
return;
}

// Deque has only one element


if (front == rear) {
front = -1;
rear = -1;
}
else if (rear == 0)
rear = capacity - 1;
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering
else
rear--;
}

// Returns front element of Deque


int getFront()
{
// check whether Deque is empty or not
if (isEmpty()) {
[Link](" Underflow");
return -1;
}
return queue[front];
}

// function return rear element of Deque


int getRear()
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering
{
// check whether Deque is empty or not
if (isEmpty()) {
[Link](" Underflow");
return -1;
}
return queue[rear];
}

// print queue elements


static void DequeDisplay()
{
int i;
if (front == -1) {
[Link]("Queue is Empty");
return;
}
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering

//traverse front to rear and print elements


[Link]("Queue is:");
if(front<=rear) {
for (i = front; i < rear; i++)
[Link](" %d , ", queue[i]);
}
else {
for (i = front; i < rear+capacity; i++)
[Link](" %d , ", queue[i%capacity]);
//for (i = 0; i < rear; i++)
//[Link](" %d , ", queue[i]);
}
[Link](" %d \n", queue[rear]);

return;
}
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering

public static void main(String[] args)


{

DequeCirArr dq = new DequeCirArr(5);

// Function calls
[Link]("Initial Queue(capacity=5):");
DequeDisplay();
[Link]("Insert element at rear: 5 ");
dq.Push_Rear(5);
DequeDisplay();

[Link]("Insert element at rear: 10 ");


dq.Push_Rear(10);
DequeDisplay();
Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering

dq.Pop_Rear();
[Link]("After delete rear element: ");
DequeDisplay();

[Link]("Insert element at front: 15 ");


dq.Push_Front(15);
DequeDisplay();

[Link]("Insert element at front: 20 ");


dq.Push_Front(20);
DequeDisplay();

[Link]("Insert element at rear: 30 ");


dq.Push_Rear(30);
DequeDisplay();

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15


School of Computer Science and Engineering
[Link]("Insert element at rear: 40 ");
dq.Push_Rear(40);
DequeDisplay();

[Link]("Insert element at rear: 50 ");


dq.Push_Rear(50);
DequeDisplay();

[Link]("Insert element at front: 60 ");


dq.Push_Front(60);
DequeDisplay();

dq.Pop_Front();
[Link]("After delete front element:");
DequeDisplay();

[Link]("get front element: "+ [Link]());


Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 12/15
School of Computer Science and Engineering
[Link]("get rear element : "+ [Link]());
}
}

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 13/15


School of Computer Science and Engineering

Priority Queue
I A priority queue is a type of queue that arranges elements
based on their priority values.
I Elements with higher priority values are typically retrieved or
removed before elements with lower priority values.
I Each element has a priority value associated with it.
I When we add an item, it is inserted in a position based on its
priority value.
I There are several ways to implement a priority queue,
including using an array, linked list, heap, or binary search tree.
I Binary heap being the most common method to implement.

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 13/15


School of Computer Science and Engineering

I 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.
I Since we use arrays, we have cache friendliness advantage also.
I 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.
I Priority Queue is used in algorithms such as Dijkstra’s
algorithm, Prim’s algorithm, Kruskal’s algorithm and Huffnam
Coding.

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 14/15


School of Computer Science and Engineering

Thank you
Please send your feedback or any queries to
ashokyadav@[Link]

Module-VII: Queue Dr. A K Yadav Data Structures using JAVA 15/15

You might also like