MODULE – I

Introduction to Data Structures- Recursion and Stack

Definition:

Data structures are a specific way of organizing data in a specialized format on a

computer so that the information can be organized, processed, stored, and retrieved
quickly and effectively.
Note:
 The idea is to reduce the space and time complexities of different tasks.
 The choice of a good data structure makes it possible to perform a variety of critical
operations effectively.
 An efficient data structure also uses minimum memory space and execution time to
process the structure.
Need of Data Structures:
 Data structure modification is easy.
 It requires less time.
 Save storage memory space.
 Data representation is easy.
 Easy access to the large database.
Classification of Data Structures:
Classification/Types of Data Structures:
 Linear Data Structure
 Non-Linear Data Structure.
Linear Data Structure:
A linear data structure is a type of data structure that stores the data linearly or sequentially.
Example: lists, stack, queue, etc.
Non-Linear Data Structure
It is a data structure where the data elements don't stay arranged linearly or sequentially.
Example: tree, graph, table, etc.

Abstract Data Type (ADT)

An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and
behaviours for a data structure, without specifying how these operations are
implemented or how data is organized in memory.
Note:
 The definition of ADT only mentions what operations are to be performed but not
how these operations will be implemented. It does not specify how data will be
organized in memory and what algorithms will be used for implementing the
operations.
 It is called “abstract” because it provides an implementation-independent view.
 The process of providing only the essentials and hiding the details is known as
abstraction.

Model for an ADT:

Examples of ADT:
List ADT, Stack ADT, and Queue ADT.
The List ADT (Abstract Data Type) is a sequential collection of elements that supports a set
of operations without specifying the internal implementation. It provides an ordered way to
store, access, and modify data.
10 20 30 40 50 60
The List ADT need to store the required data in the sequence and should have the following
operations:
 get (): Return an element from the list at any given position.
 insert (): Insert an element at any position in the list.
 remove (): Remove the first occurrence of any element from a non-empty list.
 removeAt (): Remove the element at a specified location from a non-empty list.
 replace (): Replace an element at any position with another element.
 size (): Return the number of elements in the list.
 is Empty (): Return true if the list is empty; otherwise, return false.
 is Full (): Return true if the list is full; otherwise, return false.
The Stack ADT is a linear data structure that follows the LIFO (Last In, First Out) principle.
It allows elements to be added and removed only from one end, called the top of the stack.
In Stack ADT, the order of insertion and deletion should be according to the FILO or LIFO
Principle. Elements are inserted and removed from the same end, called the top of the stack.

10
 20

30

40

50

It should also support the following operations:

 push (): Insert an element at one end of the stack called the top.
 pop (): Remove and return the element at the top of the stack, if it is not empty.
 peek (): Return the element at the top of the stack without removing it, if the stack is
not empty.
 size (): Return the number of elements in the stack.
 is Empty (): Return true if the stack is empty; otherwise, return false.
 is Full (): Return true if the stack is full; otherwise, return false.
The Queue ADT is a linear data structure that follows the FIFO (First In, First Out) principle.
It allows elements to be inserted at one end (rear) and removed from the other end (front).

10 20 30 40 50
Rear front
The Queue ADT follows a design similar to the Stack ADT, but the order of insertion and
deletion changes to FIFO. Elements are inserted at one end (called the rear) and removed
from the other end (called the front).
It should support the following operations:
 enqueue (): Insert an element at the end of the queue.
 dequeue (): Remove and return the first element of the queue, if the queue is not
empty.
 peek (): Return the element of the queue without removing it, if the queue is not
empty.
 size (): Return the number of elements in the queue.
 is Empty(): Return true if the queue is empty; otherwise, return false.

