Data Structure

Data : Collection of information

Organized collection of data in particular format
It is a technique or method of study how the data are interrelated to each
other logically or mathematically
Def: A data structure is a specialized format for organizing, processing and
storing data. It provides a means to manage large amounts of data efficiently
for uses such as large databases and internet indexing services.

Example : Linked List

Address Data Link
1 A 2
2 M NULL
3 S 6
(STARTS)
4
5 H 1
6 O 5

What is data structure

A data structure is a way of organizing, storing and managing data in a
computer so that it can be used efficiently.
What is the purpose of DS
The main aim of data structure is to increase the efficiency of program and
decrease the storage requirement
Why data structures are important
They make programs faster
They use memory efficiently
They help in easy data searching, insertion, deletion and updating
They are the foundation of algorithms
Classification of DS
1. Linear data -- Array , Linked List, Stack, Queue
Non linear -- Graph , Tree
2. Homogenous -- Array
Non homogenous – Structure, Union
 3. Static -- Size of memory , char [10]
Dynamic -- *a adjust memory allocation at run time
Operations of DS
Searching – To find element
Traversing – To individual data process
Insert – To add
Delete – To remove
Update – To edit
Merging – To join
Sorting – To sort in particular order
What is algorithm
The step by step description of program in general language is called
algorithm .
Algorithm is a sequence of a clear instructions used to solve a program such a
way that it can
implement as a program for computer.

Unit 1 : Data Structure and Algorithm Basics

Introduction: Elementary data organizations and operations on it. Abstract data
types (ADT) and their characteristics.
Algorithms: Characteristics, Asymptotic notations, time and space trade-offs,
Analysis of algorithm.
Array ADT: Representations – row-major and column-major form, Dynamic Arrays,
Implementation of Real-life problems using arrays.
Elementary Data Organizations and operations on it
1. Elementary Data Organizations
It is the basic ways of organizing data in computer memory before learning
complex data structures.
It is the foundation of data structures, dealing with simple data items and their
storage.
Data Structure Description Example

Integers, Characters Single primitive values age = 20, grade = 'A

Arrays Multiple values of same marks[5] = {85, 90, 78,
type in contiguous 92, 88}
memory

Strings Sequence of characters "Hello World"

Pointers Store the address of *p=var

another variable
Used for efficient
memory management

Records / Structures Collection of Student {name, id, gpa}

heterogeneous data
types

Lists Ordered collection with Shopping cart items

dynamic size

2. Operations on Elementary Data Organization

These are basic operations performed on data.
1. Traversal
Accessing each element one by one.
Example: Reading all elements of an array.
2. Insertion
Adding a new element to the data.
Example: Inserting a new mark in an array.
3. Deletion
Removing an element from the data.
Example: Deleting a record.
4. Searching
Finding the location of a particular element.
Example: Searching a roll number.
5. Updating (Modification)
Changing an existing data value.
Example: Updating marks of a student.
6. Sorting
Arranging data in ascending or descending order.
7. Merging
Combining two data sets into one.
Abstract Data Type (ADT) and their characteristics
1. Abstract Data Type (ADT)
Abstract Data Type is a data type that defines the data and the operations on
it, but hides the implementation details.
An Abstract Data Type (ADT) is a way of describing what data we store and
what operations we can perform on it, without telling how it is
implemented.
Def : An Abstract Data Type (ADT) is a conceptual model in computer science
that defines what operations can be performed on a data type, but not how
they are implemented. It focuses on behaviour rather than representation,
making it implementation-independent.
Example:
Think of a TV remote
You know what buttons do (change channel, volume up/down)
You don’t know how the remote works internally

Examples of ADT
Linear ADTs
● Array

● Stack (push, pop)

● Queue (enqueue, dequeue)
● List

● Set

Non Linear ADTs

● Tree
● Graph

2. Characteristics of ADT
 1. Abstraction
Only important details are shown.
Implementation details are hidden.
2. Encapsulation
Data and operations are combined together.
Data cannot be accessed directly.
3. Implementation Independent
Same ADT can be implemented using different methods.
Example: Stack using array or linked list.
4. Well-Defined Operations
Operations are clearly defined.
Example: Stack → push(), pop(), peek().
5. Reusability
ADTs can be reused in many programs.
Makes coding easier and faster.
6. Security
Data is protected because direct access is not allowed.
Core Operations of ADT
1. Create
o Creates a new instance of the ADT.
o Example: Creating an empty stack or list.
2. Insert
o Adds a new element to the ADT.
o Example: Pushing an element into a stack.
3. Delete
o Removes an element from the ADT.
o Example: Popping an element from a stack.
4. Search
o Finds a specific element in the ADT.
o Example: Searching a key in a list.
5. Access / Retrieve
 o Gets an element without modifying it.
o Example: Peek operation in a stack.
6. Update / Modify
o Changes the value of an existing element.
o Example: Updating a record in a list.
7. Traverse
o Visits all elements one by one.
o Example: Displaying all elements of a queue.
8. Check Status
o Checks conditions like empty or full.
o Example: isEmpty(), isFull().
Algorithms
An algorithm is a well-defined, finite sequence of instructions designed to solve a
specific problem or perform a computation. Think of it as a recipe that transforms
input into output through a series of clear steps.
Characteristics of an Algorithm
1. Input
o An algorithm must take zero or more inputs.
o Example: Number n for factorial.
2. Output
o An algorithm must produce at least one output.
o Example: Factorial value.
3. Definiteness
o Each step must be clear, precise, and unambiguous.
o No confusion in instructions.
4. Finiteness
o The algorithm must end after a finite number of steps.
o It should not run forever.
5. Effectiveness
o Each step must be simple and executable.
o Steps should be basic and practical.
 6. Correctness
o The algorithm should give the correct result for all valid inputs.
7. Generality
o It should work for all possible valid inputs, not just one case.

Property of Algorithm
Input
Output
Definiteness : clear instruction
Effectiveness : feasible
Finiteness : set of instructions
Example : Write a algorithm for addition of two number

Algorithm in Standard Format

Algorithm: Add_Two_Numbers
Input: Two numbers A, B
Output: Sum of A and B
1. Start
2. Input a, b
3. sum ← a + b
4. Print SUM
5. Stop

Algorithm: Factorial of a Number

