SVKMs NMIMS

Mukesh Patel School of Technology Management and Engineering, Shirpur

Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Unit – II
Linear Data Structure I
2.1 Introduction to Linear Data Structures

In the realm of computer science and programming, data structures are fundamental tools
that allow us to organize, manage, and store data efficiently. Among the various types of data
structures, linear data structures are the most basic and widely used. They are called "linear"
because they arrange data in a sequential manner, where elements are connected one after
another, like links in a chain or items in a list.

Linear data structures are essential for solving a wide range of computational problems. They
form the backbone of many algorithms and are often the first data structures introduced to
students learning programming. Their simplicity and versatility make them ideal for
understanding core concepts such as memory management, data access, and algorithmic
efficiency.

2.1.1. Characteristics of Linear Data Structures

Linear data structures have the following key characteristics:

1. Sequential Arrangement: Elements are stored in a linear sequence, meaning each

element has a unique predecessor and successor (except the first and last).
2. Single-Level Storage: Data is organized in a single dimension, unlike hierarchical
structures like trees or graphs.
3. Traversal: Elements can be traversed in a specific order (e.g., left to right).
4. Memory Allocation: Can be either static (fixed size, like arrays) or dynamic
(resizable, like linked lists).

2.1.2. Types of Linear Data Structures

There are four primary types of linear data structures: Arrays, Stacks, Queues and Linked
Lists.
1. Arrays
An array is a collection of elements stored in contiguous memory locations. Each element
can be accessed directly using its index.
 Advantages:
o Fast access using indices.
o Simple to implement.
 Disadvantages:
o Fixed size (static memory allocation).
o Insertion and deletion are costly (require shifting elements).
Example:

Page 1 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
int arr[5] = {10, 20, 30, 40, 50};
Arrays are ideal for scenarios where the number of elements is known in advance and random
access is required.
2. Stacks
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The last
element added is the first one to be removed.
 Operations:
o Push: Add an element to the top.
o Pop: Remove the top element.
o Peek/Top: View the top element without removing it.
 Applications:
o Function call management.
o Undo operations in editors.
o Expression evaluation (e.g., postfix notation).
Stacks are ideal for problems requiring backtracking or nested operations.

3. Queues
A queue is a linear data structure that follows the First In, First Out (FIFO) principle. The first
element added is the first one to be removed.
1. Operations:
o Enqueue: Add an element to the rear.
o Dequeue: Remove an element from the front.
o Front/Peek: View the front element.
2. Types:
o Simple Queue
o Circular Queue
o Priority Queue
o Deque (Double-Ended Queue)
3. Applications:
o Task scheduling.
o Print job management.
o Breadth-first search in graphs.
Queues are essential for managing tasks in order and handling asynchronous data.

4. Linked Lists
A linked list is a dynamic data structure where each element (called a node) contains data
and a reference (or pointer) to the next node.
 Types:
o Singly Linked List: Each node points to the next node.
o Doubly Linked List: Each node points to both the next and previous nodes.
o Circular Linked List: The last node points back to the first node.
 Advantages:
o Dynamic size.
o Efficient insertion and deletion.
 Disadvantages:

Page 2 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
o Slower access (no direct indexing).
o Requires extra memory for pointers.
Linked lists are useful when the size of the data structure is unknown or frequently changes.

Comparison of Linear Data Structures

Feature Array Linked List Stack Queue

Access Time Fast (O(1)) Slow (O(n)) Top only (O(1)) Front only (O(1))
Insertion Costly (O(n)) Efficient (O(1)) Top only (O(1)) Rear only (O(1))
Deletion Costly (O(n)) Efficient (O(1)) Top only (O(1)) Front only (O(1))
Memory Usage Fixed Dynamic Fixed/Dynamic Fixed/Dynamic
Use Case Static data Dynamic data Backtracking Scheduling

2.1.3. Applications of Linear Data Structures

Linear data structures are used in a wide variety of real-world applications:

 Arrays: Used in databases, image processing, and mathematical computations.

 Linked Lists: Used in dynamic memory allocation, file systems, and music playlists.
 Stacks: Used in parsing expressions, recursion, and browser history.
 Queues: Used in operating systems (process scheduling), customer service systems,
and network data packets.

Linear data structures are the foundation of data organization in computer science. Their
simplicity, efficiency, and versatility make them indispensable tools for programmers and
software engineers. Understanding how they work, when to use them, and how to implement
them is crucial for solving complex problems and writing efficient code.

However, a strong grasp of linear data structures will serve as a solid base for mastering
these more complex structures.

Page 3 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.2. Topic: Introduction to Stacks
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning
the last element added is the first to be removed. It operates through two main actions: push
(to add an element) and pop (to remove the top element).

Imagine a stack of plates in a cafeteria: you add plates to the top and remove them from the
top. This simple yet powerful concept is widely used in programming, algorithm design, and
system architecture.

Stacks are essential for managing data in a controlled and predictable manner. They are used
in various applications such as function call management, expression evaluation, syntax
parsing, and undo mechanisms in software. Understanding stacks is crucial for grasping more
advanced topics like recursion, compiler design, and memory management. They can be
implemented using arrays or linked lists. Due to their simple yet powerful structure, stacks
are fundamental in understanding recursion, memory management, and algorithm design.

The important variables used in the algorithms/ design of the Stacks are TOP & MAX_SIZE,
where TOP points to the topmost element in the stack and MAX_SIZE indicate the maximum
number of elements can be stored in the stack.
The other parameters used in the following algorithms is STACK, the storage space where the
elements of stack are stored.
The Value of TOP = -1, indicates that the stack is empty and if TOP = MAX_SIZE -1. Indicates
that the stack is full.
The various algorithms/operations of Stack are :
o Push: Add an element to the top.
o Pop: Remove the top element.
o Peek/Top: View the top element without removing it.
o IsEmpty : to check whether the stack is empty or not
o IsFull : to check whether the stack is Full or not
2.2.1. Algorithms:
1. Algorithm: Initialize Stack
Step 1: Define MAX_SIZE as the maximum capacity of the stack.
Step 2: Create an array STACK of size MAX_SIZE.
Step 3: Set TOP ← -1 to indicate the stack is initially empty.

2. Algorithm: PUSH(Element)
Input: Element to be added to the stack
Step 1: IF TOP == MAX_SIZE - 1, THEN
Display "STACK Overflow"
Go to Step 4.
Step 2: TOP ← TOP + 1.
Step 3:STACK[TOP] ← Element.
Step 4: End

