UNIT-2

SUBJECT NAME: - DSA

ADT Stack and its operations

A Stack is a widely used linear data structure in modern computers in which insertions and deletions of
an element can occur only at one end, i.e., top of the Stack. It is used in all those applications in which
data must be stored and retrieved in the last.

An everyday analogy of a stack data structure is a stack of books on a desk, Stack of plates, table
tennis, Stack of bootless, Undo or Redo mechanism in the Text Editors, etc.

A Stack is a linear data structure that holds a linear, ordered sequence of elements. It is an abstract data type. A Stack works on the
LIFO process (Last In First Out), i.e., the element that was inserted last will be removed first. To implement the Stack, it is required
to maintain a pointer to the top of the Stack, which is the last element to be inserted because we can access the elements only on
the top of the Stack.
TOP(S) denotes the top element of the stack s.

e.g. suppose S = [ S1, S2, S3,------------------,Sn)

then TOP(S) = Sn

Noel(S) denotes the number of elements in the stack.

Examples of stack:-

(i) Consider dishwater in a hotel washing plates and stacking them one
on top of another. When a waiter is to take a plate for serving, he will
take a plate from the top of the stack, which is the most recently
washed plate. The cleaner washes another plate and places it on top
of the stack.
(ii) In computer memory the elements are stored using binary
representation. In this, the bits forming are generated in reverse
order. In other words, the bits from remainders are displayed in a last
in first out manners.

Stack Representation
The following diagram depicts a stack and its operations −
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size
one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it
a fixed size stack implementation.

Basic Operations
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a
stack is used for the following two primary operations −
 push() − Pushing (storing) an element on the stack.
 pop() − Removing (accessing) an element from the stack.
When data is PUSHed onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following
functionality is added to stacks −
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full.
 isEmpty() − check if stack is empty.
At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top of
the stack, hence named top. The top pointer provides top value of the stack without actually removing it.
First we should learn about procedures to support stack functions −

(1) peek()
Algorithm of peek() function −
begin procedure peek
return stack[top]
end procedure
Implementation of peek() function in C programming language −
Example

int peek() {
return stack[top];
}

(2) isfull()
Algorithm of isfull() function −

begin procedure isfull

if top equals to MAXSIZE

return true
else
return false
endif

end procedure

Implementation of isfull() function in C programming language −

Example

bool isfull() {
 if(top == MAXSIZE)
return true;
else
return false;
}

(3) isempty()
Algorithm of isempty() function −

begin procedure isempty

if top less than 1

return true
else
return false
endif

end procedure

Implementation of isempty() function in C programming language is slightly different. We initialize top at -1, as the
index in array starts from 0. So we check if the top is below zero or -1 to determine if the stack is empty. Here's the
code −
Example

bool isempty() {
if(top == -1)
return true;
else
return false;
}

(4) Push Operation

The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a
series of steps −
 Step 1 − Checks if the stack is full.
 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.

Algorithm for PUSH Operation

A simple algorithm for Push operation can be derived as follows −

begin procedure push: stack, data

 if stack is full
return null
endif

top ← top + 1
stack[top] ← data

end procedure

Implementation of this algorithm in C, is very easy. See the following code −

Example

void push(int data) {

if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}

(5) Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of
pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack
to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates
memory space.
A Pop operation may involve the following steps −
 Step 1 − Checks if the stack is empty.
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack

if stack is empty
return null
endif

data ← stack[top]
top ← top - 1
return data

end procedure

Implementation of this algorithm in C, is as follows −

Example