Algorithm: Factorial
Input: Integer n
Output: Factorial of n
1. Start
2. Read number n
3. Set fact ← 1
4. Repeat steps from i = 1 to n
fact ← fact * i
5. Display fact
6. Stop

1. Analysis of Algorithm
Analysis of an algorithm means studying how much time and memory (space) an
algorithm requires as the input size grows.
It helps to:
● Compare different algorithms
● Choose the most efficient one
● Predict performance before implementation
Types:
● Time Complexity – time taken by an algorithm
● Space Complexity – memory used by an algorithm

2. Asymptotic Notations
Asymptotic notations describe the performance of an algorithm for large input sizes
(n).
Why Asymptotic Notations are Needed
● To measure performance of algorithms
● To compare algorithms for large inputs
(a) Big-O Notation – O(n)
● Describes the worst-case time
● Upper bound of an algorithm
Example:
Linear search → O(n)
(b) Omega Notation – Ω(n)
 ● Describes the best-case time
● Lower bound of an algorithm
Example:
Best case of linear search → Ω(1)
(c) Theta Notation – Θ(n)
● Describes the average/exact case
● Tight bound
Example:
Binary search → Θ(log n)
3. Time and Space Trade-Off
A time–space trade-off means improving time at the cost of more space or saving
space at the cost of more time.
Example:
● Using hash tables:
o Faster search (less time)
o Requires extra memory (more space)
● Using linear search:
o Less memory
o More time

Analysis of algorithm → measures efficiency

Asymptotic notations → Big-O, Ω, Θ
Time-space trade-off → balance between speed and memory
----------------------------------------------------------------------------------------------------------------
ADTs
An Abstract Data Type (ADT) is a way of describing what data we store and what
operations we can perform on it, without telling how it is implemented.
Linear ADTs
● Array

● Stack (push, pop)

● List

● Queue (enqueue, dequeue)

 ● Set

Non Linear ADTs

● Tree
● Graph

List ADT
The List ADT (Abstract Data Type) is a sequential collection of elements
It provides an ordered way to store, access, and modify data.
A List ADT is an abstract data type that represents a collection of elements
arranged in a linear order.

Lists are linear data structures stored in a non-continuous manner. The list is made
up of a series of connected nodes that are randomly stored in the memory. Here,
each node consists of two parts, the first part is the data and the second part
contains the pointer to the address of the next node.

Each element has:

● A position (index)
● A successor (except the last element)
 ● A predecessor (except the first element)
The List ADT defines what operations can be performed, but not how they are
implemented.

Characteristics of List ADT

● Elements are stored in sequence
● Allows duplicate elements
● Elements can be of same or different data types (depending on
implementation)
● Supports dynamic size
● Access can be sequential or random

Common Operations of List ADT

Operation Description
create() Creates an empty list
isEmpty() Checks whether the list is empty
size() Returns the number of elements
insert(position, element) Inserts an element at a given position
delete(position) Deletes an element from a given position
retrieve(position) Returns the element at a given position
replace(position, element) Replaces element at given position
search(element) Finds the position of an element
clear() Removes all elements
display() Displays list elements
Program on list
#include <stdio.h>
#define MAX 100
int list[MAX];
int count = 0;
/* Create an empty list */
void create() {
count = 0;
printf("List created successfully.\n");
}
/* Check if list is empty */
int isEmpty() {
if (count == 0)
return 1;
else
return 0;
}
/* Return size of list */
int size() {
return count;
}
/* Insert element at given position */
void insert(int position, int element) {
int i;
if (count == MAX) {
printf("List is full.\n");
return;
}
if (position < 1 || position > count + 1) {
printf("Invalid position.\n");
 return;
}
for (i = count; i >= position; i--) {
list[i] = list[i - 1];
}
list[position - 1] = element;
count++;
printf("Element inserted.\n");
}
/* Delete element from given position */
void delete(int position) {
int i;

if (isEmpty()) {
printf("List is empty.\n");
return;
}
if (position < 1 || position > count) {
printf("Invalid position.\n");
return;
}
for (i = position - 1; i < count - 1; i++) {
list[i] = list[i + 1];
}
count--;
printf("Element deleted.\n");
}
/* Retrieve element at given position */
void retrieve(int position) {
if (position < 1 || position > count) {
printf("Invalid position.\n");
 return;
}
printf("Element at position %d is %d\n", position, list[position - 1]);
}

/* Replace element at given position */