Page 4 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
3. Algorithm: POP()
Output: Element removed from the stack
Step 1: If TOP == -1, THEN
Display "Stack Underflow" & Go To Step 5
Step 2: Element ← STACK[TOP]
Step 3: TOP ← TOP - 1
Step 4: Return Element
Step 5: End
4. Algorithm: PEEK()
Output: Element at the top of the stack
Step 1: If TOP == -1, then
Display "Stack is empty"
Exit
Step 2: Else
Return STACK[TOP].
Step 3: End
5. Algorithm: isEmpty()
Output: TRUE if stack is empty, FALSE otherwise
Step 1: If TOP == -1, then
Return TRUE.
Step 2: Else
Return FALSE.
Step 3: End
6. Algorithm: isFull()
Output: TRUE if stack is full, FALSE otherwise
Step 1: If TOP == MAX_SIZE - 1, then
Return TRUE.
Step 2: Else
Return FALSE.
Step 3: End

2.2.2. Applications of Stack

Stacks are used in a wide variety of real-world and computational scenarios:
1. Function Call Management
When a function is called, its execution context (local variables, return address) is pushed
onto the call stack. When the function returns, the context is popped off. This is how recursion
is managed internally.
2. Expression Evaluation
Stacks are used to evaluate arithmetic expressions, especially in postfix (Reverse Polish
Notation) and prefix notation. They help in converting infix expressions to postfix and
evaluating them efficiently.
3. Syntax Parsing
Compilers use stacks to parse syntax and check for balanced parentheses, brackets, and
braces in code.

Page 5 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
4. Undo Mechanism
Applications like text editors use stacks to implement undo functionality. Each action is
pushed onto a stack, and undo pops the last action.
5. Backtracking Algorithms
Stacks are used in algorithms that require backtracking, such as maze solving, puzzle solving,
and depth-first search in graphs.
6. Browser History
Web browsers use stacks to manage the history of visited pages. The most recently visited
page is on top, and going back pops the current page.

2.2.3. Advantages of Stack

 Simple and Efficient: Easy to implement and use.

 Memory Management: Helps in managing memory during recursive function calls.
 Controlled Access: Restricts access to only the top element, ensuring data integrity.
 Versatile: Useful in a wide range of applications from system-level programming to
user interfaces.

2.2.4. Disadvantages of Stack

 Limited Access: Only the top element can be accessed directly.

 Overflow and Underflow: Fixed-size stacks can overflow, and popping from an
empty stack causes underflow.
 Not Ideal for Random Access: Unlike arrays, stacks do not support random access to
elements.

Page 6 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.3. Topic: Introduction to Queues
Queues are classified in to four types

o Simple (or Linear ) Queue

o Circular Queue
o Priority Queue
o Deque (Double-Ended Queue)

2.3.1. Simple (or Linear ) Queue

A queue is a fundamental linear data structure that operates on the principle of First In, First
Out (FIFO). This means that the first element added to the queue is the first one to be
removed. Think of a queue as a line of people waiting at a ticket counter—those who arrive
first are served first. This simple concept is widely used in computer science for managing
tasks, resources, and data flow in a sequential and orderly manner.

Among the various types of queues, the linear queue is the most basic. It arranges elements
in a straight line and allows insertion at one end (rear) and deletion from the other end
(front). Linear queues are used in numerous applications such as task scheduling, buffering,
and resource management.

2.3.1.1. Characteristics of Linear Queue

A linear queue has the following key characteristics:

1. FIFO Order: Elements are processed in the order they arrive.

2. Single Direction: Insertion happens at the rear, and deletion happens at the front.
3. Fixed Size (in array implementation): The queue has a maximum capacity.
4. Sequential Storage: Elements are stored in a linear sequence.

2.3.1.2. Basic Operations of Linear Queue

Linear queues support several fundamental operations:

1. Enqueue(): Adds an element to the rear of the queue.

2. Dequeue(): Removes an element from the front of the queue.
3. Front(): Returns the front element without removing it.
4. isEmpty(): Checks if the queue is empty.
5. isFull(): Checks if the queue has reached its maximum capacity.

These operations ensure orderly processing of data and tasks.

Page 7 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
The important variables used in the algorithms/ design of the QUEUEs are FRONT, REAR &
MAX_SIZE, where FRONT points to the first element in the QUEUE, REAR points to the last
element in the queue,and MAX_SIZE indicate the maximum number of elements can be
stored in the Queue.
The other parameters used in the following algorithms is QUEUE, the storage space where
the elements of stack are stored.
The Value of FRONT = REAR = -1, indicates that the QUEUE is empty and if REAR = MAX_SIZE
-1, it indicates that the QUEUE is full.

2.3.1.3. Algorithms:
The various algorithms on Linear queue are :

1. Enqueue: Adds an element to the rear of the queue.

2. Dequeue: Removes an element from the front of the queue.
3. Front: Returns the front element without removing it.
4. isEmpty: Checks if the queue is empty.
5. isFull: Checks if the queue has reached its maximum capacity.

1. Algorithm: Initialize QUEUE

Step 1: Define MAX_SIZE as the maximum capacity of the Queue.
Step 2: Create an array QUEUE of size MAX_SIZE.
Step 3: Set FRONT ← -1 & REAR ← -1 to indicate the QUEUE is initially empty.

2. Algorithm : Enqueue(Element)
Input: Element to be added to the Queue
Step 1: IF REAR = MAX_SIZE - 1, THEN
Display "QUEUE Overflow"
Go to Step 4.
Step 2: IF REAR = -1, THEN
FRONT ← REAR ← 0
ELSE
REAR ← REAR+1
Step 3: QUEUE[REAR] ← Element
Step 4: End

3. Algorithm : Dequeue()
Output: Element removed from the QUEUE
Step 1 : IF FRONT = -1, THEN
Display “QUEUE UNDERFLOW” & Go To Step 5.
Step 2 : Element ← QUEUE[FRONT].
Step 3 : IF FRONT = REAR, Then
Front ← REAR ← -1.
ELSE
Front ← FRONT + 1.
Step 4 : Return Element.
Step 5 : End.

Page 8 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
4. Algorithm : FRONT()
Output: Element returned from the front of the QUEUE
Step 1 : IF FRONT = -1, THEN
Display “QUEUE UNDERFLOW” & Go To Step 4.
Step 2 : Element ← QUEUE[FRONT].
Step 3 : Return Element.
Step 4 : End