int pop(int data) {

if(!isempty()) {
data = stack[top];
 top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}

Advantages of Stack

1. A Stack helps to manage the data in the ‘Last in First out’ method.
2. When the variable is not used outside the function in any program, the Stack can be used.
3. It allows you to control and handle memory allocation and deallocation.
4. It helps to automatically clean up the objects.

Disadvantages of Stack

1. It is difficult in Stack to create many objects as it increases the risk of the Stack overflow.
2. It has very limited memory.
3. In Stack, random access is not possible.

Application of the Stack

Following are some of the important applications of a Stack data structure:

1. Stacks can be used for expression evaluation.

2. Stacks can be used to check parenthesis matching in an expression.
3. Stacks can be used for Conversion from one form of expression to another.
4. Stacks can be used for Memory Management.
5. Stack data structures are used in backtracking problems.

1. Expression Evaluation

Stack data structure is used for evaluating the given expression. For example,
consider the following expression

5 * ( 6 + 2 ) - 12 / 4
Since parenthesis has the highest precedence among the arithmetic operators, (
6 +2 ) = 8 will be evaluated first. Now, the expression becomes

5 * 8 - 12 / 4

* and / have equal precedence and their associativity is from left-to-right. So,
start evaluating the expression from left-to-right.

5 * 8 = 40 and 12 / 4 = 3

Now, the expression becomes

40 - 3

And the value returned after the subtraction operation is 37.

2. Parenthesis Matching

Given an expression, you have to find if the parenthesis is either correctly

matched or not. For example, consider the expression ( a + b ) * ( c + d ).

In the above expression, the opening and closing of the parenthesis are given
properly and hence it is said to be a correctly matched parenthesis expression.
Whereas, the expression, (a + b * [c + d ) is not a valid expression as the
parenthesis are incorrectly given.

3. Expression Conversion
Converting one form of expressions to another is one of the important
applications of stacks.

 Infix to prefix
 Infix to postfix
 Prefix to Infix
 Prefix to Postfix
 Postfix to Infix
  Postfix to Infix

4. Memory management

The assignment of memory takes place in contiguous memory blocks. We call

this stack memory allocation because the assignment takes place in the
function call stack. The size of the memory to be allocated is known to the
compiler. When a function is called, its variables get memory allocated on the
stack. When the function call is completed, the memory for the variables is
released. All this happens with the help of some predefined routines in the
compiler. The user does not have to worry about memory allocation and release
of stack variables.

5. Backtracking Problems

Consider the N-Queens problem for an example. The solution of this problem
is that N queens should be positioned on a chessboard so that none of the
queens can attack another queen. In the generalized N-Queens problem, N
represents the number of rows and columns of the board and the number of
queens which must be placed in safe positions on the board.

The basic strategy we will use to solve this problem is to use backtracking. In
this particular case, backtracking means we will perform a safe move for a
queen at the time we make the move. Later, however, we find that we are stuck
and there is no safe movement for the next Queen, whom we are trying to put
on the blackboard, so we have to go back.
 This means we return to the queen's previous move, undo this step, and
continue to search for a safe place to place this queen.

We will use the stack to remember where we placed queens on the board, and
if we need to make a backup, the queen at the top of the stack will be popped,
and we will use the position of that queen to resume the search for next safe
location.

Conversion of Infix to Postfix

Algorithm for Infix to Postfix

Step 1: Consider the next element in the input.

Step 2: If it is operand, display it.

Step 3: If it is opening parenthesis, insert it on stack.

Step 4: If it is an operator, then

 If stack is empty, insert operator on stack.

 If the top of stack is opening parenthesis, insert the operator on stack
 If it has higher priority than the top of stack, insert the operator on stack.
 Else, delete the operator from the stack and display it, repeat Step 4.
Step 5: If it is a closing parenthesis, delete the operator from stack and display them until an opening
parenthesis is encountered. Delete and discard the opening parenthesis.

Step 6: If there is more input, go to Step 1.

Step 7: If there is no more input, delete the remaining operators to output.

Example: Suppose we are converting 3*3/(4-1)+6*2 expression into postfix form.

Following table shows the evaluation of Infix to Postfix:

2. Infix to Prefix
Algorithm for Infix to Prefix Conversion:

Step 1: Insert “)” onto stack, and add “(” to end of the A .

Step 2: Scan A from right to left and repeat Step 3 to 6 for each element of A until the stack is empty .

Step 3: If an operand is encountered, add it to B .

Step 4: If a right parenthesis is encountered, insert it onto stack .

Step 5: If an operator is encountered then,

a. Delete from stack and add to B (each operator on the top of stack)
which has same or higher precedence than the operator.
b. Add operator to stack.

Step 6: If left parenthesis is encountered then ,

a. Delete from the stack and add to B (each operator on top of stack
until a left parenthesis is encountered).
b. Remove the left parenthesis.

Step 7: Exit
 3. Postfix to Infix
Following is an algorithm for Postfix to Infix conversion:

Step 1: While there are input symbol left.

Step 2: Read the next symbol from input.

Step 3: If the symbol is an operand, insert it onto the stack.

Step 4: Otherwise, the symbol is an operator.

Step 5: If there are fewer than 2 values on the stack, show error /* input not sufficient values in the
expression */

Step 6: Else,
a. Delete the top 2 values from the stack.
b. Put the operator, with the values as arguments and form a string.
c. Encapsulate the resulted string with parenthesis.
d. Insert the resulted string back to stack.

Step 7: If there is only one value in the stack, that value in the stack is the desired infix string.

Step 8: If there are more values in the stack, show error /* The user input has too many values */

4. Prefix to Infix
Algorithm for Prefix to Infix Conversion

Step 1: The reversed input string is inserted into a stack -> prefixToInfix(stack)

Step 2: If stack is not empty,

a. Temp -> pop the stack
b. If temp is an operator,
Write a opening parenthesis “(“ to show -> prefixToInfix(stack)
Write temp to show -> prefixToInfix(stack)
Write a closing parenthesis “)” to show
c. Else If temp is a space ->prefixToInfix(stack)
d. Else, write temp to show if stack.top != space ->prefixToInfix(stack)

QUEUE:-
Queue is a linear data structure in which the insertion and deletion operations are performed at two
different ends. In a queue data structure, adding and removing elements are performed at two different
positions. The insertion is performed at one end and deletion is performed at another end. In a queue
data structure, the insertion operation is performed at a position which is known as 'rear' and the deletion
operation is performed at a position which is known as 'front'. In queue data structure, the insertion and
deletion operations are performed based on FIFO (First In First Out) principle.
Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both
its ends. One end is always used to insert data (enqueue) and the other is used to remove data
(dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed
first.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first. More
real-world examples can be seen as queues at the ticket windows and bus-stops.

Queue data structure can be defined as follows...

Queue data structure is a linear data structure in which the operations are performed based
on FIFO principle.

A queue data structure can also be defined as

"Queue data structure is a collection of similar data items in which insertion and deletion
operations are performed based on FIFO principle".

Example
Queue after inserting 25, 30, 51, 60 and 85.
EXAMPLES OF QUEUE:-
(I) The line of passenger at the ticket window is an example of a queue. The first
passenger in the line gets the ticket first & then second & so on. The new
person joins the queue in the end of the line.
(II) A customer checkout line at a super market cash register also forms a queue.
(III) Timesharing computer system where many users share the computer system
simultaneously.

Basic operations in Queue

Basic Operations
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.
Few more functions are required to make the above-mentioned queue operation efficient. These are −
 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.
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.
Let's first learn about supportive functions of a queue −

peek()
This function helps to see the data at the front of the queue. The algorithm of peek() function is as follows −
Algorithm
begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we just check for the rear pointer to reach at MAXSIZE
to determine that the queue is full. In case we maintain the queue in a circular linked-list, the algorithm will differ.
Algorithm of isfull() function −
Algorithm

begin procedure isfull

if rear equals to MAXSIZE

return true
else
return false
endif

end procedure

Implementation of isfull() function in C programming language −

Example

bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function −
Algorithm

begin procedure isempty

if front is less than MIN OR front is greater than rear

return true
else
return false
endif

end procedure

If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence empty.
Here's the C programming code −
Example

bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}

Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement
than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
 Step 1 − Check if the queue is full.
 Step 2 − If the queue is full, produce overflow error and exit.
 Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
 Step 4 − Add data element to the queue location, where the rear is pointing.
 Step 5 − return success.

Algorithm for enqueue operation

procedure enqueue(data)

if queue is full
return overflow
endif

rear ← rear + 1
queue[rear] ← data
return true

end procedure

Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data
where front is pointing and remove the data after access. The following steps are taken
to perform dequeue operation −
 Step 1 − Check if the queue is empty.
 Step 2 − If the queue is empty, produce underflow error and exit.
  Step 3 − If the queue is not empty, access the data where front is pointing.
 Step 4 − Increment front pointer to point to the next available data element.
 Step 5 − Return success.

Algorithm for dequeue operation

procedure dequeue

if queue is empty
return underflow
end if

data = queue[front]
front ← front + 1
return true

end procedure

Application of Queue
Here are some scenarios for the usage of Queue:
1. When any resource is shared among multiple consumers. Then the process of using the resource is
done using the queue. For example, CPU scheduling, Disk scheduling etc.
2. The queue is used in the implementation of various other data structures deque, priority queue,
doubly ended priority queue.
3. In networks, there are mail queues and queues in routers/switches.
4. In operating systems, queues are used in
1. Semaphores
2. Spooling in printers
3. FCFS (First come First serve) scheduling, example: FIFO queue
4. Buffer for devices like keyboards.
5. In the case of transferring the data asynchronously (i.e. it is not necessary to receive and
send the data at the same rate) between two processes. For example, IO Buffers, pipes, file
IO,

Some other applications of queue data structure:

 Applied as buffers on playing music in the mp3 players or CD players.

 Applied on handling the interruption in the operating system.
 Applied to add a song at the end of the playlist.
 Applied as the waiting queue for using the single shared resources like CPU,
Printers, or Disk.
 Applied to the chat application when someone sends messages to us and we
don’t have an internet connection then the messages are stored in the server
of the chat application.

Real-time application of Queue:

 ATM Booth Line

 Ticket Counter Line
 Key press sequence on the keyboard
 CPU task scheduling
 Waiting time of each customer at call centers.
 Advantages of Queue:

 A large amount of data can be managed efficiently with ease.

 Operations such as insertion and deletion can be performed with ease as it follows the first in first
out rule.
 Queues are useful when a particular service is used by multiple consumers.
 Queues are fast in speed for data inter-process communication.
 Queues can be used in the implementation of other data structures.

Disadvantages of Queue:

 The operations such as insertion and deletion of elements from the middle are time consuming.
 Limited Space.
 In a classical queue, a new element can only be inserted when the existing elements are deleted
from the queue.
 Searching an element takes O(N) time.
 Maximum size of a queue must be defined prior.

Types of queues:
1. Simple Queue: In a Simple queue, insertion of the element takes place at the rear end i.e.
ENQUEUE, and removal of the element takes place at the front end i.e. DEQUEUE. The simple
queue is also called a linear queue.

2. Circular Queue
A circular queue is an extended version of a linear queue as it follows the First In First Out principle with the
exception that it connects the last node of a queue to its first by forming a circular link. Hence, it is also called a Ring
Buffer.

In this tutorial, you will learn what a circular queue is. Also, you will find implementation of circular
queue in C, C++, Java and Python.

A circular queue is the extended version of a regular queue where the last element is connected to
the first element. Thus forming a circle-like structure.
How Circular Queue Works
Circular Queue works by the process of circular increment i.e. when we try to increment the pointer
and we reach the end of the queue, we start from the beginning of the queue.

Here, the circular increment is performed by modulo division with the queue size. That is,

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Circular Queue Operations

 The circular queue work as follows:

 two pointers FRONT and REAR

 FRONT track the first element of the queue

 REAR track the last elements of the queue
 initially, set value of FRONT and REAR to -1
1. Enqueue Operation

 check if the queue is full

 for the first element, set value of FRONT to 0

 circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it
would be at the start of the queue)
 add the new element in the position pointed to by REAR

2. Dequeue Operation

 check if the queue is empty

 return the value pointed by FRONT

 circularly increase the FRONT index by 1

 for the last element, reset the values of FRONT and REAR to -1

However, the check for full queue has a new additional case:

 Case 1: FRONT = 0 && REAR == SIZE - 1

 Case 2: FRONT = REAR + 1

The second case happens when REAR starts from 0 due to circular increment and when its value is
just 1 less than FRONT, the queue is full.
Why Was the Concept of Circular Queue Introduced?
Implementation of a linear queue brings the drawback of memory wastage. However, memory is a crucial resource
that you should always protect by analyzing all the implications while designing algorithms or solutions. In the case of
a linear queue, when the rear pointer reaches the MaxSize of a queue, there might be a possibility that after a certain
number of dequeue() operations, it will create an empty space at the start of a queue.
Circular Queue Complexity Analysis
The complexity of the enqueue and dequeue operations of a circular queue
is O(1) for (array implementations).
 Applications of Circular Queue

The circular Queue can be used in the following scenarios:

o Memory management: The circular queue provides memory management. As we have

already seen that in linear queue, the memory is not managed very efficiently. But in case of a
circular queue, the memory is managed efficiently by placing the elements in a location which
is unused.
o CPU Scheduling: The operating system also uses the circular queue to insert the processes
and then execute them.
o Traffic system: In a computer-control traffic system, traffic light is one of the best examples
of the circular queue. Each light of traffic light gets ON one by one after every jinterval of time.
Like red light gets ON for one minute then yellow light for one minute and then green light.
After green light, the red light gets ON.

Algorithm for Insertion an element in a circular queue

Insert CircularQueue ( )

1. If (FRONT == 1 and REAR == N) or (FRONT == REAR + 1) Then

2. Print: Overflow

3. Else

4. If (REAR == 0) Then [Check if QUEUE is empty]

(a) Set FRONT = 1

(b) Set REAR = 1

5. Else If (REAR == N) Then [If REAR reaches end if QUEUE]

6. Set REAR = 1

7. Else

8. Set REAR = REAR + 1 [Increment REAR by 1]

[End of Step 4 If]

9. Set QUEUE[REAR] = ITEM

10. Print: ITEM inserted

[End of Step 1 If]

11. Exit

Algorithm for Deletion in a circular queue

Delete CircularQueue ( )

1. If (FRONT == 0) Then [Check for Underflow]

2. Print: Underflow

3. Else

4. ITEM = QUEUE[FRONT]

5. If (FRONT == REAR) Then [If only element is left]

(a) Set FRONT = 0

(b) Set REAR = 0

6. Else If (FRONT == N) Then [If FRONT reaches end if QUEUE]

7. Set FRONT = 1

8. Else

9. Set FRONT = FRONT + 1 [Increment FRONT by 1]

[End of Step 5 If]

10. Print: ITEM deleted

[End of Step 1 If]

1. 11. Exit
Priority Queue
A priority queue is a special type of queue in which each element is associated with a priority value.
And, elements are served on the basis of their priority. That is, higher priority elements are served
first.

Rules:-

1. An element of higher priority is processing before any elements of lower priority.

 2. Two elements with the same priority are processed in FIFO manner.

Priority queue are useful in simulation for maintaining future events ordered by
time so that they can be quickly acceded what the next thing to happen is.

Takeaways
 Complexity of Priority queue
o Time complexity -
 Insertion : O(log n)O(logn)
 Peek : O(1)O(1)
 Deletion : O(log n)O(logn)

Characteristics of a Priority Queue

A queue is called a Priority Queue when it has the following characteristics:

 Each item in the queue must have a priority associated with it.
 Higher or lower priority elements must be dequeued before lower or higher
priority elements respectively depending on priority order taken by user that is if
user consider lower number as higher priority or higher number as higher priority.
 If two elements in the queue have the same priority value then the first in first out
rule is followed for these two elements alone i.e. the element that entered the
priority queue first will be the first to be removed.

Types of Priority Queue

 There are two types of Priority Queues:
1. Ascending Order Priority Queue

As mentioned before, the elements in the priority queue must be comparable which
means they are either less than, equal to or greater than one another. In an ascending
order priority queue, all the elements are compared with another and the rule:

The smaller the element(number), the higher the priority is applied.

Let us consider a priority queue having the following priorities:

4,2,6,1,8

The first step would be to arrange them in ascending order as follows:

1,2,4,6,8

In this priority queue, 1 is the smallest number and is hence the item with the highest
priority. On the other hand, 8 is the largest number and is hence the item with the lowest
priority.
2. Descending Order Priority Queue

In a descending order priority queue, all the elements are compared with another and
the rule:

The larger the element(number), the higher the priority.

Let us consider a priority queue having the following priorities:

4,2,6,1,8

The first step would be to arrange them in descending order as follows:

8,6,4,2,1

In this priority queue, 8 is the largest number and is hence the item with the highest priority. On
the other hand, 1 is the smallest number and is hence the item with the lowest priority.

Implementation of Priority Queue in Data Structures

A Priority Queue is implemented using one of the 4 Data Structures:

1. Linked List

In the linked list, the element having higher priority will be present at the head of the list. Then,
based on priority, all the elements in the list are arranged in descending order based on priority.

Class Declaration:
static class pqNode {
int data;
int priority;
Node next;
}
To insert an element, the list is traversed until a suitable position is found for the element to be
inserted in order to maintain the overall order of the linked list. Hence, the worst time complexity
is O(n) as the worst case is when all elements of the list need to be traversed.

For example, let us consider the linked list:

Let us consider that we need to insert an element with priority 8. 8 has a priority lower
than 5 so we traverse the linked list till we find a position where it is suitable. The linked list
will then look like this:

For deletion, the highest priority element will be removed first from the priority queue
and the highest priority element is at the head of the list and hence it will simply be
removed.

peek() is used to retrieve the highest priority element without removing it and this is also
present at the head of the list.

Since the highest priority element is present at the head of the list, it takes just O(1) time
to remove it or to do the peek() operation.

Table for time complexities to implement priority queue using various

data structures:

Data
Insert Delete Peek Reason
Structure
Highest priority element at head and hence can be
Linked List O(n) O(1) O(1) removed in O(1) time. For insertion, list needs to be
traversed till suitable position found, hence O(n).
All elements in order since remove and peek are O(1).
Ordered
O(n) O(1) O(1) For insertion, the array must be traversed until a
Array
suitable place is found, hence O(n).
Unordered O(1) O(n) O(n) In an unordered array, insertion can be done anywhere
Array since no order is maintained hence O(1). However for
removal or peek, the list must be traversed to find the
 Data
Insert Delete Peek Reason
Structure
highest or lowest priority element, hence O(n)
Top priority or lowest priority element is present at the
O(log O(log root node and hence the complexity for peek is O(1).
Heap O(1)
n) n) For removal and insertion, heapify operations must be
implemented which takes O(log n) complexity.
A pointer can be kept at the highest or lowest priority
element and hence the time complexity for peek is O(1).
Binary
O(log O(log For both insertion and deletion operations, the tree must
Search O(1)
n) n) be brought back to a form where all binary search trees
Tree
conditions hold true and hence the time complexity
is O(log n).

Priority Queue Operations

The operations on a Priority Queue in a heap are done in the following way:

A heap is a tree based data structure. A max-heap is one where the key value of the
parent node is always greater than or equal to the key value of the child node. Hence,
the element with the largest key value comes at the root.

Conversely, a min-heap is one where the key value of the parent node is always lesser
than or equal to the key value of the child node. Hence, the element with the lowest key
value comes at the root.

1. Inserting

We will make use of the Max-Heap data structure to implement insertion in a Priority
Queue. The algorithm is as follows:

1. START
2. If(no node):
1. Create node
3. Else:
1. Insert node at end of heap
4. Heapify
5. END

Let us now see with an example how this works:

Let’s say the elements are 1,4,2,7,8,5. The max-heap of these elements would look like:
Now, let’s try to insert a new element, 6. Since there are nodes present in the heap, we insert this
node at the end of heap so it looks like thi

Then, heapify operation is implemented. After which, the heap will look like this:
2. Deleting

We again make use of the Max-Heap Data Structure here to implement deletion in
a Priority Queue. The algorithm is as follows:

1. START
2. If node that needs to be deleted is a leaf node:
1. Remove the node
3. Else:
1. Swap node that needs to be deleted with the last leaf node present.
2. Remove the node
4. Heapify
5. END

Let us now see with an example how this works:

Let’s say the elements are 1,4,2,7,8,5,6. The max-heap of these elements would look
like:
Now, let’s try to delete an element, 6. Since this is not a leaf node, we swap it with the
last leaf node so it looks like this:

Then, we remove the leaf node so it looks like this:

 Then, heapify operation is implemented. After which, the heap will look like this:

Priority Queue Applications

Some of the applications of a priority queue are:

 Dijkstra's algorithm

 for implementing stack

 for load balancing and interrupt handling in an operating system

 for data compression in Huffman code

Deque (or double-ended queue)

The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion and
deletion operations are performed from both ends. We can say that deque is a generalized version of
the queue.

Though the insertion and deletion in a deque can be performed on both ends, it does not follow the
FIFO rule. The representation of a deque is given as follows -

Types of deque

There are two types of deque -

o Input restricted queue

o Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion can be
performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while insertion can be
performed from both ends.
Operations performed on deque
There are the following operations that can be applied on a deque -

o Insertion at front
o Insertion at rear
o Deletion at front
o Deletion at rear

We can also perform peek operations in the deque along with the operations
listed above. Through peek operation, we can get the deque's front and rear
elements of the deque. So, in addition to the above operations, following
operations are also supported in deque -

o Get the front item from the deque

o Get the rear item from the deque
o Check whether the deque is full or not
o Checks whether the deque is empty or not

Applications of deque
o Deque can be used as both stack and queue, as it supports both operations.
o Deque can be used as a palindrome checker means that if we read the string from both ends,
the string would be the same.