void replace(int position, int element) {
if (position < 1 || position > count) {
printf("Invalid position.\n");
return;
}
list[position - 1] = element;
printf("Element replaced.\n");
}
/* Search element in list */
void search(int element) {
int i;
for (i = 0; i < count; i++) {
if (list[i] == element) {
printf("Element found at position %d\n", i + 1);
return;
}
}
printf("Element not found.\n");
}
/* Clear the list */
void clear() {
count = 0;
printf("List cleared.\n");
}
/* Display list elements */
void display() {
int i;
if (isEmpty()) {
printf("List is empty.\n");
return;
}
printf("List elements: ");
for (i = 0; i < count; i++) {
printf("%d ", list[i]);
}
printf("\n");
}
/* Main function */
int main() {
create();
insert(1, 10);
insert(2, 20);
insert(3, 30);
display();
retrieve(2);
replace(2, 25);
display();
search(30);
delete(1);
display();
printf("Size of list: %d\n", size());
clear();
display();
return 0;
}
Key Difference Between array and Array ADT
A simple array is a physical data structure used to store elements, whereas an Array
ADT is an abstract concept that defines the operations that can be performed on an
array.
When to Use
● Use simple array → when data size is fixed and operations are minimal
● Use Array ADT → when structured operations and scalability are required
Simple Array : Only stores and accesses data
int a[5] = {10, 20, 30, 40, 50};
printf("%d", a[2]);
Simple Array Program in C
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};
int i;
printf("Array elements are:\n");
for (i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Insert 6th Element in Array of Size 10

#include <stdio.h>
int main() {
int arr[10] = {10, 20, 30, 40, 50}; // 5 elements already stored
int n = 5; // current number of elements
 int newElement;
printf("Enter the 6th element: ");
scanf("%d", &newElement);
arr[n] = newElement; // insert at 6th position
n++; // increase element count
printf("Array elements are:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
C Program: Insert Element at Position 70 in Array of Size 100
#include <stdio.h>
int main() {
int arr[100] = {10, 20, 30, 40, 50}; // existing elements
int n = 5; // current number of elements
int pos = 70; // position to insert
int value;
int i;

if (pos < 1 || pos > 100) {

printf("Invalid position.\n");
return 0;
}

printf("Enter value to insert at position %d: ", pos);

scanf("%d", &value);

/* Shift elements to the right */

for (i = n; i >= pos - 1; i--) {
arr[i + 1] = arr[i];
 }
arr[pos - 1] = value; // insert value
n++;
printf("Array elements after insertion:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Delete an Element from Array

#include <stdio.h>
int main() {
int arr[20] = {10, 20, 30, 40, 50};
int n = 5; // current number of elements
int pos, i;
printf("Enter position to delete (1 to %d): ", n);
scanf("%d", &pos);
if (pos < 1 || pos > n) {
printf("Invalid position.\n");
return 0;
}
/* Shift elements to the left */
for (i = pos - 1; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--; // decrease number of elements
printf("Array after deletion:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
 return 0;
}

Array ADT (Abstract Data Type)

An Array ADT is a collection of similar data elements stored in contiguous memory
locations, where each element is accessed using an index.
Characteristics of Array ADT
● Stores homogeneous elements (same data type)
● Elements are stored in continuous memory
● Each element is accessed using an index
● Supports random (direct) access
● Size can be fixed or dynamic (conceptually)
● Indexing usually starts from 0
Basic Operations:
Operation Description
create() Creates an empty array
traverse() Accesses each element
insert(index, element) Inserts element at given index
delete(index) Removes element from given index
search(element) Finds an element
update(index, element) Modifies an element
sort() Arranges elements
merge() Combines two arrays
size() Returns number of elements
Array Representation in Memory OR Types of Array ADT
One-Dimensional Array
Linear arrangement
Index: 0 1 2 3
Data: 10 20 30 40
Two-Dimensional Array
 Table or matrix form
10 20
30 40
Multi-Dimensional Array : Array with more than two dimensions
(a) Row-Major Order
● Elements of a row are stored continuously in memory.
● Used in languages like C, C++.
Address Formula
Why address is needed, Arrays store elements in contiguous memory locations.
So, to reach A[i], the system moves:
i × size bytes forward from the base address

Calculate the memory address (location) of an element in a one-dimensional array.

LOC(A[3]) = 1000 + 3 × 4
= 1000 + 12
A[3] = 1012 LOC(A[i]) = Base + i × size
Index 0 1 2 3 Size (in bytes) of one a

Address 1000 1004 1008 1012 Index of the required elem

Address of the first element of the

Value A[0] A[1] A[2] A[3]
Memory address of the i-th element of array A

LOC - LOC stands for Location. “where in memory” a

Calculate the memory address (location) of an element in a 2D-dimensional array.

1 2 3
4 5 6
Stored as: 1 2 3 4 5 6

(b) Column-Major Order

● Elements of a column are stored continuously.
● Used in languages like FORTRAN, MATLAB.
Address Formula (2D Array):

● 2-D array A[3][4] (3 rows, 4 columns)

● Data type = int
● Size of int = 4 bytes
● Base address = 1000
● Find LOC(A[1][2])

1 2 3
4 5 6
Stored as: 1 4 2 5 3 6
3. Dynamic Arrays
A dynamic array is an array whose size can change at runtime.
Features:
● Allocated in heap memory
● Size can grow or shrink
● Requires reallocation when full

Why Do We Need Dynamic Arrays?

Static arrays:
● Waste memory if size is larger than needed
● Cannot grow or shrink
Dynamic arrays:
 ● Allocate memory when required
● Use memory efficiently
● Can resize as elements are added or removed
3. Characteristics of Dynamic Array
● Size decided at runtime
● Memory allocated from the heap
● Supports random access like static arrays
● Requires manual memory management
● Uses pointers

How Dynamic Arrays Work

1. Allocate memory using:
malloc() : allocates a single block of memory of the specified size at
runtime.
Does not initialize memory(garbage value)
Faster than calloc
Returns Null if allocation fails
It gives one continuous block of that size
ptr = (datatype*) malloc(size_in_bytes);
int *arr;
arr = (int*) malloc(5 * sizeof(int));
allocates memory for 5 integer values in the heap at runtime.

calloc() : contiguous allocation) allocates multiple blocks of memory and

initializes all bytes to zero.
Slower than malloc
Returns Null if allocation fails
Reserved multiple memory location p[laced next to each other
We provide no. of elements and size of each
ptr = (datatype*) calloc(number_of_elements, size_of_each);
int *arr;
 arr = (int*) calloc(5, sizeof(int));
allocates memory for 5 integer values in the heap and initializes all
of them to zero
2. Access elements using indexing
3. Resize memory using:
realloc()
4. Release memory using: free()

realloc() is a dynamic memory allocation function in C used to resize previously

allocated memory.

It is declared in: #include <stdlib.h>

Syntax : ptr = (type*) realloc(ptr, new_size);

ptr → pointer previously allocated using malloc() or calloc()

new_size → new memory size in bytes
Returns → pointer to resized memory block

Why realloc() is Used in Data Structures?

In data structures like:

Dynamic Arrays
Array-based Stack
Array-based Queue

Sometimes the size needs to increase or decrease during runtime.

realloc() helps to:

Expand array size when it becomes full

Shrink memory when not needed
Avoid memory wastage

How It Works
1. If enough space is available → memory is extended at same location.

2. If not → new memory block is created.

3. Old data is copied.

 4. Old memory is freed automatically

Dynamic Array Resize

#include <stdio.h>
#include <stdlib.h>

int main() {
int *arr;
int n = 3;

arr = (int*) malloc(n * sizeof(int));

for(int i = 0; i < n; i++) {

arr[i] = i + 1;
}

// Increase size to 6
n = 6;
arr = (int*) realloc(arr, n * sizeof(int));

for(int i = 3; i < n; i++) {

arr[i] = i + 1;
}

for(int i = 0; i < n; i++) {

printf("%d ", arr[i]);
}

free(arr);
return 0;
}

Feature malloc() calloc() realloc()

Full Form Memory Contiguous Allocation Re-allocation

Allocation

Header File <stdlib.h> <stdlib.h> <stdlib.h>

Arguments 1 argument 2 arguments 2 arguments

Purpose Allocates memory Allocates memory for Resizes previously
block multiple elements allocated memory

Memory No (contains Yes (initializes to 0) Keeps old data

Initialization garbage values) (new part
uninitialized)

Syntax ptr = ptr = calloc(n, size); ptr = realloc(ptr,

malloc(size); new_size);

Speed Faster Slightly slower (due to Depends on

zero initialization) resizing

Best Use When initial When zero initialization When

values are not is needed increasing/decreasi
required ng size dynamically

Example:
#include <stdio.h>
#include <stdlib.h>

int main() {
int *a, *b, i;

// malloc - allocate 3 integers

a = (int*) malloc(3 * sizeof(int));

// calloc - allocate 3 integers (initialized to 0)

b = (int*) calloc(3, sizeof(int));

printf("Values from malloc (before initialization):\n");

for (i = 0; i < 3; i++)
printf("%d ", a[i]); // Garbage values

printf("\n\nValues from calloc:\n");

for (i = 0; i < 3; i++)
printf("%d ", b[i]); // 0 0 0

// Initialize malloc array

for (i = 0; i < 3; i++)
a[i] = i + 1;

// Realloc - increase size of malloc array from 3 to 5

a = (int*) realloc(a, 5 * sizeof(int));
 // Initialize new elements
for (i = 3; i < 5; i++)
a[i] = i + 1;

printf("\n\nValues after realloc (size increased to 5):\n");

for (i = 0; i < 5; i++)
printf("%d ", a[i]);

free(a);
free(b);

return 0;
}

Write a C program to dynamically allocate memory for n integers using malloc().

Read the elements from the user, display them on the screen and free the
allocated memory.
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, i;
int *ptr;
printf("Enter number of elements: ");
scanf("%d", &n);
// Memory allocation using malloc
ptr = (int*) malloc(n * sizeof(int));
// Check allocation
if (ptr == NULL) {
printf("Memory allocation failed");
return 0;
}
// Input values
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &ptr[i]);
}
// Display values
printf("Elements are:\n");
 for (i = 0; i < n; i++) {
printf("%d ", ptr[i]);
}
// Free memory
free(ptr);
return 0;
}
Enter number of elements: 5
Enter 5 elements:
10 20 30 40 50
Elements are:
10 20 30 40 50

Write a C program to dynamically allocate memory for n integers using calloc().

Display the default values stored in the allocated memory and free the memory
after use.
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, i;
int *ptr;
printf("Enter number of elements: ");
scanf("%d", &n);
// Memory allocation using calloc
ptr = (int*) calloc(n, sizeof(int));
// Check allocation
if (ptr == NULL) {
printf("Memory allocation failed");
return 0;
}
// Display default values
printf("Default values after calloc:\n");
 for (i = 0; i < n; i++) {
printf("%d ", ptr[i]); // all zeros
}
// Free memory
free(ptr);
return 0;
}
Enter number of elements: 5
Default values after calloc:
00000

#include <stdio.h> Header Files

#include <stdlib.h>
int main() {
int n, i;
int *arr;
printf("Enter number of elements: ");
scanf("%d", &n);
arr = (int*) malloc(n * sizeof(int));
if (arr == NULL) {
 If memory is not available, malloc() returns NULL
This prevents program crash

If
re
Th

Valu
mem
arr[i]

4. Implementation of Real-Life Problems Using Arrays

(a) Student Marks System
● Store marks of students
● Calculate average, highest, lowest marks
(b) Employee Salary Management
● Store salaries
● Compute total payroll
(c) Inventory Management
 ● Store quantity of items
● Update stock levels
(d) Image Processing
● 2D arrays store pixel values
(e) Daily Temperature Record
● Store temperatures of each day
● Analyze trends

5. Advantages of Arrays
● Fast access using index
● Easy to implement
● Efficient memory usage for fixed-size data

6. Limitations of Arrays
● Fixed size (static arrays)
● Insertion and deletion are costly
● Memory wastage possible
1. Array ADT – Basic Example (1D Array)
#include <stdio.h>
int main() {
int marks[5] = {78, 85, 90, 66, 72};
int i;
printf("Student Marks:\n");
for(i = 0; i < 5; i++) {
printf("%d ", marks[i]);
}
return 0;
}
2. Row-Major Order Representation (2D Array)
#include <stdio.h>
int main() {
int a[2][3] = {{1,2,3},{4,5,6}};
int i, j;
printf("Row-major order:\n");
for(i = 0; i < 2; i++) {
for(j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
return 0;
}
3. Column-Major Order
C does not support column-major storage directly, but we can access elements
column-wise.
#include <stdio.h>

int main() {
int a[2][3] = {{1,2,3},{4,5,6}};
int i, j;

printf("Column-major order:\n");
for(j = 0; j < 3; j++) {
for(i = 0; i < 2; i++) {
printf("%d ", a[i][j]);
}
}
return 0;
}
Dynamic Array Example
#include <stdio.h>
#include <stdlib.h>
int main() {
int *arr, n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
arr = (int*)malloc(n * sizeof(int));
printf("Enter elements:\n");
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Array elements are:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
free(arr);
return 0;
}
Real-Life Problem Implementation Using Array
Example: Calculate average temperature of a week
#include <stdio.h>
int main() {
float temp[7], sum = 0;
int i;
printf("Enter temperatures for 7 days:\n");
for(i = 0; i < 7; i++) {
scanf("%f", &temp[i]);
sum += temp[i];
}
printf("Average temperature = %.2f", sum / 7);
return 0;
}
Real-Life Example: Employee Salary System
#include <stdio.h>
int main() {
int salary[5], i;
int total = 0;
printf("Enter salaries of 5 employees:\n");
for(i = 0; i < 5; i++) {
scanf("%d", &salary[i]);
total += salary[i];
}
printf("Total salary = %d", total);
return 0;
}

Unit 2:
Stack Data Structure or Stack ADT
A stack is an ordered list or we can say a container in which insertion and deletion
can be done from the one end known as the top of the stack. The last inserted
element is available first and is the first one to be deleted. Hence, it is known as Last
In, First Out LIFO, or First In, Last Out FILO
A stack is called an abstract data type (ADT) because it defines a set of operations
(such as push and pop) and properties (such as Last-In-First-Out behaviour) without
specifying the implementation details.
A Stack is a linear data structure that follows a particular order in which the
operations are performed. The order may be LIFO(Last In First Out) or FILO(First In
Last Out). LIFO implies that the element that is inserted last, comes out first
and FILO implies that the element that is inserted first, comes out last.
It behaves like a stack of plates, where the last plate added is the first one to be
removed.
Pushing an element onto the stack is like adding a new plate on top
Popping an element removes the top plate from the stack.
LIFO(Last In First Out) Principle
The LIFO principle means that the last element added to a stack is the first one to be
removed.
● New elements are always pushed on top.
● Removal (pop) also happens only from the top.
● This ensures a strict order: last in → first out.
Basic Terminologies of Stack

● top(): returns the value of the node present at the top of the stack.
● push(int val): creates a node with value = val and puts it at the stack top.
● pop(): removes the node from the top of the stack.
● empty(): returns true if the stack is empty else false.
● size(): returns the number of nodes present in the stack

Stack using Array

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It
can be implemented using an array by treating the end of the array as the top of the
stack.

A stack can be implemented using an array where we maintain:

● An integer array to store elements.
● A variable capacity to represent the maximum size of the stack.
● A variable top to track the index of the top element. Initially, top = -1 to
indicate an empty stack.
Recursion, Conversion of infix to post fix expression, Conversion of infix to polish
notation to object code.

Operations On Stack
The time complexity of all the given operations is constant, i.e. O(1).
Insertion: Push Operation:
Adds an item to the stack. If the stack is full, then it is said to be an
Overflow condition.
● Top in stack is a pointer variable
● Before pushing the element to the stack, we check if the stack is full.
● If the stack is full (top == capacity-1) , then Stack Overflows and we cannot
insert the element to the stack.
● Otherwise, we increment the value of top by 1 (top = top + 1) and the new
value is inserted at top position .
● The elements can be pushed into the stack till we reach the capacity of the
stack.
Algorithm: PUSH Operation (Stack using Array)
Step 1: Start
Step 2: Check if top == MAX – 1
If true, print “Stack Overflow” and go to Step 6
Step 3: Increment top by 1
Step 4: Insert the element at stack[top]
Step 5: Print “Element pushed successfully”
Step 6: Stop

Stack Program (PUSH Operation)

#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
int main() {
push(10);
push(20);
push(30);
push(40);
push(50);
push(60); // causes overflow

return 0;
}
void push(int value) {
if (top == MAX - 1) {
 printf("Stack Overflow\n");
} else {
top++;
stack[top] = value;
printf("%d pushed into stack\n", value);
}
}
Output
10 pushed into stack
20 pushed into stack
30 pushed into stack
40 pushed into stack
50 pushed into stack
Stack Overflow

Deletion: POP()

Algorithm: POP Operation (Stack using Array)

Step 1: Start
Step 2: Check if top == -1
If true, print “Stack Underflow” and go to Step 6
Step 3: Store the value at stack[top] in a variable item
Step 4: Decrement top by 1
Step 5: Print “item popped successfully”
Step 6: Stop

Stack Using Array (Only POP)

#include <stdio.h>
#define MAX 3
int stack[MAX] = {10, 20, 30}; // predefined elements
int top = 2; // index of last element

void pop() {
if (top == -1) {
printf("Stack Underflow\n");
} else {
printf("%d popped from stack\n", stack[top]);
top--;
}
}
int main() {
pop();
pop();
pop();
pop(); // Underflow condition

return 0;
}
30 popped from stack
20 popped from stack
10 popped from stack
Stack Underflow

Simple stack program using array in C both push and pop operation
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
/* Push operation */
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
top++;
stack[top] = value;
printf("%d pushed into stack\n", value);
}
}

/* Pop operation */
void pop() {
if (top == -1) {
 printf("Stack Underflow\n");
} else {
printf("%d popped from stack\n", stack[top]);
top--;
}
}

/* Display stack elements */

void display() {
if (top == -1) {
printf("Stack is empty\n");
} else {
printf("Stack elements are:\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
}
}

int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}
10 pushed into stack
20 pushed into stack
30 pushed into stack
Stack elements are:
30
20
10
30 popped from stack
Stack elements are:
20
10

push and pop operation using stack by ADT

What is Stack ADT?
A Stack ADT defines what operations can be performed on a stack, not how they are
implemented
Why we use ADT?
ADT hides implementation details
User only knows how to use stack, not how it works internally

Difference between simple stack and ADT stack

Feature Simple Stack Stack ADT
Direct implementation of Abstract definition of stack
Definition
stack operations
How stack is
Focus What operations are allowed
implemented
Data often accessed
Data Access Data accessed only through functions
directly
Abstraction No abstraction Provides abstraction
Modularity Low High
Reusability Limited High
Implementation Usually array-based Can be array or linked list
Security Less secure More secure
Flexibility Less flexible Highly flexible
Example stack[top] = x; push(&s, x);

Basic Stack ADT Operations

● push() – insert element
● pop() – delete element
● isEmpty()
● isFull()
● peek()
● size()

size() function for stack

It returns the number of elements present in the stack.

#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
/* size function */
int size() {
return top + 1;
}

int main() {
printf("Size of stack: %d\n", size());
 return 0;
}

peek()

peek() returns the top element of the stack without removing it.

The peek() operation returns the value of the topmost element of the stack without
modifying the stack. This can be useful when you need to check the value of the top
element before deciding whether to remove it or not.

Algorithm for peek() operation on the stack

begin
return stack[top]
end procedure

#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;

/* push function */
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = value;
}
}

/* peek function */
void peek() {
if (top == -1) {
printf("Stack is empty\n");
} else {
 printf("Top element is: %d\n", stack[top]);
}
}
int main() {
push(10);
push(20);
push(30);
peek(); // shows top element

return 0;
}

isFull()
It checks whether the stack is full or not.

The isFull() operation is used to determine if the stack is full or not. A stack is said to
be full if it has reached its maximum capacity and there is no more space to add new
elements to the stack.

Algorithm for isFull() operation on the stack

begin
if stack length is equal to the maximum stack size
return true
endif
else
return false
end else
end procedure

#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

/* isFull function */
int isFull() {
if (top == MAX - 1)
return 1; // stack is full
else
return 0; // stack is not full
}

int main() {
 if (isFull())
printf("Stack is Full\n");
else
printf("Stack is Not Full\n");

return 0;
}

isEmpty()
The isEmpty() operation is used to check if the stack is empty or not. It returns a
boolean value, true when the stack is empty, otherwise false.
Algorithm for isEmpty() operation on the stack
begin
if top < 1
return true
else
return false
end procedure

It checks whether the stack is empty or not.

#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

/* isEmpty function */
int isEmpty() {
if (top == -1)
return 1; // stack is empty // condition satisfied
else
return 0; // stack is not empty
}
int main() {
if (isEmpty())
printf("Stack is Empty\n");
else
printf("Stack is Not Empty\n");
return 0;
}
#include <stdio.h>
#define MAX 5

/* Stack ADT using structure */

typedef struct {
int data[MAX];
int top;
} Stack;

/* initialize stack */
void init(Stack *s) {
s->top = -1;
}
/* push operation */
void push(Stack *s, int value) {
if (s->top == MAX - 1)
printf("Stack Overflow\n");
else
s->data[++s->top] = value;
}
/* pop operation */
int pop(Stack *s) {
if (s->top == -1) {
printf("Stack Underflow\n");
return -1;
}
return s->data[s->top--];
}
int main() {
Stack s;
init(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("Popped element: %d\n", pop(&s));
return 0;
}
Stack ADT user define Structure
#define MAX 5
typedef struct {
int data[MAX];
int top;
} Stack;
PUSH Operation using Stack ADT
Algorithm
1. Check if stack is full (top == MAX - 1)
2. If full → print Stack Overflow
3. Else increment top
4. Insert element at data[top]

Program:
void push(Stack *s, int value) {
if (s->top == MAX - 1) {
printf("Stack Overflow\n");
} else {
s->top++;
s->data[s->top] = value;
printf("%d pushed into stack\n", value);
}
}

POP Operation using Stack ADT

Algorithm
1. Check if stack is empty (top == -1)
2. If empty → print Stack Underflow
3. Else store data[top]
4. Decrement top
5. Return or display popped element

void pop(Stack *s) {

if (s->top == -1) {
printf("Stack Underflow\n");
} else {
printf("%d popped from stack\n", s->data[s->top]);
s->top--;
}
}

Main Function
int main() {
Stack s; (With typedef)
[Link] = -1;

push(&s, 10);
push(&s, 20);
push(&s, 30);
 pop(&s);
pop(&s);

return 0;
}
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 popped from stack
20 popped from stack

Dynamic Stack program using malloc() and calloc()

Why Dynamic Stack?
● Stack size is decided at runtime
● Memory is allocated from heap
● More flexible than static array stack

Stack ADT Structure

typedef struct {
int *data;
int top;
int capacity;
} Stack;

Dynamic Stack using malloc()

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int *data;
int top;
int capacity;
} Stack;

void push(Stack *s, int value) {

if (s->top == s->capacity - 1) {
printf("Stack Overflow\n");
} else {
s->data[++s->top] = value;
printf("%d pushed into stack\n", value);
}
}
void pop(Stack *s) {
if (s->top == -1) {
printf("Stack Underflow\n");
} else {
printf("%d popped from stack\n", s->data[s->top--]);
}
}

int main() {
Stack s;
[Link] = 3;
[Link] = -1;

// Dynamic allocation using malloc

[Link] = (int *)malloc([Link] * sizeof(int));

if ([Link] == NULL) {
printf("Memory allocation failed\n");
return 0;
}

push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40); // overflow

pop(&s);
pop(&s);

free([Link]);
return 0;
}
10 pushed into stack
20 pushed into stack
30 pushed into stack
Stack Overflow
30 popped from stack
20 popped from stack
Dynamic Stack using calloc()

Difference
● calloc() initializes memory to 0
● malloc() gives garbage values
 Allocation line change only:
[Link] = (int *)calloc([Link], sizeof(int));

What is an Expression?

An expression is a combination of operands and operators.

Example:
A + B, 3 * 4

● Infix: The operator is placed between operands. Example: A + B

● Postfix (Reverse Polish Notation): The operator comes after the operands.
Example: A B +
● Prefix (Polish Notation): The operator comes before the operands.
Example: + A B

Types of Expressions
Type Example
Infix A+B
Postfix AB+
Prefix +AB

Stack is mainly used for conversion and evaluation of expressions

Infix to Postfix Conversion

Why conversion is needed?
● Computers cannot directly evaluate infix expressions
● They can easily evaluate postfix / prefix using stack

Rules
1. If operand → add to postfix
2. If ( → push to stack
3. If ) → pop until ( is found
4. Operator precedence:
*/>+-
Precedenc
Operator e

Parentheses () Highest

Exponents ^ High
Multiplication
Medium
*

Division / Medium

Mod % Medium

Addition + Low

Subtraction - Low

Example
Infix : A + B * C
Post fix : A B C * +

Role of Stack
● Stack temporarily stores operators
● Helps manage precedence and parentheses

Infix to Prefix Conversion

Steps:
1. Reverse infix expression
2. Convert to postfix
3. Reverse result → prefix

Given a string s representing an infix expression ("operand1 operator operand2" ),

Convert it into its postfix notation ("operand1 operand2 operator").

Input: s = "a*(b+c)/d"
Output: abc+*d/

Explanation: The expression is a * (b + c) / d.

First, inside the brackets, b + c becomes bc+. Now the expression ,a * (bc+) / d.
Next, multiply a with (bc+), so it becomes abc+* .
Finally, divide this result by d, so it becomes abc+*d/.

Input: s = "a+b*c/d"
Output: abc*+d/
Explanation: The expression a + b * c / d is converted by first doing b * c → bc*, then
adding a → abc*+, and finally adding d → abc*+d/.
Infix to Postfix and Prefix
1. a+b
2. a+b-c
3. a*b-c
4. a*b+c
5. a/b/c
6. a%b
7. a%b+c
8. a%b*c
9. a+b%c
10.a/b%c+d
11.a^b/c^d+e^f
12.a+(b-c)*d/e^f
13.((a-b)*c+d/e)
14.(a+b)*(c-d)
15.(a+b)/(c+d)-(d*e)
16.a-(b/c+(d%e*f)/g)*h
17.3+4*6
18.2+5/4-1*4
19.4-2+5*3/1
20.4-((4/2)*4-(8+1))

Expression Conversion using Stack

Algorithm:
Algorithm: Infix to Postfix Conversion
Step 1
Read the infix expression from the user.

Step 2
Initialize:
● an empty stack for operators
● an empty postfix string

Step 3
Scan the infix expression from left to right, symbol by symbol.

Step 4
For each symbol:
a) If the symbol is an operand
Add it directly to the postfix expression.

b) If the symbol is (
Push it onto the stack.
c) If the symbol is )
Pop operators from the stack and add to postfix
Stop when ( is found
Remove ( from the stack.

d) If the symbol is an operator (+ - * / % ^)

● While the stack is not empty and
o the operator on top of the stack has higher precedence, OR
o the operator on top has equal precedence and the incoming operator
is left-associative
Pop the stack operator and add it to postfix.
● Push the incoming operator onto the stack.

Step 5
After scanning the entire infix expression,
Pop all remaining operators from the stack and add to postfix.

Step 6
The resulting string is the postfix expression.

Operator Rules ( Always Write This Below Algorithm )

● ^ → highest precedence, right-associative
● * / % → left-associative
● + - → left-associative
---------------------------------------------------------------------------------------------------------------
Convert Infix to Postfix using stack ( 1 for 2 Marks)
Algorithm:
Initialize empty stack
Initialize empty postfix string

Scan infix from left to right:

If operand → add to postfix
If '(' → push to stack
If ')' → pop until '('
If operator:
while stack not empty and
precedence(top) ≥ precedence(current)
pop to postfix
push operator

Pop remaining stack to postfix

#include <stdio.h>
#include <string.h>
//stdio.h → for input/output (printf, scanf)
//string.h → for string operations ,mainly '\0' check

#define MAX 50
//Stack and expressions maximum size 50 to set

char stack[MAX];
int top = -1;
//stack[MAX] → array to store operator
//top = -1 → stack empty

/* push operator */
void push(char ch) {
stack[++top] = ch;
}
//top=top+1;stack[top]=ch
//stack[top] = ch → push operator to stack top
// Example:
// if top = -1 then
// ++top = 0
// stack[0] = '+'

/* pop operator */
char pop() {
return stack[top--];
}
//stack[top] → remove top element from stack
// top-- → decrement top
//return popped operator

/* precedence function */
int precedence(char ch)
//to check the Operator priority {
if (ch == '^')
return 3;
if (ch == '*' || ch == '/' || ch == '%')
return 2;
if (ch == '+' || ch == '-')
return 1;
return 0;
}
/* check operand */
int isOperand(char ch)
//Check if operand or not {
if ((ch >= 'A' && ch <= 'Z') ||
(ch >= 'a' && ch <= 'z') ||
(ch >= '0' && ch <= '9'))
return 1;
return 0;
}