5. Algorithm: isEmpty()
Output: TRUE if QUEUE is empty, FALSE otherwise
Step 1: If FRONT == -1, then
Return TRUE
Step 2: Else
Return FALSE
Step 3: End

6. Algorithm: isFull()
Output: TRUE if QUEUE is full, FALSE otherwise
Step 1: If REAR == MAX_SIZE - 1, then
Return TRUE
Step 2: Else
Return FALSE
Step 3: End

2.3.1.4. Limitations of Linear Queue

While linear queues are simple and easy to implement, they have some limitations, especially
in array-based implementations:

 Wasted Space: After several dequeue operations, the front pointer moves forward,
leaving unused space at the beginning of the array.
 Fixed Size: The maximum size is predetermined, which can lead to overflow even
when there is unused space.
 No Reuse of Space: Once the rear reaches the end of the array, no more elements can
be added, even if there is space at the front.

These limitations are addressed by circular queues, which allow the rear to wrap around to
the beginning of the array.

2.3.1.5. Applications of Linear Queue

Linear queues are used in a wide range of real-world and computational scenarios:

1. Task Scheduling
Operating systems use queues to manage processes and tasks. Tasks are scheduled in
the order they arrive.

Page 9 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2. Print Queue
Printers use queues to manage print jobs. The first document sent to the printer is
printed first.
3. Customer Service Systems
Call centers and help desks use queues to manage customer requests. Requests are
handled in the order they are received.
4. Data Buffers
Queues are used in buffering data streams, such as audio or video playback, to ensure
smooth processing.
5. Breadth-First Search (BFS)
In graph traversal algorithms like BFS, queues are used to explore nodes level by level.

2.3.1.4. Advantages of Linear Queue

 Simple Structure: Easy to understand and implement.
 Orderly Processing: Ensures tasks are handled in the order they arrive.
 Efficient for Sequential Tasks: Ideal for scenarios where order matters.

Disadvantages of Linear Queue

 Fixed Size: Limited capacity in array-based implementation.

 Wasted Space: Inefficient use of memory after multiple dequeue operations.
 No Dynamic Resizing: Cannot grow or shrink based on demand (unless implemented
using linked lists).

2.3.2. Circular Queue

A circular queue is an advanced form of the linear queue that solves one of its major
limitations—wasted space due to the movement of the front and rear pointers. Like a linear
queue, a circular queue follows the First In, First Out (FIFO) principle, but with a twist: the
last position is connected back to the first position, forming a circle. This circular arrangement
allows efficient utilization of memory and is especially useful in systems where fixed-size
buffers are required.

Circular queues are widely used in real-time systems, operating systems, and embedded
systems where memory is limited and performance is critical. Understanding circular queues
is essential for mastering efficient data handling and resource management.

In a linear queue implemented using arrays, once the rear reaches the end of the array, no
more elements can be added—even if there is space at the front due to previous deletions.
This leads to inefficient memory usage.

A circular queue overcomes this by allowing the rear to wrap around to the beginning of the
array when space is available. This ensures that all positions in the array can be reused,
making it ideal for scenarios where memory is constrained.

Page 10 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.3.2.1. Characteristics of Circular Queue

1. FIFO Order: Elements are processed in the order they arrive.

2. Circular Arrangement: The last position is connected to the first.
3. Efficient Memory Use: No wasted space due to shifting.
4. Fixed Size: Typically implemented using arrays with a fixed capacity.
5. Two Pointers: front and rear track the positions for deletion and insertion.

2.3.2.2. Basic Operations of Circular Queue

Circular queues support the following operations:

1. Enqueue: Adds an element to the rear of the queue.

2. Dequeue: Removes an element from the front of the queue.
3. Front: Returns the front element without removing it.
4. isEmpty: Checks if the queue is empty.
5. isFull: Checks if the queue is full.
The key difference lies in how the FRONT and REAR pointers are updated using modulo
arithmetic to wrap around the array.

2.3.2.3. Algorithms:
The various algorithms on Circular queue are similar to Linear Queue with difference in the
pointer updating:
1. Enqueue: Adds an element to the rear of the queue.
2. Dequeue: Removes an element from the front of the queue.
3. Front: Returns the front element without removing it.
4. isEmpty: Checks if the queue is empty.
5. isFull: Checks if the queue has reached its maximum capacity.

1. Algorithm: Initialize QUEUE

Step 1: Define MAX_SIZE as the maximum capacity of the Queue.
Step 2: Create an array QUEUE of size MAX_SIZE.
Step 3: Set FRONT ← -1 & REAR ← -1 to indicate the QUEUE is initially empty.
2. Algorithm : Enqueue(Element)
Input: Element to be added to the Queue
Step 1: IF (FRONT =0 & REAR = MAX_SIZE – 1) OR (FRONT = REAR +1), THEN
Display "QUEUE Overflow"
Go to Step 4.
Step 2: IF REAR = -1, THEN
FRONT ← REAR ← 0
ELSE IF REAR = MAX_SIZE -1, THEN
REAR ←0.
ELSE
REAR ← REAR+1.
Step 3: QUEUE[REAR] ← Element
Step 4: End

Page 11 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
3. Algorithm : Dequeue()
Output: Element removed from the QUEUE
Step 1 : IF FRONT = -1, THEN
Display “QUEUE UNDERFLOW” & Go To Step 5.
Step 2 : Element ← QUEUE[FRONT].
Step 3 : IF FRONT = REAR, Then
Front ← REAR ← -1.
ELSE IF FRONT = MAX_SIZE – 1, THEN
FRONT ← 0.
ELSE
Front ← FRONT + 1.
Step 4 : Return Element.
Step 5 : End.

4. Algorithm : FRONT()
Output: Element returned from the front of the QUEUE
Step 1 : IF FRONT = -1, THEN
Display “QUEUE UNDERFLOW” & Go To Step 4.
Step 2 : Element ← QUEUE[FRONT].
Step 3 : Return Element.
Step 4 : End

5. Algorithm: isEmpty()
Output: TRUE if QUEUE is empty, FALSE otherwise
Step 1: If FRONT == -1, THEN
Return TRUE
Step 2: Else
Return FALSE
Step 3: End