Features of ADT
Abstract data types (ADTs) are a way of encapsulating data and operations on that data into a
single unit.
Some of the key features of ADTs include:
Abstraction: The user does not need to know the implementation of the data structure only
essentials are provided.
Better Conceptualization: ADT gives us a better conceptualization of the real world.
Robust: The program is robust and has the ability to catch errors.
Encapsulation: ADTs hide the internal details of the data and provide a public interface for
users to interact with the data. This allows for easier maintenance and modification of the
data structure.
Data Abstraction: ADTs provide a level of abstraction from the implementation details of
the data. Users only need to know the operations that can be performed on the data, not how
those operations are implemented.
Data Structure Independence: ADTs can be implemented using different data structures,
such as arrays or linked lists, without affecting the functionality of the ADT.
Information Hiding: ADTs can protect the integrity of the data by allowing access only to
authorized users and operations. This helps prevent errors and misuse of the data.
Modularity: ADTs can be combined with other ADTs to form larger, more complex data
structures. This allows for greater flexibility and modularity in programming.

Advantages of ADT
Encapsulation: ADTs provide a way to encapsulate data and operations into a single unit,
making it easier to manage and modify the data structure.
Abstraction: ADTs allow users to work with data structures without having to know the
implementation details, which can simplify programming and reduce errors.
Data Structure Independence: ADTs can be implemented using different data structures,
which can make it easier to adapt to changing needs and requirements.
Information Hiding: ADTs can protect the integrity of data by controlling access and
preventing unauthorized modifications.
Modularity: ADTs can be combined with other ADTs to form more complex data structures,
which can increase flexibility and modularity in programming.

Disadvantages of ADT
Overhead: Implementing ADTs can add overhead in terms of memory and processing,
which can affect performance.
Complexity: ADTs can be complex to implement, especially for large and complex data
structures.
Learning Curve: Using ADTs requires knowledge of their implementation and usage, which
can take time and effort to learn.
Limited Flexibility: Some ADTs may be limited in their functionality or may not be suitable
for all types of data structures.
Cost: Implementing ADTs may require additional resources and investment, which can
increase the cost of development.

ADT Implementations and Examples:

There are two basic structures we can use to implement an ADT list: arrays and linked lists.
Array Implementations:
Array Implementations In an array, the sequentiality of a list is maintained by the order
structure of elements in the array (indexes).
Although searching an array for an individual element can be very efficient, addition and
deletion of elements are complex and inefficient processes.
For this reason, arrays are seldom used, especially when the list changes frequently.
In addition, array implementations of nonlinear lists can become excessively large,
especially when there are several successors for each element.
Advantages of Array Implementation:
 Easy to implement.
 Memory is saved as pointers are not involved.
Disadvantages of Array Implementation:
 It is not dynamic i.e., it doesn’t grow and shrink depending on needs at runtime.
 The total size of the stack must be defined beforehand.
Linked List Implementations
A linked list is an ordered collection of data in which each element contains the location of
the next element or elements.
In a linked list, each element contains two parts: data and one or more links. The data part
holds the application data—the data to be processed.
Links are used to chain the data together. They contain pointers that identify the next element
or elements in the list.
We can use a linked list to create linear and non-linear structures. In linear linked lists, each
element has only zero or one successor.
In non-linear linked lists, each element can have zero, one, or more successors.
Advantages:
 Data are easily inserted and deleted.
 It is not necessary to shift elements of a linked list to make room for a new element or
to delete an element.
Disadvantages:
because the elements are no longer physically sequenced, we are limited to sequential
searches:1 we cannot use a binary search.
Note: We define an empty list as a null list pointer.

Examples:
Stack data structure can be implemented in two ways. They are as follows...
1. Using Array
2. Using Linked List

Stack Operations using Array

Steps to create an empty stack.
 Step 1: Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
 Step 2: Declare all the functions used in stack implementation.
 Step 3: Create a one-dimensional array with fixed size (int stack [SIZE])
 Step 4: Define a integer variable 'top' and initialize with '-1'. (int top = -1)
 Step 5: In main method display menu with list of operations and make suitable