int main() {
char infix[MAX], postfix[MAX];
int i, j = 0;
//infix[] → user input expression
//postfix[] → converted expression
//i → infix scan
//j → postfix index

printf("Enter infix expression: ");

scanf("%s", infix);
// to take User input infix expression

for (i = 0; infix[i] != '\0'; i++) {

// to scan Expression from left to right
char ch = infix[i];
//to store the Current character

/* Operand */
if (isOperand(ch)) {
postfix[j++] = ch;
}
//if operand then push into postfix

/* Left parenthesis */
else if (ch == '(') {
push(ch);
}
//( → push in stack

/* Right parenthesis */
else if (ch == ')') {
while (top != -1 && stack[top] != '(')
postfix[j++] = pop();
pop(); // remove '('
 }
// pop operator from stack
//till ( not find
// discard (

/* Operator */
else {
while (top != -1 &&
(precedence(stack[top]) > precedence(ch) ||
(precedence(stack[top]) == precedence(ch) && ch != '^')))
postfix[j++] = pop();
// when perform Pop
//when stack top precedence is greater
//or even same and operator is left associative then
// for ^ equal priority no pop is done

push(ch);
// push the Current operator to stack
}
}

/* pop remaining operators */

while (top != -1)
postfix[j++] = pop();
//pop all Stack operators to postfix

postfix[j] = '\0';
// String end here

printf("Postfix expression: %s\n", postfix);

// Final postfix print

return 0;
//Successful execution
}
-------------------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#define MAX 50
char stack[MAX];
int top = -1;
/* Push into stack */
void push(char ch) {
top = top + 1;
 stack[top] = ch;
}
/* Pop from stack */
char pop() {
char x = stack[top];
top = top - 1;
return x;
}
/* Operator precedence */
int precedence(char ch) {
if (ch == '+' || ch == '-')
return 1;
if (ch == '*' || ch == '/')
return
return 0;
}
/* Check operand */
int isOperand(char ch) {
if ((ch >= 'A' && ch <= 'Z') ||
(ch >= 'a' && ch <= 'z') ||
(ch >= '0' && ch <= '9'))
return 1;
return 0;
}
int main() {
char infix[MAX], postfix[MAX];
int i, j = 0;
printf("Enter infix expression: ");
scanf("%s", infix);
for (i = 0; infix[i] != '\0'; i++) {
char ch = infix[i];
if (isOperand(ch)) {
postfix[j++] = ch;
}
else if (ch == '(') {
push(ch);
}
else if (ch == ')') {
while (top != -1 && stack[top] != '(')
postfix[j++] = pop();
pop(); // remove '('
}
else { // operator
while (top != -1 && precedence(stack[top]) >= precedence(ch))
 postfix[j++] = pop();
push(ch);
}
}

while (top != -1)

postfix[j++] = pop();

postfix[j] = '\0';

printf("Postfix expression: %s\n", postfix);

return 0;
}
-------------------------------------------------------------------------------------------------------------
Expression : a+b*c
#include <stdio.h>