6. Algorithm: isFull()
Output: TRUE if QUEUE is full, FALSE otherwise
Step 1: IF (FRONT = 0 & REAR == MAX_SIZE – 1) OR (FRONT = REAR+1), THEN
Return TRUE
Step 2: Else
Return FALSE
Step 3: End
2.3.2.4. Advantages of Circular Queue
 Efficient Memory Utilization: No wasted space due to shifting.
 Fixed Size Control: Ideal for buffer management.
 Fast Operations: Constant time insertion and deletion.
 Predictable Behavior: Useful in real-time systems.
2.3.2.5. Disadvantages of Circular Queue
 Complex Pointer Management: Requires careful handling of wrap-around logic.
 Fixed Capacity: Cannot grow dynamically unless implemented with linked lists.
 Overflow Risk: Must check for full condition before enqueue.

Page 12 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.3.2.6. Applications of Circular Queue
Circular queues are used in a variety of real-world and computational scenarios:
1. CPU Scheduling
Operating systems use circular queues to manage processes in round-robin
scheduling, where each process gets a fixed time slice.
2. Buffer Management
Circular queues are ideal for managing buffers in data streaming, audio/video
playback, and network packet handling.
3. Traffic Systems
Used in simulations of traffic lights and vehicle queues where cyclic behavior is
required.
4. Embedded Systems
Used in microcontrollers and real-time systems where memory is limited and
performance is critical.
5. Multitasking Systems
Circular queues help manage multiple tasks or threads in a cyclic order.

2.3.2.7. Circular Queue vs Linear Queue

Feature Linear Queue Circular Queue
Memory Utilization Inefficient Efficient
Wrap-Around Support No Yes
High (even with Low (space
Overflow Risk
space) reused)
Implementation Simple Slightly complex
Use Case Basic scheduling Real-time systems

2.3.3. Priority Queue

A priority queue is an advanced type of queue in which each element is associated with a
priority, and elements are served based on their priority rather than their order of arrival.
Unlike a regular queue that follows the First In, First Out (FIFO) principle, a priority queue
serves the element with the highest priority first, regardless of its position in the queue.
Priority queues are widely used in computer science and real-world applications where tasks
must be processed based on importance or urgency. Examples include CPU scheduling,
bandwidth management, emergency systems, and pathfinding algorithms like Dijkstra’s.

2.3.3.1. Characteristics of Priority Queue

1. Priority-Based Processing: Elements are dequeued based on priority, not arrival time.
2. Dynamic Ordering: The queue reorders itself as elements are added or removed.
3. Multiple Priorities: Each element has a priority value, which determines its position.
4. Flexible Implementation: Can be implemented using arrays, linked lists, heaps, or
binary trees.

Page 13 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.3.3.2. Basic Operations of Priority Queue
Priority queues support the following operations:
1. Insert (Enqueue): Adds an element with a given priority.
2. Delete (Dequeue): Removes the element with the highest priority.
3. Peek: Returns the highest priority element without removing it.
4. isEmpty: Checks if the queue is empty.
5. Change Priority: Updates the priority of an existing element (optional in advanced
implementations).

Types of Priority Queues

1. Max Priority Queue
In a max priority queue, the element with the highest priority value is served first.
2. Min Priority Queue
In a min priority queue, the element with the lowest priority value is served first. This is
commonly used in algorithms like Dijkstra’s shortest path.

2.3.3.3. Implementation of Priority Queue

Priority queues can be implemented in several ways, each with different performance
characteristics.
1. Using Arrays or Linked Lists
 Unsorted Array/List: Insertion is fast (O(1)), but deletion requires scanning the entire
structure (O(n)).
 Sorted Array/List: Deletion is fast (O(1)), but insertion requires finding the correct
position (O(n)).
2. Using Heaps
The most efficient and common implementation is using a binary heap, which is a complete
binary tree that maintains the heap property:
 Max Heap: Parent node is greater than or equal to its children.
 Min Heap: Parent node is less than or equal to its children.

Page 14 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Operations in Heap-Based Priority Queue:
 Insert: O(log n)
 Delete Max/Min: O(log n)
 Peek: O(1)

2.3.3.4. Applications of Priority Queue

Priority queues are used in a wide range of real-world and computational scenarios:
1. CPU Scheduling
Operating systems use priority queues to manage processes. High-priority tasks are
executed before lower-priority ones.
2. Dijkstra’s Algorithm
Used in graph theory to find the shortest path. A min-priority queue helps select the
next node with the smallest tentative distance.
3. Bandwidth Management
Routers and switches use priority queues to manage network traffic, ensuring critical
packets are transmitted first.
4. Emergency Systems
In hospital management or disaster response, patients or cases are handled based on
severity.
5. Event-Driven Simulations
Priority queues manage events based on their scheduled time or importance.
6. Data Compression (Huffman Coding)

Priority queues are used to build Huffman trees for efficient data encoding.

2.3.3.5. Advantages of Priority Queue

 Efficient Task Management: Ensures important tasks are handled first.
 Flexible Design: Can be tailored to specific needs (max or min priority).
 Optimized Performance: Heap-based implementations offer logarithmic time
complexity.
 Widely Applicable: Useful in both system-level and application-level programming.

2.3.3.6. Disadvantages of Priority Queue

 Complex Implementation: More complex than linear queues.
 Overhead in Maintenance: Requires reordering after insertion or deletion.
 Limited Direct Access: Cannot access arbitrary elements easily.

2.3.4. DEQUE (Double ended Queue)

A deque, short for double-ended queue, is a versatile linear data structure that allows
insertion and deletion of elements from both ends—front and rear. Unlike a regular
queue that follows the First In, First Out (FIFO) principle and restricts operations to
one end, a deque provides greater flexibility by supporting operations at both ends.
Deques are widely used in scenarios where elements need to be added or removed

Page 15 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
from either side efficiently. They are particularly useful in implementing algorithms
that require bidirectional access, such as sliding window problems, palindrome
checking, and task scheduling. Understanding deques is essential for mastering
advanced data structures and optimizing performance in real-time systems.

Types of Deque
There are two main types of deques:
1. Input-Restricted Deque
 Insertion is allowed only at one end (usually rear).
 Deletion is allowed from both ends.
2. Output-Restricted Deque
 Deletion is allowed only at one end (usually front).
 Insertion is allowed at both ends.
These variations allow deques to be tailored to specific application needs.

2.3.4.1. Characteristics of Deque