function calls to perform operation selected by the user on the stack.
push(value) - Inserting value into the stack in a stack, push () is a function used to insert an
element into the stack. In a stack, the new element is always inserted at top position. Push
function takes one integer value as parameter and inserts that value into the stack.
Steps to push an element on to the stack...
 Step 1: Check whether stack is FULL. (top == SIZE-1)
 Step 2: If it is FULL, then display "Stack is FULL!!! Insertion is not possible!!!" and
terminate the function.
 Step 3: If it is NOT FULL, then increment top value by one (top++) and set stack[top]
to value (stack[top] = value).
pop () - Delete a value from the Stack In a stack, pop () is a function used to delete an
element from the stack. In a stack, the element is always deleted from top position. Pop
function does not take any value as parameter.
steps to pop an element from the stack...
 Step 1: Check whether stack is EMPTY. (top == -1)
 Step 2: If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not possible!!!"
and terminate the function.
 Step 3: If it is NOT EMPTY, then delete stack[top] and decrement top value by one
(top--).
display () - Displays the elements of a Stack
We can use the following steps to display the elements of a stack...
 Step 1: Check whether stack is EMPTY. (top == -1)
 Step 2: If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function.
  Step 3: If it is NOT EMPTY, then define a variable 'i' and initialize with top. Display
stack[i] value and decrement i value by one (i--).
 Step 4: Repeat above step until i value becomes '0'.

// C code to implement stack using array

void push (int value)
{
if (top == SIZE-1)
printf ("\n Stack is Full!!! Insertion is not possible!!!");
else
{
top++;
stack[top] = value;
printf("\n Insertion success!!!");
}
}
void pop ()
{
if (top == -1)
printf ("\n Stack is Empty!!! Deletion is not possible!!!");
else
{
Printf ("\n Deleted: %d", stack[top]);
top--;
}
}
void display ()
{
If (top == -1)
printf ("\n Stack is Empty!!!");
else
{
int i;
printf("\nStack elements are:\n");
for(i=top; i>=0; i--)
printf("%d\n",stack[i]);
}
}

Stack operations using Linked List

The major problem with the stack implemented using array is the amount of data must be
specified at the beginning of the implementation itself.
It is not suitable, when we don't know the size of data which we are going to use.
A stack data structure can be implemented by using linked list data structure can be used for
unlimited number of values.
That means, stack implemented using linked list works for variable size of data.
In linked list implementation of a stack, every new element is inserted as 'top' element.
That means every newly inserted element is pointed by 'top'.
Whenever we want to remove an element from the stack, simply remove the node which is
pointed by 'top' by moving 'top' to its next node in the list.
The next field of the first element must be always NULL.
Example:
Top

99

50

32

25 N

In above example, the last inserted node is 99 and the first inserted node is 25. The order of
elements inserted is 25, 32,50 and 99.
Operations To implement stack using linked list, we need to set the following things before
implementing actual operations.
 Step 1: Include all the header files which are used in the program. And declare all the
user defined functions.
 Step 2: Define a 'Node' structure with two members data and next.
 Step 3: Define a Node pointer 'top' and set it to NULL.
 Step 4: Implement the main method by displaying Menu with list of operations and
make suitable function calls in the main method.

push(value) - Inserting an element into the Stack

steps to insert a new node into the stack...
 Step 1: Create a newNode with given value.
 Step 2: Check whether stack is Empty (top == NULL)
 Step 3: If it is Empty, then set newNode → next = NULL.
 Step 4: If it is Not Empty, then set newNode → next = top.
 Step 5: Finally, set top = newNode

Pop () - Deleting an Element from a Stack

steps to delete a node from the stack...
 Step 1: Check whether stack is Empty (top == NULL).
 Step 2: If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and
terminate the function
 Step 3: If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
 Step 4: Then set 'top = top → next'.
 Step 5: Finally, delete 'temp' (free(temp)).

Display () - Displaying stack of elements

steps to display the elements (nodes) of a stack...
 Step 1: Check whether stack is Empty (top == NULL).
 Step 2: If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
 Step 3: If it is Not Empty, then define a Node pointer 'temp' and initialize with top. 5
 Step 4: Display 'temp → data --->' and move it to the next node. Repeat the same until