#define MAX 10

char stack[MAX];
int top = -1;

void push(char ch) {

top = top + 1;
stack[top] = ch;
}

char pop() {
char x = stack[top];
top = top - 1;
return x;
}

int main() {
char infix[] = "a+b*c";
char postfix[MAX];
int i, j = 0;

for (i = 0; infix[i] != '\0'; i++) {

char ch = infix[i];

if (ch >= 'a' && ch <= 'z') {

postfix[j++] = ch; // operand
 }
else if (ch == '+') {
push(ch); // operator +
}
else if (ch == '*') {
push(ch); // operator *
}
}

while (top != -1) {

postfix[j++] = pop();
}
postfix[j] = '\0';
printf("Postfix expression: %s\n", postfix);
return 0;
}
------------------------------------------------------------------------------------------------------
Expression must be in POSTFIX form to be evaluated using a stack,
because operator precedence and brackets make it ambiguous.

Postfix Evaluation Rules

Operand → push into stack
Operator → pop two operands
● first pop → operand2
● second pop → operand1
● compute , operand1 operator operand2
● push result back
----------------------------------------------------------------------------------------------
Perform infix to postfix conversion using stack data structure : 5 + 6 – 2 * 12/4
Also evaluate the obtained postfix expression using stack.(5 Marks)
Solution:
Operator Precedence Associativity
^ 3 Right
*/ 2 Left
+- 1 Left