1. Bidirectional Access: Elements can be inserted or removed from both front and rear.
2. Linear Structure: Elements are arranged in a sequence.
3. Flexible Operations: Supports both stack-like (LIFO) and queue-like (FIFO) behavior.
4. Efficient Performance: Constant time insertion and deletion at both ends.

2.3.4.2. Basic Operations of Deque

A deque supports the following operations:
1. InsertFront: Adds an element at the front.
2. InsertRear: Adds an element at the rear.
3. DeleteFront: Removes an element from the front.
4. DeleteRear: Removes an element from the rear.
5. PeekFront: Returns the front element without removing it.
6. PeekRear: Returns the rear element without removing it.
7. isEmpty: Checks if the deque is empty.

Page 16 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
8. isFull: Checks if the deque is full (in array-based implementation).

2.3.4.3. Applications of Deque

Deques are used in a wide range of real-world and computational scenarios:
1. Sliding Window Algorithms
Used in problems where a fixed-size window moves over data, such as finding
maximums or minimums in subarrays.
2. Palindrome Checking
Deques allow checking characters from both ends, making them ideal for
palindrome validation.
3. Task Scheduling
Operating systems use deques to manage tasks that can be added or
removed from either end.
4. Undo/Redo Functionality
Applications like text editors use deques to manage history for undo and redo
operations.
5. Browser History Navigation
Deques help manage forward and backward navigation efficiently.

2.3.4.4. Advantages of Deque

 Flexible Access: Supports both ends for insertion and deletion.
 Efficient Performance: Constant time operations at both ends.
 Versatile Use: Can mimic both stacks and queues.
 Dynamic Memory Use: Linked list implementation allows dynamic resizing.

2.3.4.5. Disadvantages of Deque

 Complex Implementation: More complex than simple queues or stacks.
 Fixed Size Limitation: Array-based implementation has a fixed capacity.
 Pointer Management: Requires careful handling of front and rear pointers.

Page 17 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.4. Examples on the Application of Stacks & Queues
2.4.1. Stack Application Examples
 Conversion of Infix Expression in to its equivalent Post-Fix Expression
 Evaluation of Post- Fix Expression
 Conversion of Infix Expression inn to its equivalent Pre-Fix (POLISH) Expression
 Evaluation of Pre- Fix Expression
 Balanced Parenthesis Checking Problem

Infix, prefix, and postfix expressions, commonly used in computer science and
mathematics:
1. Infix Expression
 Definition: Operators are written between the operands.
 Example: A + B
 Usage: This is the most common notation used in arithmetic and algebra.
 Challenge: Requires parentheses and operator precedence rules to avoid ambiguity.
2. Prefix Expression (Polish Notation)
 Definition: Operators are written before the operands.
 Example: + A B
 Advantage: No need for parentheses; evaluation order is clear.
 Usage: Used in some compilers and calculators.

3. Postfix Expression (Reverse Polish Notation)

 Definition: Operators are written after the operands.
 Example: A B +
 Advantage: Easy to evaluate using a stack; no need for parentheses.
 Usage: Common in stack-based programming languages and calculators.

2.4.1.1. Conversion of Infix Expression in to its equivalent Post-Fix Expression

Steps for Conversion of In-fix Expression in to its equivalent post fix expression, are as
follows:
1. Initialize
a. Create an empty stack for operators and PUSH ‘(‘ in to it add ‘)’ at the end of infix
expression.
b. Create an empty output list for the postfix expression.
2. Scan the Infix Expression from Left to Right
For each symbol in the expression:
a. IF Operand (e.g., A, B, 1, 2), THEN
1. Add directly to the output.
b. IF Left Parenthesis ‘(‘, THEN
1. Push onto the stack.
c. IF Right Parenthesis ‘)’, THEN
1. Pop from the stack and add to output until a left parenthesis ‘(‘ is
encountered.
2. Discard the left parenthesis.

Page 18 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
d. IF Operator (e.g., +, -, , /, ^), THEN
1. While the stack is not empty and the top of the stack has higher or equal
precedence,
 pop from the stack and add to output.
2. Then push the current operator onto the stack.
3. After Scanning All Symbols, Pop all remaining operators from the stack and add to output.
4. End

Example 1. Convert the Infix: A + B * C in to its equivalent Postfix expressions.

Given infix Expression: A + B * C)