temp reaches to the first node in the stack (temp → next != NULL).
 Step 5: Finally! Display 'temp → data ---> NULL'.

// C code to implement stack using Linked Lists

void push (int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if (top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
If (top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
while(temp->next != NULL)
{
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL",temp->data);
}
}

Recursion:
Definition:
Recursion in the data structure can be defined as a method through which problems are
broken down into smaller sub-problems to find a solution.
This is done by replicating the function on a smaller scale, making it call itself and then
combining them together to solve problems.

Designing Recursive Algorithms

Every recursive call must either solve a part of the problem or reduce the size of the
problem.
The rules for designing a recursive algorithm:
1. First, determine the base case.
2. Then determine the general case.
3. Combine the base case and the general cases into an algorithm.
In combining the base and the general case into an algorithm, we must pay careful attention
to the logic. Each call must reduce the size of the problem and move it toward the base case.
The base case, when reached, must terminate without a call to the recursive algorithm; that is,
it must execute a return.
Limitations of Recursion
 Recursion works best when the algorithm uses a data structure that naturally supports
recursion. For example, Trees are a naturally recursive structure and recursion works
well with them.
 In other cases the algorithm is naturally suited to recursion. For example, the binary
search algorithm lends itself to a natural recursive algorithm, as does the Towers of
Hanoi algorithm.
 On the other hand, not all looping algorithms can or should be implemented with
recursion.
  Recursive solutions may involve extensive overhead (both time and memory)
because they use calls. Each call takes time to execute.
 A recursive algorithm therefore generally runs more slowly than its non-recursive
implementation.
Examples:
1. Greatest Common Divisor Recursive Definition
// Euclidean Algorithm for Greatest Common Divisor
Algorithm gcd (a, b)
Calculates greatest common divisor using the Euclidean algorithm.
Pre a and b are positive integers greater than 0
Post greatest common divisor returned
 S1 : if (b equals 0)
1
return a
 S2 : end if
 S3 : if (a equals 0)
2
return b
 S4 : end if
 S5 : return gcd (b, a mod b)
end gcd
// C program to determine the greatest common divisor of two numbers.
#include <stdio.h>
#include <ctype.h>
int gcd (int a, int b);
int main (void)
{
int gcdResult;
// Statements
printf("Test GCD Algorithm\n");
gcdResult = gcd (10, 25);
printf("GCD of 10 & 25 is %d", gcdResult);
printf("\nEnd of Test\n");
return 0;
}
int gcd (int a, int b)
{
if (b == 0)
return a;
if (a == 0)
return b;
return gcd (b, a % b);
}

2. Fibonacci Numbers Recursive Definition

Fibonacci Numbers
Fibonacci numbers are named after Leonardo Fibonacci, an Italian mathematician who lived
in the early thirteenth century. In this series each number is the sum of the previous two
numbers.
The first few numbers in the Fibonacci series are
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
// C Program to print Fibonacci series
#include <stdio.h>
long fib (long num);
int main (void)
{
int seriesSize = 10;
printf("Print a Fibonacci series.\n");
for (int looper = 0; looper < seriesSize; looper++)
{
if (looper % 5)
printf(", %8ld", fib(looper));
else
printf("\n%8ld", fib(looper));
}
printf("\n");
return 0;
}

long fib (long num)

{
if (num == 0 || num == 1)
return num;
return (fib (num - 1) + fib (num - 2));
}

3. The Towers of Hanoi Recursive Definition

The Towers of Hanoi is a classic recursion problem that is relatively easy to follow, is
efficient, and uses no complex data structures.
1. Only one disk could be moved at a time. A larger disk must never be stacked above a
smaller one.
2. One and only one auxiliary needle could be used for the intermediate storage of disks.

Towers of Hanoi Algorithm

towers (numDisks, source, dest, auxiliary)
Recursively move disks from source to destination. Pre numDisks is number of disks to be
moved source, destination, and auxiliary towers given Post steps for moves printed.
S1:print("Towers: ", numDisks, source, dest, auxiliary)
S2: if (numDisks is 1)
print ("Move from ", source, " to ", dest)
S3: else
1 towers (numDisks - 1, source, auxiliary, dest, step)
2 print ("Move from " source " to " dest)
3 towers (numDisks - 1, auxiliary, dest, source, step)
S4: end if
end towers.

// C Program to implement Towers of Hanoi

#include<stdio.h>
void towers (int n, char source, char dest, char auxiliary);
int main (void)
{
int numDisks;
printf("Please enter number of disks: ");
scanf ("%d", &numDisks);
printf("Start Towers of Hanoi.\n\n");
towers (numDisks, 'A', 'C', 'B');
printf("\nI Hope you didn't select 64 " "and end the world!\n");
return 0;
}
void towers (int n, char source, char dest, char auxiliary)
{
static int step = 0;
printf("Towers (%d, %c, %c, %c)\n", n, source, dest, auxiliary);
if (n == 1)
printf("\t\t\tStep %3d: Move from %c to %c\n", ++step, source, dest);
else
{
towers (n - 1, source, auxiliary, dest);
printf("\t\t\tStep %3d: Move from %c to %c\n", ++step, source, dest);
towers (n - 1, auxiliary, dest, source);
}
return;
}

Stacks and its Implementations

Stack is a linear data structure that follows LIFO (Last In First Out) Principle, the last
element inserted is the first to be popped out. It means both insertion and deletion
operations happen at one end only.
LIFO(Last In First Out) Principle
Here are some real world examples of LIFO
Consider a stack of plates. When we add a plate, we add at the top. When we remove, we
remove from the top.
A shuttlecock box (or any other box that is closed from one end) is another great real-world
example of the LIFO (Last In, First Out) principle where do insertions and removals from the
same end.
Representation of Stack Data Structure:
Stack follows LIFO (Last In First Out) Principle so the element which is pushed last is
popped first.

Types of Stack:
Fixed Size Stack : As the name suggests, a fixed size stack has a fixed size and cannot grow
or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an
overflow error occurs. If the stack is empty and an attempt is made to remove an element
from it, an underflow error occurs.
Dynamic Size Stack : A dynamic size stack can grow or shrink dynamically. When the stack
is full, it automatically increases its size to accommodate the new element, and when the
stack is empty, it decreases its size. This type of stack is implemented using a linked list, as it
allows for easy resizing of the stack.

Basic Operations on Stack:

push() to insert an element into the stack
pop() to remove an element from the stack
top() Returns the top element of the stack.
isEmpty() returns true if stack is empty else false.
isFull() returns true if the stack is full else false.

Implementation of Stack
There are two ways to implement a stack –
Implementation of Stack using Array (Refer page No. 7)
Implementation of Stack using Linked List (Refer page No. 7)

Applications of Stacks:
Function calls: Stacks are used to keep track of the return addresses of function calls,
allowing the program to return to the correct location after a function has finished executing.
Recursion: Stacks are used to store the local variables and return addresses of recursive
function calls, allowing the program to keep track of the current state of the recursion.
Expression evaluation: Stacks are used to evaluate expressions in postfix notation (Reverse
Polish Notation).
Syntax parsing: Stacks are used to check the validity of syntax in programming languages
and other formal languages.
Memory management: Stacks are used to allocate and manage memory in some operating
systems and programming languages.

Advantages of Stacks:
Simplicity: Stacks are a simple and easy-to-understand data structure, making them suitable
for a wide range of applications.
Efficiency: Push and pop operations on a stack can be performed in constant time (O(1)),
providing efficient access to data.
Last-in, First-out (LIFO): Stacks follow the LIFO principle, ensuring that the last element
added to the stack is the first one removed. This behavior is useful in many scenarios, such as
function calls and expression evaluation.
Limited memory usage: Stacks only need to store the elements that have been pushed onto
them, making them memory-efficient compared to other data structures.
Disadvantages of Stacks:
Limited access: Elements in a stack can only be accessed from the top, making it difficult to
retrieve or modify elements in the middle of the stack.
Potential for overflow: If more elements are pushed onto a stack than it can hold, an
overflow error will occur, resulting in a loss of data.
Not suitable for random access: Stacks do not allow for random access to elements, making
them unsuitable for applications where elements need to be accessed in a specific order.
Limited capacity: Stacks have a fixed capacity, which can be a limitation if the number of
elements that need to be stored is unknown or highly variable.

Expression Evaluation:
Infix Expressions
Infix expressions are mathematical expressions where the operator is placed between its
operands. This is the most common mathematical notation used by humans. For example, the
expression "2 + 3" is an infix expression, where the operator "+" is placed between the
operands "2" and "3".
Infix notation is easy to read and understand for humans, but it can be difficult for computers
to evaluate efficiently. This is because the order of operations must be taken into account, and
parentheses can be used to override the default order of operations.

Common way of writing Infix expressions:

Infix notation is the notation that we are most familiar with. For example, the expression "2 +
3" is written in infix notation.
In infix notation, operators are placed between the operands they operate on. For example, in
the expression "2 + 3", the addition operator "+" is placed between the operands "2" and "3".
Parentheses are used in infix notation to specify the order in which operations should be
performed. For example, in the expression "(2 + 3) * 4", the parentheses indicate that the
addition operation should be performed before the multiplication operation.

Operator precedence rules:

Infix expressions follow operator precedence rules, which determine the order in which
operators are evaluated. For example, multiplication and division have higher precedence
than addition and subtraction. This means that in the expression "2 + 3 * 4", the
multiplication operation will be performed before the addition operation.
Here's the table summarizing the operator precedence rules for common mathematical
operators:

Operator Precedence
Parentheses () Highest
Exponents ^ High
Multiplication * Medium
Division / Medium
Addition + Low
Subtraction - Low

Evaluating Infix Expressions

Evaluating infix expressions requires additional processing to handle the order of operations
and parentheses. First convert the infix expression to postfix notation. This can be done using
a stack or a recursive algorithm. Then evaluate the postfix expression.
Advantages of Infix Expressions
 More natural and easier to read and understand for humans.
 Widely used and supported by most programming languages and calculators.
Disadvantages Infix Expressions
 Requires parentheses to specify the order of operations.
 Can be difficult to parse and evaluate efficiently.

Prefix Expressions (Polish Notation)

Prefix expressions are also known as Polish notation, are a mathematical notation where the
operator precedes its operands. This differs from the more common infix notation, where the
operator is placed between its operands.
In prefix notation, the operator is written first, followed by its operands. For example, the
infix expression "a + b" would be written as "+ a b" in prefix notation.
Advantages of Prefix Expressions
 No need for parentheses, as the operator always precedes its operands.
 Easier to parse and evaluate using a stack-based algorithm.
 Can be more efficient in certain situations, such as when dealing with expressions that
have a large number of nested parentheses.
Disadvantages of Prefix Expressions
 Can be difficult to read and understand for humans.
 Not as commonly used as infix notation.

Postfix Expressions (Reverse Polish Notation)

Postfix expressions are also known as Reverse Polish Notation (RPN), are a mathematical
notation where the operator follows its operands. This differs from the more common infix
notation, where the operator is placed between its operands.
In postfix notation, operands are written first, followed by the operator. For example, the
infix expression "5 + 2" would be written as "5 2 +" in postfix notation.
Advantages of Postfix Notation
 Also eliminates the need for parentheses.
 Easier to read and understand for humans.
 More commonly used than prefix notation.
Disadvantages of Postfix Expressions
 Requires a stack-based algorithm for evaluation.
 Can be less efficient than prefix notation in certain situations.

Expression Evaluation:
Algorithms
Problems