Expression : 5 + 6 - 2 * 12 / 4
Scan Action Stack Postfix
5 Operand → output – 5
+ Push + 5
6 Operand → output + 56
 Stack top + has equal precedence → pop +,
- - 56+
push -
2 Operand → output - 56+2
* Higher than - → push -* 56+2
12 Operand → output -* 56+212
/ Equal precedence with * → pop *, push / - / 56+212*
4 Operand → output -/ 56+212*4
End Pop remaining stack → pop / then - – 56+212*4/-

Postfix Expression : 56+212*4/-

Evaluation Using Stack

Scan Action Stack (values)
5 Push 5
6 Push 5, 6
+ Pop 6, 5 → 5+6=11 → push 11
2 Push 11, 2
12 Push 11, 2, 12
* Pop 12, 2 → 2*12=24 → push 11, 24
4 Push 11, 24, 4
/ Pop 4, 24 → 24/4=6 → push 11, 6
- Pop 6, 11 → 11-6=5 → push 5

Final Answer is 5
Infix: 5 + 6 - 2 * 12 / 4
Postfix: 56+212*4/-
Evaluated Result: 5
=================================================================
Expression Conversion Using Stack (Polish Notation)
Algorithm:
Infix to Prefix Conversion ( 1 marks)
Step 1: Reverse the given infix expression.
While reversing, change ( to ) and ) to (.
Step 2: Convert the reversed infix expression into postfix expression using stack.
Step 3: Reverse the obtained postfix expression.
The result will be prefix expression.

Detailed Algorithm( for min. 5 marks)

1. Start
 2. Read the infix expression
3. Reverse the infix expression
4. Replace:
( with )
) with (
5. Initialize empty stack and postfix array
6. Scan the reversed expression from left to right
7. If operand → add to postfix
8. If ( → push into stack
9. If ) → pop from stack until ( is found
[Link] operator:
While stack not empty and precedence of top ≥ current operator
Pop from stack and add to postfix
Push current operator into stack
[Link] scanning complete expression
Pop all remaining operators from stack to postfix
[Link] postfix expression → get prefix
[Link]

Operator Rules ( Always Write This Below Algorithm )

● ^ → highest precedence, right-associative
● * / % → left-associative
● + - → left-associative
---------------------------------------------------------------------------------------------------
Convert infix expression into prefix : A+B*C
Solution :
1. Reverse the string: C*B+A
2. Find the post fix: CB*A+
3. Prefix of given expression : +A*BC

C Program to convert infix to prefix using reverse function

#include<stdio.h>
#include<string.h>

char stack[100];
int top = -1;

void push(char x){

stack[++top] = x;
}

char pop(){
return stack[top--];
}
int priority(char x){
if(x=='^') return 3;
if(x=='*' || x=='/') return 2;
if(x=='+' || x=='-') return 1;
return 0;
}

void reverse(char exp[]){

int i, j;
char temp;
int len = strlen(exp);

for(i=0, j=len-1; i<j; i++, j--){

temp = exp[i];
exp[i] = exp[j];
exp[j] = temp;
}
}

int main(){
char infix[100], postfix[100], prefix[100];
int i, k=0;

printf("Enter infix expression: ");

scanf("%s", infix);

// Step 1: reverse infix

reverse(infix);

// Step 2: change brackets

for(i=0; infix[i]; i++){
if(infix[i]=='(')
infix[i]=')';
else if(infix[i]==')')
infix[i]='(';
}

// Step 3: infix to postfix

for(i=0; infix[i]; i++){
char ch = infix[i];

if((ch>='A'&&ch<='Z') || (ch>='a'&&ch<='z') || (ch>='0'&&ch<='9')){

postfix[k++] = ch;
 }
else if(ch=='('){
push(ch);
}

C Program to convert infix to prefix using without reverse function

#include<stdio.h>
#include<string.h>

char stack[100];
int top = -1;

void push(char x){

stack[++top] = x;
}

char pop(){
return stack[top--];
}

int priority(char x){

if(x=='^') return 3;
if(x=='*' || x=='/') return 2;
if(x=='+' || x=='-') return 1;
return 0;
}

int main(){
char infix[100], postfix[100], prefix[100];
char rev[100];
int i, j=0, k=0;

printf("Enter infix expression: ");

scanf("%s", infix);

int len = strlen(infix);

// reverse infix manually

for(i=len-1; i>=0; i--){
if(infix[i]=='(')
rev[j++]=')';
else if(infix[i]==')')
rev[j++]='(';
 else
rev[j++]=infix[i];
}
rev[j]='\0';

// infix to postfix
for(i=0; rev[i]!='\0'; i++){
char ch = rev[i];

if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||(ch>='0'&&ch<='9')){
postfix[k++]=ch;
}
else if(ch=='('){
push(ch);
}
else if(ch==')'){
while(stack[top]!='('){
postfix[k++]=pop();
}
pop();
}
else{
while(top!=-1 && priority(stack[top])>=priority(ch)){
postfix[k++]=pop();
}
push(ch);
}
}

while(top!=-1){
postfix[k++]=pop();
}
postfix[k]='\0';

// reverse postfix to get prefix (manual)

int p=0;
for(i=k-1; i>=0; i--){
prefix[p++]=postfix[i];
}
prefix[p]='\0';

printf("Prefix expression: %s", prefix);

return 0;
}