Symbol Stack Postfix Expression Remarks
Scanned
A ( A Put in to Expression (Step 2.a)
+ (+ A ‘+’ PUSH in to STACK (Step 2.d)
B (+ AB Put in to Expression(Step 2.a)
* (+* AB ‘*’ PUSH in to STACK(Step 2.d)
C (+* ABC Put in to Expression(Step 2.a)
) EMPTY ABC*+ POP all remaining operators from
STACK(Step 2.c)
Equivalent Postfix Expression: A B C * +

Example 2. Convert the Infix: A + B/C- D*E - F in to its equivalent Postfix expressions.
Given: Infix Expression : A + B/C- D*E – F)
Symbol Stack Postfix Remarks
Scanned Expression
A ( A Put in to Expression(Step 2.a)
+ (+ A ‘+’ PUSH in to STACK(Step 2.d)
B (+ AB Put in to Expression(Step 2.a)
/ (+/ AB ‘/’ PUSH in to STACK(Step 2.d)
C (+/ ABC Put in to Expression(Step 2.a)
- (- ABC/+ Operator Precedence Resolved (Step 2.d)
D (- ABC/+D Put in to Expression(Step 2.a)
* (-* ABC/+D ‘*’ PUSH in to STACK(Step 2.d)
E (-* ABC/+DE Put in to Expression(Step 2.a)
- (- ABC/+DE*- Operator Precedence Resolved (Step 2.d)
F (- ABC/+DE*-F Put in to Expression(Step 2.a)
) EMPTY ABC/+DE*-F- POP all remaining operators from STACK(Step 2.c)
Equivalent Postfix Expression: ABC/+DE*-F-

Page 19 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.4.1.2. Evaluation of Post- Fix Expression with the help of Stack
Steps for Evaluation of Post-Fix Expression with the help of STACK are as follows:
1. Initialize an empty stack.
2. Scan the postfix expression from left to right.
3. For each symbol in the expression:
a. If operand (e.g., number or variable):
→ Push it onto the stack.
b. If operator (e.g., +, -, *, /):
→ Pop the top two elements from the stack.
→ Apply the operator: “second_operand” “operator” “first_operand”.
→ Push the result back onto the stack.
4. After the entire expression is scanned, the result will be the only element left in the stack.

Example 1: Evaluate the given Postfix expression using stack “5 6 2 + * 12 4 / -”

Symbol Stack Remarks

Scanned
5 5 PUSH in to STACK(Step 3.a.)
6 56 PUSH in to STACK(Step 3.a.)
2 562 PUSH in to STACK(Step 3.a.)
+ 58 POP last two operands and PUSH their
evaluation result on STACK (Step 3.b)
* 40 POP last two operands and PUSH their
evaluation result on STACK (Step 3.b)
12 40 12 PUSH in to STACK(Step 3.a.)
4 40 12 4 PUSH in to STACK(Step 3.a.)
/ 40 3 POP last two operands and PUSH their
evaluation result on STACK (Step 3.b)
- 37 POP last two operands and PUSH their
evaluation result on STACK (Step 3.b)
EMPTY POP the result (Step 4)
Answer is : 37

Example 2: Evaluate the given Postfix expression using stack “8 4 + 6 2 - *”

Symbol Stack Remarks

Scanned
8 8 PUSH in to STACK(Step 3.a.)
4 84 PUSH in to STACK(Step 3.a.)
+ 12 POP last two operands and PUSH their
evaluation result on STACK (Step 3.b)
6 12 6 PUSH in to STACK(Step 3.a.)
2 12 6 2 PUSH in to STACK(Step 3.a.)

Page 20 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
- 12 4 POP last two operands and PUSH their
evaluation result on STACK (Step 3.b)
* 48 POP last two operands and PUSH their
evaluation result on STACK (Step 3.b)
EMPTY POP the result
Answer is: 96

2.4.1.3. Conversion of Infix Expression in to its equivalent Post-Fix Expression

Steps for Conversion of In-fix Expression in to its equivalent post fix expression, are as
follows:
1. Reverse the infix expression. While reversing, swap every ( with ) and vice versa.
Ex : If the Original is (A + B) * (C - D), then Reversed: (D - C) * (B + A)
2. Convert the reversed expression to postfix using the standard infix-to-postfix algorithm.
If the Reversed Infix: (D - C) * (B + A), then the Postfix of reversed :DC-BA+*
3. Reverse the postfix expression to get the final prefix expression:
Reverse: * + A B - C D

Example 1. Convert the Infix: (A + B) * (C - D) in to its equivalent Prefix expressions.

Given infix Expression: (A + B) * (C - D)

1. Reverse the infix expression : (D - C) * (B + A)
2. Convert the reversed expression to postfix
3. The reverse infix Expression: (D - C) * (B + A))

Symbol Stack Postfix Expression Remarks

Scanned
( (( ‘(’ PUSH in to STACK(Step 2.b)
D (( D Put in to Expression(Step 2.a)
- ((- D ‘-’ PUSH in to STACK(Step 2.d)
C ((- DC Put in to Expression(Step 2.a)
) ( DC- ‘)’ parenthesis, POP all symbol and put in to
expression till ‘(‘ (Step 2.c)
* (* DC- ‘*-’ PUSH in to STACK(Step 2.d)
( (*( DC- ‘(’ PUSH in to STACK(Step 2.b)
B (*( DC-B Put in to Expression(Step 2.a)
+ (*(+ DC-B ‘+’ PUSH in to STACK(Step 2.d)
A (*(+ DC-BA Put in to Expression(Step 2.a)
) (* DC-BA+ ‘)’ parenthesis, POP all symbol and put in to
expression till ‘(‘ (Step 2.c)
) EMPTY DC-BA+* POP all remaining operators from
STACK(Step 2.c)
Equivalent Postfix Expression: DC-BA+*
3. Reverse the postfix expression to get the final prefix expression
*+AB-CD

Page 21 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.4.1.4. Evaluation of Prefix Expression with the help of Stack
The steps for Evaluation of Pre-Fix Expression with the help of STACK are as follows:
1. Initialize an empty stack.
2. Scan the postfix expression from right to left.
3. For each symbol in the expression:
i. If operand (e.g., number or variable):
→ Push it onto the stack.
ii. If operator (e.g., +, -, *, /):
→ Pop the top two elements from the stack.
→ Apply the operator: “First_operand” “operator” “Second_operand”.
→ Push the result back onto the stack.
4. After the entire expression is scanned, the result will be the only element left in the
stack.

Example 2: Evaluate the given Postfix expression using stack “+ * 2 3 / 9 3”

Symbol Stack Remarks
Scanned
3 3 PUSH in to STACK(Step 3.i.)
9 39 PUSH in to STACK(Step 3.i.)
/ 3 POP last two operands and PUSH their evaluation
result on STACK (Step 3.ii)
3 33 PUSH in to STACK(Step 3.i.)
2 332 PUSH in to STACK(Step 3.i.)
* 36 POP last two operands and PUSH their evaluation
result on STACK (Step 3.ii)
+ 9 POP last two operands and PUSH their evaluation
result on STACK (Step 3.ii)
EMPTY POP the result
Answer is: 9

2.4.1.5. Balanced Parenthesis Checking Problem

The Balanced Parenthesis Checking Problem is a classic problem in computer science,
especially in compiler design and expression parsing. It involves verifying whether every
opening bracket (like (, {, [) in an expression has a corresponding and correctly placed closing
bracket (), }, ])
The Steps for checking the balanced parenthesis is

1) Initialize an empty stack.

2) Scan the expression from left to right.
3) For each character:
a) If it is an opening bracket ((, {, [), push it onto the stack.
b) If it is a closing bracket (), }, ]):
i) Check if the stack is not empty.
ii) Pop the top element and check if it matches the type of closing bracket.
iii) If it doesn’t match or the stack is empty, the expression is not balanced.
4) After scanning, if the stack is empty, the expression is balanced. Otherwise, it is not
balanced.

Page 22 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Example 1. Check whether the given expression contains balanced parenthesis or not.
Expression: { [ ( ) ] }

Symbol Stack Remarks

Scanned
{ { PUSH in to STACK(Step 3.a.)
[ {[ PUSH in to STACK(Step 3.a.)
( {[( PUSH in to STACK(Step 3.a.)
) {[ POP the top element (Step 3.b.ii)
] { POP the top element (Step 3.b.ii)
} EMPTY POP the top element (Step 3.b.ii)
The given expression contains the balanced parenthesis

Example 2. Check whether the given expression contains balanced parenthesis or not.
Expression: { [ ( {) ] }

Symbol Stack Remarks

Scanned
{ { PUSH in to STACK(Step 3.a.)
[ {[ PUSH in to STACK(Step 3.a.)
( {[( PUSH in to STACK(Step 3.a.)
{ {[({ PUSH in to STACK(Step 3.a.)
) {[({ The Expression does not contains the balanced
parenthesis (Step 3.b.iii)
The given expression does not contains the balanced parenthesis.

2.4.2. Examples on the Application of Queues (Josephus Problem)

The Josephus Problem is a famous theoretical puzzle in mathematics and computer science,
rooted in history and rich in algorithmic significance. The problem is named after Flavius
Josephus, a Jewish historian who lived during the 1st century AD. According to legend, during
the Jewish-Roman War, Josephus and his 40 soldiers were trapped in a cave by Roman forces.
Rather than surrender, they chose to commit suicide in a specific order. They formed a circle
and every third person was to be killed until only one remained. Josephus, not wanting to die,
figured out the position he should stand in to be the last survivor. This story gave rise to the
mathematical formulation of the problem. It involves a group of people standing in a circle,
where every k-th person is eliminated in a fixed sequence until only one person remains. The
challenge is to determine the position of the survivor. This problem is not only a fascinating
exercise in logic and recursion but also has practical applications in areas such as data
structures, game theory, and even cryptography.

It is defined as, Given: A group of people standing in a circle, numbered from 1 to n. starting
from a given position, every k-th person is eliminated from the circle, and the process
continues around the circle until only one person remains.
Goal: To determine the position of the last remaining person.

Page 23 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Example:
If there are 7 (n = 7) people and every 3rd (k = 3) person is eliminated:
 People: 1 2 3 4 5 6 7
 Elimination order: 3 → 6 → 2 → 7 → 5 → 1 → 4 survives
4 is the winner in this problem.
Applications
1. Computer Science:
o Used in data structures like circular linked lists.
o Helps understand recursion and modular arithmetic.
o Useful in operating systems for scheduling algorithms.
2. Game Theory:
o Models elimination games and strategic positioning.
3. Cryptography:
o Concepts of safe positions and elimination can be applied in secure communication
protocols.
4. Simulation and Modelling:
o Used in simulations involving circular processes or turn-based systems.
Variants of the Problem
Several variations of the Josephus problem exist:
 Changing step size: Instead of a fixed k, the step size changes dynamically.
 Multiple survivors: Determine the last m survivors instead of just one.
 Starting from different positions: The counting starts from a position other than
1.
 Bidirectional elimination: Elimination alternates between clockwise and counter-
clockwise.
These variants add complexity and are often used in advanced algorithmic challenges.

Page 24 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.5. Recursion

Recursion is a fundamental concept in computer science and mathematics where a

function calls itself to solve a problem. The idea is to break down a complex problem into
smaller, more manageable sub-problems of the same type.

A recursive function must have two essential parts: Base Case and Recursive Case.
Base Case: The condition under which the recursion stops. Without it, the function would
call itself indefinitely, leading to a stack overflow.
Recursive Case: The part where the function calls itself with a modified argument, moving
toward the base case.

Example : Consider the example of calculating factorial of n.

factorial(n):
IF n = 0, THEN
return 1 # Base case
ELSE
return n * factorial(n - 1) # Recursive case

Let’s say we call factorial(3):

 factorial(3) → 3 * factorial(2)
 factorial(2) → 2 * factorial(1)
 factorial(1) → 1 * factorial(0)
 factorial(0) → 1 (base case reached)
Now the calls return in reverse:
 factorial(1) returns 1 * 1 = 1
 factorial(2) returns 2 * 1 = 2
 factorial(3) returns 3 * 2 = 6

In recursive functions like factorial calculation, the stack plays a crucial role in managing
the flow of execution and memory. When a recursive function is called, the system uses a
call stack to keep track of each function invocation. Each time the function calls itself, a
new frame is pushed onto the stack, containing the function’s parameters, local variables,
and the return address. This continues until the base case is reached, which is the
condition that stops further recursion. For example, in calculating the factorial of a
number nn, the function Factorial(n) calls Factorial(n-1), which calls Factorial(n-2), and so
on, until it reaches Factorial(0), which returns 1. At this point, the stack begins to unwind.
The return value of Factorial(0) is passed back to Factorial(1), which multiplies it by 1 and
returns the result to Factorial(2), and this process continues until the original call
Factorial(n) receives the final result. Each step of this unwinding involves popping the top
frame off the stack and using its stored data to compute the result. This mechanism
ensures that each recursive call has its own isolated environment, preventing interference
between calls. However, because each call consumes stack memory, deep recursion can

Page 25 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
lead to stack overflow if the base case is not reached quickly or if the input is too large.
The stack also preserves the order of operations, ensuring that the last function called is
the first to return, which is essential for correctly computing values in recursive
algorithms. In the case of factorial, the multiplication happens during the unwinding
phase, meaning the actual computation is deferred until the base case is resolved. This
behavior highlights the importance of understanding stack dynamics when working with
recursion. The stack not only manages memory but also controls the logical flow of
recursive functions, making it a fundamental concept in programming. Without the stack,
recursion would not be possible, as there would be no way to remember where each
function left off or how to return to the previous state. Thus, the stack is the backbone of
recursive execution, enabling complex problems to be solved elegantly by breaking them
down into simpler sub-problems and systematically resolving them through a structured
and memory-managed process.

2.5.1. Types of Recursion

There are multiple types of recursion based on the method of call to the recursive
function.

1. Direct Recursion: A function calls itself directly.

1. Example 1: Factorial Calculation

Function Factorial(n)
If n = 0, Then
Return 1
Else
Return n * Factorial(n - 1)
End Function

2. Example 2: Countdown
Function Countdown(n)
If n == 0, Then
Print "Blast off!"
Else
Print n
Countdown(n - 1)
End Function

2. Indirect Recursion: A function calls another function, which eventually calls the
original function.

1. Example 1: Function A and B

If n > 0, Then
Print "A:", n
B(n - 1)
End Function

Page 26 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Function B(n)
If n > 0, Then
Print "B:", n
A(n // 2)
End Function

2. Example 2: Even-Odd Check

If n = 0
Return True
Else
Return IsOdd(n - 1)
End Function

Function IsOdd(n)
If n == 0
Return False
Else
Return IsEven(n - 1)
End Function

3. Tail Recursion: The recursive call is the last operation in the function.

1. Example 1: Tail Recursive Factorial

Function TailFactorial(n, accumulator)
If n = 0, Then
Return accumulator
Else
Return TailFactorial(n - 1, n * accumulator)
End Function

2. Example 2: Tail Recursive Sum

Function TailSum(n, total)
If n = 0, Then
Return total
Else
Return TailSum(n - 1, total + n)
End Function

4. Head Recursion: The recursive call is made before any other operations.

1. Example 1: Print Numbers in Ascending Order

Function PrintAscending(n)
If n > 0, Then
PrintAscending(n - 1)
Print n
End Function

Page 27 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2. Example 2: Head Recursive Sum
If n = 0, Then
Return 0
Else
result = HeadSum(n - 1)
Return result + n
End Function

5. Tree Recursion: A function makes multiple recursive calls.

1. Example 1: Fibonacci Series
Function Fibonacci(n)
If n <= 1
Return n
Else
Return Fibonacci(n - 1) + Fibonacci(n - 2)
End Function

2.5.2. Applications of Recursion

Recursion is widely used in:
 Mathematics: Factorials, Fibonacci numbers, permutations, combinations.
 Data Structures: Trees, graphs, linked lists.
 Algorithms: Divide and conquer (e.g., Merge Sort, Quick Sort), backtracking (e.g.,
Sudoku solver, N-Queens problem).
 File Systems: Navigating directories and subdirectories.
 Artificial Intelligence: Game trees, decision trees.

2.5.3. Advantages of Recursion

 Simplicity: Recursive solutions are often more elegant and easier to understand.
 Problem Decomposition: Naturally breaks problems into smaller sub-problems.
 Useful for Tree/Graph Traversal: Recursion is ideal for exploring hierarchical
structures.

2.5.4. Disadvantages of Recursion

 Performance: Recursive calls use stack memory. Deep recursion can lead to stack
overflow.
 Overhead: Each function call adds overhead due to memory and time.
 Difficult to Debug: Tracing recursive calls can be complex.

2.5.5. Recursive vs Iterative Approach

Feature Recursive Iterative
Code Simplicity Often simpler and cleaner Can be more complex
Memory Usage Uses more memory (call stack) Uses less memory
Speed Slower due to function call overhead Faster in many cases
Risk Stack overflow No stack overflow

Page 28 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
2.6. Exercise

Practice Questions:
1. What are linear data structures? Explain their key characteristics.
2. Define an array. What are its advantages and disadvantages?
3. What is a stack? Describe its basic operations.
4. Explain the LIFO principle with a real-life example.
5. What are the applications of stacks in computer science?
6. Describe the structure and types of linked lists.
7. What is a queue? How does it differ from a stack?
8. Explain the FIFO principle with a suitable analogy.
9. What are the types of queues? Briefly describe each.
10. What is a circular queue? How does it overcome the limitations of a linear queue?
11. Explain the concept and operations of a priority queue.
12. What is a deque? How is it different from a regular queue?
13. Write a short note on the applications of linear data structures in operating systems.
14. Compare arrays and linked lists in terms of access time and memory usage.
15. What is the role of the call stack in recursion?
16. Explain the algorithm for converting an infix expression to postfix using a stack.
17. How a postfix expression is evaluated using a stack?
18. What is the balanced parenthesis checking problem? How is it solved using stacks?
19. Describe the Josephus problem and its relevance to data structures.
20. What are the different types of recursion? Give examples of each.

Infix Expression Conversion Questions

1. Decode the arithmetic intent: Convert the infix expression “A + B * C” into its prefix and
postfix forms using a stack.
2. Parentheses puzzle: Given the expression “(A + B) * (C - D)”, use stack operations to derive its
prefix and postfix equivalents.
3. Operator hierarchy challenge: Transform the infix “A + B / C - D * E” into prefix and postfix
formats, respecting operator precedence.
4. Nested expression unraveling: Convert the infix “((A + B) * C) / (D - E)” into prefix and postfix
using stack-based parsing.
5. Expression with exponentiation: Given “A ^ B + C * D”, apply stack logic to convert it into
prefix and postfix notation.
6. Balanced brackets test: Convert the infix “((A + B) * (C + D)) / E” into prefix and postfix forms
using stack operations.
7. Multi-level precedence: Transform “A + (B * (C + D)) – E” into prefix and postfix using stack-
based conversion.
8. Complex expression evaluation: Convert the infix “A + B * C ^ D - E / F” into prefix and postfix
using stack precedence rules.
9. Expression with all operators: Given “A + B - C * D / E ^ F”, use stack-based conversion to
derive prefix and postfix forms.
10. Logical structure breakdown: Convert the infix “((A + B) * (C - D)) ^ (E + F)” into prefix and
postfix using stack-based parsing.

Page 29 of 30
 SVKMs NMIMS
Mukesh Patel School of Technology Management and Engineering, Shirpur
Course : Data Structures and Algorithms
--------------------------------------------------------------------------------------------------------
Postfix Expression Evaluation (Using Stack)
1. Stack it up: Evaluate the postfix expression “5 3 + 8 2 - *” using a stack. Show intermediate
stack states.
2. Arithmetic adventure: Given the postfix expression “6 2 / 3 4 * +”, compute the final result
using stack operations.
3. Operator overload: Evaluate “7 2 3 * - 4 +” using a stack. What is the final value?
4. Nested logic: Use a stack to evaluate the postfix expression “9 3 1 + / 2 *”.
5. Expression unraveling: Evaluate the postfix expression “4 5 + 6 2 / -” using stack-based steps.

Prefix Expression Evaluation (Using Stack)

1. Prefix puzzle: Evaluate the prefix expression “+ * 2 3 / 9 3” using a stack. Show each step.
2. Reverse logic: Given the prefix expression “- + 7 * 4 5 6”, compute the result using stack
evaluation.
3. Stack reversal: Evaluate the prefix expression “+ 5 * - 6 2 3” using stack-based logic.
4. Operator-first challenge: Use a stack to evaluate the prefix expression “* + 2 3 - 8 4”.
5. Prefix breakdown: Evaluate the prefix expression “/ * + 1 2 3 4” using stack operations.

Page 30 of 30