Delhi Technical Campus, Greater Noida

DATA STRUCTURES

Unit: 1

SUBJECT NAME:- DATA STRUCTURES

SUBJECT CODE: CIC-209

COURSE: B.Tech FACULTY NAME: Ms. Pridhi Arora

DESIGNATION : Assistant Professor
BRANCH: CSE/CST
DEPARTMENT: CSE
COLLEGE:- DTC, GREATER NOIDA

9/13/2025 1
 INTRODUCTION: WHAT IS DATA STRUCTURES ?

A data structure is a way of organizing, managing, and storing data so that it can be
accessed and modified efficiently.

Think of it like arranging books in a library:

Random pile of books → hard to find one quickly.
Organized shelves by category → easy and fast to locate.
 Need for Data Structures

•Efficiency: Choose the right data structure to make operations faster.

•Memory management: Helps store data compactly.
•Reusability: Well-designed structures can be reused in multiple programs.
•Scalability: Handles large volumes of data efficiently.
 WHAT DATA STRUCTURES SPECIFIES?

• Organization of Data
• Accessing Methods
• Degree of Association
• Processing methods
 ALGORITHMS: WHAT IS AN ALGORITHM ?
• An algorithm is a step-by-step procedure to solve a problem.

In computer science, we define it more formally:

• An algorithm is a well-defined computational procedure.
• It always takes input (for example, numbers, data, text).
• It always produces an output (for example, a sum, a sorted list, or a search
result).
• It always finishes in a finite number of steps (it cannot go on forever).

Algorithms are the brains behind how data structures are used to solve
problems efficiently.
 ALGORITHMS: WHAT IS AN ALGORITHM ?

 An algorithm is any well-defined computational procedure that takes some

value, or set of values, as input and produces some value, or set of values, as
output in a finite amount of time.

Set of rules to
obtain the
INPUT expected OUTPUT
output from
given input

ALGORITHM
 ALGORITHMS: WHY WE STUDY ALGORITHMS ?
By studying algorithms, developers can write better programs. Some
examples are as follows:

1. Finding the fastest route in a GPS navigation system

2. Navigating an airplane or a car (cruise control)

3. Finding what users search for (search engine)

4. Sorting, for example sorting movies by rating

 CHARACTERISTICS OF AN ALGORITHM
Following are the characteristics of an algorithm:

1. WELL-DEFINED INPUT

2. WELL-DEFINED OUTPUT

3. UNAMBIGUITY

4. FINITENESS

5. FEASIBILITY
How do we judge whether
one algorithm is better
than another?
 ANALYSIS OF ALGORITHM

• The term “Analysis of Algorithms" was coined by Donald Knuth.

• To estimate the complexity function for large input.

• Analysis of algorithms is the determination of the amount of time and

space resources required to execute it.

• An algorithm's efficiency or running time is stated as a function relating

the input length to the number of steps, known as time complexity, or
volume of memory, known as space complexity.

• The main concern of the analysis of algorithms is the required time or

performance.
 ANALYSIS OF ALGORITHM

• Space Complexity
• Time Complexity
• Best Case
• Worst Case
• Average Case
 ANALYSIS OF ALGORITHM
•Space Complexity:
This tells us how much memory an algorithm uses while running. For example, a simple algorithm that just adds
two numbers will use very little memory, but a sorting algorithm working on millions of elements may need a lot of
space.

•Time Complexity:
This tells us how much time an algorithm takes to execute, depending on the size of input. For example,
searching for a number in a list of 10 elements is fast. But what if the list has 10 million elements? The time
increases — and that’s what we measure.

•Best Case:
This is the scenario where the algorithm performs in the minimum possible time. Example: In linear search, if the
element we’re searching is the very first one, that’s the best case.

•Worst Case:
This is when the algorithm takes the maximum possible time. Example: In the same linear search, if the element
is at the very end of the list — or not present at all — that’s the worst case.

•Average Case:
This is the expected running time over many different inputs. It gives us a more realistic idea of performance.
 TIME COMPLEXITY OF AN ALGORITHM

• Time complexity is defined as the amount of time taken by an

algorithm to run, as a function of the length of the input. It
measures the time taken to execute each statement of code in an
algorithm.

• Time complexity is commonly estimated by counting the number of

elementary operations performed by the algorithm, supposing that
each elementary operation takes a fixed amount of time to perform.
 TIME COMPLEXITY OF AN ALGORITHM
• Why is time complexity a function of its input size?
To perfectly grasp the concept of "as a function of input size," imagine you have an algorithm that
computes the sum of numbers based on your input. If your input is 4, it will add 1+2+3+4 to output
10; if your input is 5, it will output 15 (meaning 1+2+3+4+5).
 TIME COMPLEXITY OF AN ALGORITHM

In the above code, we have three statement

• Looking at the image above, we only have three statements. Still, because there is a loop, the second statement will
be executed based on the input size, so if the input is four, the second statement (statement 2) will be executed four
times, meaning the entire algorithm will run six (4 + 2) times.

• In plain terms, the algorithm will run input + 2 times, where the input can be any number. This shows that it's
expressed in terms of the input. In other words, it is a function of the input size.
 TIME COMPLEXITY OF AN ALGORITHM

How to measure time?

Count the total number of fundamental operations in the program and this total
will give a rough estimate of the running time in terms of input size.

• Best Case: The minimum number of steps taken on any instance of size n.

• Average Case: An average number of steps taken on any instance of size n.

• Worst Case: The maximum number of steps taken on any instance of size n.
 TIME COMPLEXITY OF AN ALGORITHM

Running time for Algorithm

• ALGORITHM COST RUNNING TIME
Sum(A,n)
{
S=0 C1 1
for i=1 to n do C2 n+1
s=s+A[i] C3 n
return s C4 1
}

• Total Running Time = c1 + c2(n+1)+c3(n) + c4

• T(n) = Linear function
9/13/2025 19
9/13/2025 20
9/13/2025 21
TOPIC: TYPES OF DATA STRUCTURES

22
 TOPIC: TYPES OF DATA STRUCTURES
DATA TYPES: Data Types are declarations of variables. This determines the type
and size of data associated with variables.

TYPES OF DATA STRUCTURES:

1. PRIMITIVE DATA-STRUCTURES

2. NON-PRIMITIVE DATA-STRUCTURES

9/13/2025 23
 TOPIC: PRIMITIVE DATA STRUCTURES
• PRIMITIVE DATA STRUCTURES:

• Primitive data structure is considered as the fundamental data

structure and it allows storing the values of only one data type.
• The primitive data structure consists of fundamental data types like
float, character, integer, etc.
• A variable with the data type integer can allow storing the values of
integer type only, a variable with the float data type can allow storing
the values of float data type, and the variable with the character data
type allows storing character values only.

9/13/2025 24
 TOPIC: PRIMITIVE DATA STRUCTURES
• PRIMITIVE DATA STRUCTURES:

9/13/2025 25
 TOPIC: NON-PRIMITVE DATA STRUCTURES
• NON-PRIMITIVE DATA STRUCTURES:

• Non-Primitive data structures are considered as the user-defined structure that

allows storing values of different data types within one entity.

• Non-primitive data structures are the data structures created by the programmer
with the help of primitive data structures.
 TOPIC: TYPES OF NON-PRIMITIVE DATA STRUCTURES

• NON-PRIMITIVE DATA STRUCTURES ARE FURTHER DIVIDED INTO TWO

CATEGORIES:

1. LINEAR DATA STRUCTURES

2. NON-LINEAR DATA STRUCTURES

9/13/2025 27
 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES

• LINEAR DATA STRUCTURES:

• In linear data structures, the elements are arranged in sequence one
after the other. Since elements are arranged in a particular order,
they are easy to implement. However, when the complexity of the
program increases, the linear data structures might not be the best
choice because of operational complexities.

• Examples: ARRAYS,LINKED LIST, QUEUES, STACKS.

9/13/2025 28
 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES
• LINEAR DATA STRUCTURES:

9/13/2025 29
 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES

• NON-LINEAR DATA STRUCTURES:

• Unlike linear data structures, elements in non-linear data structures
are not in any sequence. Instead, they are arranged in a hierarchical
manner where one element will be connected to one or more
elements.

• Examples: TREES, GRAPHS, MAP

9/13/2025 30
 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES

• NON-LINEAR DATA STRUCTURES:

9/13/2025 31
 TOPIC: DIFFERENCE BETWEEN LINEAR AND NON-LINEAR DATA
STRUCTURES
S.NO LINEAR DATASTRUCTURES NON-LINEAR DATA STRUCTURES
1 The data items are arranged in The data items are arranged in non-sequential
sequential order, one after the other. order (hierarchical manner).

2 All the items are present on the single The data items are present at different layers.
layer.

3 It can be traversed on a single run. That It requires multiple runs. That is, if we start from
is, if we start from the first element, we the first element it might not be possible to
can traverse all the elements sequentially traverse all the elements in a single pass.
in a single pass.

4 The memory utilization is not efficient. Different structures utilize memory in different
efficient ways depending on the need.

5 The time complexity increase with the Time complexity remains the same.
data size.

6 Example: Arrays, Stack, Queue. Example: Tree, Graph, Map. 32

 Thank you

9/13/2025 33
 Arrays: Definition, Single and Multidimensional Arrays

What is an Array?
A linear data structure where elements are stored sequentially.
Stores a collection of elements of the same data type in contiguous memory locations.

How it Works?
Each element has an index (starting from 0).
The position of each element can be calculated using the base address + offset.
Offset = Index × Size of data type.

1
2
 How to declare an array in C

• datatype arrayName[array Size];

• int marks[5];

• In C programming, when an array is declared, memory is allocated for its elements, but the initial values of
these elements remain undefined or contain garbage values. This means that until explicitly initialized, the
contents of a newly declared array in C are unpredictable.

• Array Size in C: It's crucial to note that in C, the size of an array is fixed upon declaration and cannot be altered
thereafter. This underscores the importance of planning array usage according to fixed size constraints in C
applications.

Example:
int marks[5]; // Declaration
marks[0] = 85; // Initialization
int marks[5] = {10, 20, 30, 40, 50}; // Declaration + Initialization

3
 How to initialize and Change values in an array in C

• dataType arrayName[arraySize] = {value1, value2, ..., valueN};

• int myarray[5] = {1, 2, 3, 4, 5};

• int myarray[] = {1, 2, 3, 4, 5};

• make the value of the third element to -1

myarray[2] = -1;

• make the value of the fifth element to 0

myarray[4] = 0;

4
 Types of indexing in array

• 0 (zero-based indexing): The first element of the array is indexed by subscript of 0

• 1 (one-based indexing): The first element of the array is indexed by subscript of 1

• n (n-based indexing): The base index of an array can be freely chosen. Usually programming
languages allowing n-based indexing also allow negative index values and other scalar data types like
enumerations, or characters may be used as an array index.

5
 Size of an array

Number of elements = (Upper bound – Lower Bound) + 1

• Lower bound index of the first element of the array

• Upper bound index of the last element of the array
• Size = number of elements * Size of each elements in bytes

6
 One Dimensional array

• Address of the element at kth index

• a[k] = B + W*(k – Lower bound)

• B is the base address of the array

• W is the size of each element
• K is the index of the element
• Lower bound index of the first element of the array
• Upper bound index of the last element of the array

7
 Example: Given the base address of an array

A[1300 ………… 1900] as 1020 and the size

of each element is 2 bytes in the memory,
find the address of A[1700].

6/11/2024 8
Given:

Base address B = 1020

Lower Limit/Lower Bound of subscript LB = 1300

Storage size of one element store in any array W = 2 Byte

Subset of element whose address to be found I = 1700

Formula: Address of A[I] = B + W*(k – Lower bound)

Solution:

Address of A[1700] = 1020 + 2 * (1700 – 1300)

= 1020 + 2 * (400)

= 1020 + 800

Address of A[1700] = 1820

9
 Two-Dimensional array

• A two-dimensional (2D) array is essentially an array of arrays. It is organized in a matrix-like structure,

consisting of rows and columns. This makes it ideal for representing data in a tabular format.

• 2D arrays are often used to simulate relational databases or other grid-based structures. They allow for
efficient storage and retrieval of large amounts of data, which can easily be passed to multiple functions as
needed, simplifying data management.

data_type array_name[rows][columns];

int myArray[2][4] = {
{10, 11, 12, 13},
{14, 15, 16, 17}
};

OR

int myArray[2][4] = { 10, 11, 12, 13, 14, 15, 16, 17};
10
 Implementation of 2D array

• In computing, row-major order and column-major order are methods for storing multidimensional arrays in
linear storage such as random access memory.

• The difference between the orders lies in which elements of an array are contiguous in memory.

11
 Row Major implementation of 2D array

• In Row major method elements of an array are arranged sequentially row by row.

• Thus, elements of first row occupies first set of memory locations reserved for the array, elements of second
row occupies the next set of memory and so on.

12
 Row Major implementation of 2D array

Address of a[i][j] = B + W*[ (U2-L2+1) (i-L1) + (j-L2)]

B = Base address
W = Size of each element
L1 = Lower bound of rows
U1 = Upper bound of rows
L2 = Lower bound of columns
U2 = Upper bound of columns
(U2-L2+1) = numbers of columns
(i-L1) = number of rows before us
(j-L2) = number of elements before us in current row

13
Given an array, arr[1………10][1………15]
with base value 100 and the size of each
element is 1 Byte in memory. Find the address
of arr[8][6] with the help of row-major order.

14
Given an array, arr[1………10][1………15] with base value 100 and the size of each element is 1 Byte in memory.
Find the address of arr[8][6] with the help of row-major order.
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound + 1
= 15 – 1 + 1
= 15
Formula: Address of A[I][J] = B + W*[ (U2-L2+1) (i-L1) + (j-L2)]
Solution: Address of A[8][6] = 100 + 1 * ((15–1+1) * (8-1) + (6 – 1))
= 100 + 1 * ((15) * 7 + (5))
= 100 + 1 * (110)
Address of A[I][J] = 210
15
 Column Major implementation of 2D array

• In Column major method elements of an array are arranged sequentially column by column. Thus, elements of
first column occupies first set of memory locations reserved for the array, elements of second column occupies
the next set of memory and so on.

16
 Column Major implementation of 2D array

Address of a[i][j] = B + W*[ (U1-L1+1) (j-L2) + (i-L1)]

B = Base address
W = Size of each element
L1 = Lower bound of rows
U1 = Upper bound of rows
L2 = Lower bound of columns
U2 = Upper bound of columns
(U1-L1+1) = numbers of rows
(j-L2) = number of columns before us
(i-L1) = number of elements before us in current column

17
Given an array, arr[1………10][1………15]
with base value 100 and the size of each
element is 1 Byte in memory. Find the address
of arr[8][6] with the help of column - major
order.

18
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of Rows given in the matrix M = Upper Bound – Lower Bound + 1
= 10 – 1 + 1
= 10
Formula: Address of A[I][J] = B + W*[ (U1-L1+1) (j-L2) + (i-L1)]

Address of A[8][6] = 100 + 1 * ((10–1+1) *(6-1) + (8 – 1))

= 100 + 1 * ((10) * 5+ (7))
= 100 + 1 * (57)
Address of A[I][J] = 157 19
 Representation of Arrays: Row Major Order, and Column Major Order

Aspect Row Major Order Column Major Order

Elements are stored row by row in contiguous Elements are stored column by column in
Memory Organization
locations. contiguous locations.
For a 2D array A[m][n]: [A[0][0], A[0][1], …, For the same array: [A[0][0], A[1][0], …,
Memory Layout Example
A[m-1][n-1]] A[m-1][n-1]]

Moves through the entire row before Moves through the entire column before
Traversal Direction
progressing to the next row. progressing to the next column.

Efficient for row-wise access, less efficient Efficient for column-wise access, less
Access Efficiency
for column-wise access. efficient for row-wise access.

Common Use Cases Commonly used in languages like C and C++. Commonly used in languages like Fortran.

Suitable for row-wise operations, e.g., image Suitable for column-wise operations, e.g.,
Applications
processing. matrix multiplication.

So it’s all based on the position of the element whose address is to be found for some cases the same answers is also obtained with row-
major order and column-major order and for some cases, different answers are obtained.
20
 Advantages and Disadvantages

• Advantages of Arrays:
• Efficient Storage and Access: Arrays store elements in contiguous memory locations, allowing for fast
retrieval using indices, making them suitable for handling large amounts of data.
• Random Access: Arrays provide constant-time access to any element using its index, making operations like
reading or updating an element extremely efficient.
• Ease of Use: Arrays are simple to understand and use, with common sorting and searching algorithms like
binary search applicable, making them an accessible data structure for beginners and experts alike.

• Disadvantages of Arrays:
• Fixed Size: Once created, the size of an array cannot be changed, which can be restrictive when working with
dynamic data where the size of the data set may increase or decrease.
• Lack of Flexibility for Insertion/Deletion: Arrays do not natively support efficient insertion or deletion of
elements, as these operations may require shifting elements, which can be time-consuming.
• Homogeneous Elements: Arrays can only store elements of the same data type, limiting their flexibility in
scenarios that require handling multiple types of data.

21
 1D vs 2D

Basis One Dimension Array Two Dimension Array

Store a single list of the element of a similar Store a ‘list of lists’ of the element of a similar data
Definition
data type. type.
Represent multiple data items as a table consisting of
Representation Represent multiple data items as a list.
rows and columns.
The declaration varies for different The declaration varies for different programming
programming language: language:
2. For C++, 2. For C++,
Declaration datatype variable_name[row] datatype variable_name[row][column]
3. For Java, 3. For Java,
datatype [] variable_name= new datatype [][] variable_name= new
datatype[row] datatype[row][column]
Dimension One Two
size of(datatype of the variable of the array) * size of(datatype of the variable of the array)* the
Size(bytes)
size of the array number of rows* the number of columns.

22
 Arrays: Definition, Single and Multidimensional Arrays

Basis One Dimension Array Two Dimension Array

Address of a[i][j] can be calculated in two ways row-
major and column-major
2. Column Major: Base Address + Size of each
Address Address of a[index] is equal to (base Address+ element (number of rows(j-lower bound of the
calculation. Size of each element of array * index). column)+(i-lower bound of the rows))
3. Row Major: Base Address + Size of each
element (number of columns(i-lower bound of
the row)+(j-lower bound of the column))
int arr[2][5]; //an array with two rows and five
int arr[5]; //an array with one row and five columns will be created.
Example columns will be created.
a b c d e
{a , b , c , d , e}
f g h i j

23
 Array Operations:

1. Traversal
2. Insertion
3. Deletion
4. Updation
5. Searching
6. Sorting

24
 Array Operation: Traversal

•Definition: Accessing and visiting each element of the array one by one.
•Example: Printing all elements of an array.

Algorithm for Array Traversal:

1. Start
2. Initialize a loop variable i=0
3. Loop while i<n (array size)
4. Access and process element at index i
5. Increment i
6. End loop when all elements are processed

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

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

25
 Array Operation: Traversal

#include <stdio.h>

int main()
{
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate number of elements

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

{
printf("Element at index %d: %d\n", i, arr[i]);
}

return 0;
}

26
 Array Operation: Insertion

Insertion means adding a new element into the array at a specific position (beginning, end, or middle).

Types of Insertions

27
 Array Operations: Insertion

Algorithm
Suppose we want to insert item at position pos in an array of size n.

Step 1: Start
Step 2: If array is full → Insertion not possible
Step 3: For i = n-1 down to pos:
arr[i+1] = arr[i] // shift elements
Step 4: arr[pos] = item
Step 5: n = n + 1
Step 6: Stop

28
 #include <stdio.h>

int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5; // current size
int item = 25, pos = 2; // insert at index 2 (0-based)

// shift elements to right

for (int i = n - 1; i >= pos; i--) {
arr[i + 1] = arr[i];
}
// place item
arr[pos] = item;
n++;

// print updated array

printf("Array after insertion:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

6/11/2024 29
 Array Operations: Insertion

Insertion at the Beginning of an Array

Algorithm
Step 1: Start
Step 2: If array is full → Insertion not possible
Step 3: For i = n-1 down to 0:
arr[i+1] = arr[i] // shift elements right
Step 4: arr[0] = item // place new element
Step 5: n = n + 1 // increase size
Step 6: Stop

30
#include <stdio.h>

int main() {
int arr[10] = {10, 20, 30, 40};
int n = 4; // current size
int item = 5; // element to insert

// shift elements to right

for (int i = n - 1; i >= 0; i--) {
arr[i + 1] = arr[i];
}

// place at first position

arr[0] = item;
n++;

// print updated array

printf("Array after insertion at beginning:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
} 31
 Array Operations: Insertion

Insertion at the End of an Array

Algorithm
Step 1: Start
Step 2: If array is full → Insertion not possible
Step 3: arr[n] = item // place at last index
Step 4: n = n + 1 // increase size
Step 5: Stop

32
#include <stdio.h>

int main() {
int arr[10] = {10, 20, 30, 40};
int n = 4; // current size
int item = 50; // element to insert

// place at the end

arr[n] = item;
n++;

// print updated array

printf("Array after insertion at end:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

33
 Applications of Array Data Structure:
1. Storing and accessing data: Arrays are used to store and retrieve data in a specific order. For example, an array can be
used to store the scores of a group of students, or the temperatures recorded by a weather station.
2. Sorting: Arrays can be used to sort data in ascending or descending order. Sorting algorithms such as bubble sort, merge
sort, and quicksort rely heavily on arrays.
3. Searching: Arrays can be searched for specific elements using algorithms such as linear search and binary search.
4. Matrices: Arrays are used to represent matrices in mathematical computations such as matrix multiplication, linear
algebra, and image processing.
5. Stacks and queues: Arrays are used as the underlying data structure for implementing stacks and queues, which are
commonly used in algorithms and data structures.
6. Graphs: Arrays can be used to represent graphs in computer science. Each element in the array represents a node in the
graph, and the relationships between the nodes are represented by the values stored in the array.
7. Dynamic programming: Dynamic programming algorithms often use arrays to store intermediate results of subproblems
in order to solve a larger problem.

34
STACK IN DATA
STRUCTURES
Definition, Operations, Implementation, Applications
Introduction
Definition
◦ A Stack is a linear data structure that follows the LIFO principle – Last In, First
Out.
◦ This means the last element inserted into the stack is the first one removed.
Key Idea
◦ Insertion and deletion happen only from one end, called the Top.
◦ Think of it like a pile where items are added or removed from the same side.
Real-Life Examples
◦ 📚 Stack of Books/Plates → You can only take from the top.
◦ ↩️ Undo/Redo in Text Editor → The most recent action is undone first.
◦ 🌐 Browser History → The last visited page is the first to go back to.
◦ 📞 Call Stack in Programming → Keeps track of function calls.
Properties of Stack

1. LIFO Principle (Last In, First Out)

◦ The most recently added element is removed first.
◦ Example: Last plate kept on top is the first to be taken out.
2. Access is Restricted
◦ Insertion and deletion happen only from one end (Top).
◦ Unlike arrays or linked lists, you can’t insert/remove from anywhere.
3. Representation
◦ Stack can be implemented using:
◦ Array → Fixed size, simple to implement.
◦ Linked List → Dynamic size, flexible memory usage.
4. Efficiency
◦ Push, Pop, Peek all take O(1) time.
◦ Very fast compared to searching in arrays or lists.
Properties of Stack
5. Key Operations
◦ Push → Add an element at the top.
◦ Pop → Remove the element from the top.
◦ Peek/Top → View the element at the top without
removing it.
◦ isEmpty → Check if the stack has no elements.
◦ isFull → Check if the stack has reached its maximum
capacity (in array implementation).
Stack Representation
1. Using Array
◦ Stored in contiguous memory.
◦ Easy to implement but has fixed size.
◦ Variables:
◦ stack[MAX] → Array to hold elements.
◦ top → Index of current top element.
◦ Conditions:
◦ Overflow → when top == MAX – 1.
◦ Underflow → when top == -1.
Stack Representation
◦ 2. Using Linked List
◦ Each node contains:
◦ Data field.
◦ Pointer to next node.
◦ The Top pointer always points to the head node.
◦ Advantage: Dynamic size → grows/shrinks at runtime.
◦ No overflow unless memory is exhausted.
Algorithm for Push
Push Operation (Insert element at Top)
Algorithm
◦ If TOP == MAX – 1 → Overflow (Stack is full).
◦ Else:
◦ Increment TOP (TOP = TOP + 1).
◦ Set STACK[TOP] = ITEM.
◦ End.
Algorithm for Pop
◦ Pop Operation (Remove element from Top)
◦ Algorithm
◦ If TOP == -1 → Underflow (Stack is empty).
◦ Else:
◦ Set ITEM = STACK[TOP].
◦ Decrement TOP (TOP = TOP – 1).
◦ Return ITEM.
◦ End.
Array Implementation of Stack
#include <stdio.h> { printf("Stack is empty\n");

#define MAX 5 // maximum size of printf("Stack Overflow! Cannot push } else {

stack %d\n", x);
printf("Top element is: %d\n",
int stack[MAX]; } else { stack[top]);

int top = -1; // stack is initially empty stack[++top] = x; }

// Function to check if stack is full printf("%d pushed into stack\n", x); }

int isFull() }

{ } int main() {

return top == MAX - 1; // Pop operation push(10);

} void pop() { push(20);

if(isEmpty()) { push(30);

// Function to check if stack is empty printf("Stack Underflow! Cannot peek(); // shows top element
pop\n");
int isEmpty() pop();
} else {
{ peek();
printf("%d popped from stack\n",
return top == -1; stack[top--]); return 0;

} } }

}
// Push operation

void push(int x) // Peek operation

{ void peek() {
if(isFull()) if(isEmpty()) {
Linked Implementation of Stack
#include <stdio.h> printf("Stack Overflow! Memory not }
available\n");
#include <stdlib.h>
return;
// Peek operation
}
// Node structure void peek() {
newNode->data = x;
struct Node { if(isEmpty()) {
newNode->next = top;
int data; printf("Stack is empty\n");
top = newNode;
struct Node* next; } else {
printf("%d pushed into stack\n", x);
}; printf("Top element is: %d\n", top-
} >data);

}
struct Node* top = NULL;
// Pop operation }

void pop() {
// Check if stack is empty
if(isEmpty()) { int main() {
int isEmpty() {
printf("Stack Underflow! Cannot push(10);
return top == NULL; pop\n");
push(20);
} } else {
push(30);
struct Node* temp = top;
peek(); // shows top element
// Push operation printf("%d popped from stack\n",
top->data); pop();
void push(int x) {
top = top->next; peek();
struct Node* newNode = (struct
Node*)malloc(sizeof(struct Node)); free(temp); return 0;

if(newNode == NULL) { } }
Applications of Stack
1. Expression Handling
◦ Converting Infix → Postfix → Prefix
◦ Evaluating Postfix expressions
2. Parentheses Balancing
◦ Checking valid brackets { [ ( ) ] } in compilers
3. Function Calls / Recursion
◦ Maintains function call sequence in memory
4. Undo/Redo
◦ Editors (MS Word, Photoshop, etc.)
5. Browser Navigation
◦ Back/Forward button uses stack
What is an Expression?
◦ An expression is a combination of operands (variables, constants)
and operators (+, -, *, /, ^) that represents a computation.
◦ Example: A + B * C
◦ Expressions tell what operation to perform and in what order.
Types of Expressions
Infix Expression
•Operator is between operands.
•Example: A + B
•This is the way we normally write math (human-friendly).
•Problem: Ambiguity (needs parentheses and operator precedence).

Prefix Expression (Polish Notation)

•Operator comes before operands.
•Example: + A B
•Advantage: No parentheses needed; evaluation is unambiguous.

Postfix Expression (Reverse Polish Notation)

•Operator comes after operands.
•Example: A B +
•Widely used in compilers, calculators, and stack-based evaluation.
•Easy for computers (using stack, left-to-right evaluation).
Algorithm to Convert Infix to Postfix
 Operator Precedence &
Associativity
Precedence
Operator Description Associativity
(High → Low)
Exponentiation
^ Highest Right → Left
(power)
Multiplication,
*, /, % Division, Higher than +, - Left → Right
Modulus
Addition,
+, - Lower than *, / Left → Right
Subtraction
Overrides all
Parentheses
(, ) (highest N/A
(grouping)
control)
Infix: A + B * C → Postfix: A B C * +
Symbol Action Stack Postfix
A Output — A
+ Push + A
B Output + AB
Push (higher
* +* AB
than +)
C Output +* ABC
End Pop *, then + — ABC*+
Infix: (A + B) * C  Postfix :A B + C *

Token Action Stack Postfix

( Push ( —
A Output ( A
+ Push (+ A
B Output (+ AB
) Pop until ( — AB+
* Push * AB+
C Output * AB+C
End Pop * — AB+C*
A+B*C-D/E → ABC*+DE/-

Token Action Stack Postfix

A Output — A
+ Push + A
B Output + AB
Push (higher
* +* AB
than +)
C Output +* ABC
Pop * (higher),
- pop + (equal), - ABC+*
then push -
D Output - ABC+D*
Push (higher
/ -/ ABC*+D
than -)
E Output -/ ABC+DE*
End Pop /, then - — ABC+DE/-*
(A + B) * (C - D) / E → A B + C D - * E /

Token Action Stack Postfix

( Push ( —
A Output ( A
+ Push (+ A
B Output (+ AB
) Pop until ( — AB+
* Push * AB+
( Push *( AB+
C Output *( AB+C
- Push *(- AB+C
D Output *(- AB+CD
) Pop -, pop ( * AB+CD-
Pop * (equal
/ precedence), / AB+CD-*
push /
E Output / *AB+CD-E
End Pop / — *AB+CD-E/
Evaluation of Postfix Expression
Example 1: 5 6 2 + *

Token Action Stack

5 Push [5]
6 Push [5, 6]
2 Push [5, 6, 2]
Pop 2 & 6 → 6+2=8 →
+ [5, 8]
Push 8
Pop 8 & 5 → 5*8=40
* [40]
→ Push 40
Example 2: 7 4 5 * + 6 -

Token Action Stack

7 Push [7]
4 Push [7, 4]
5 Push [7, 4, 5]
Pop 5 & 4 → 20 →
* [7, 20]
Push
Pop 20 & 7 → 27 →
+ [27]
Push
6 Push [27, 6]
Pop 6 & 27 → 27–
- [21]
6=21 → Push
What is the equivalent infix expression of the following postfix
expression?
M, N, O, +, *, P, /, Q, R, S, T, /, +, *, –

◦ N*(M+Q)/Q-P*(S+R/T)
◦ (((M*(N+O))/P)-(Q*(R+(S/T))))
◦ O * (M + N)/P – Q * (R + S/T)
◦ M * (N + O)/Q – P * (R/S + T)
What is the equivalent infix expression of the following postfix
expression?
M, N, O, +, *, P, /, Q, R, S, T, /, +, *, –

◦ N*(M+Q)/Q-P*(S+R/T)
◦ (((M*(N+O))/P)-(Q*(R+(S/T))))
◦ O * (M + N)/P – Q * (R + S/T)
◦ M * (N + O)/Q – P * (R/S + T)
The result evaluating the postfix expression 10 5 + 60 6 / * 8 − is
◦ 284
◦ 213
◦ 142
◦ 71
The result evaluating the postfix expression 10 5 + 60 6 / * 8 − is
◦ 284
◦ 213
◦ 142
◦ 71
What is the postfix representation of the following infix expression?
(A + B) * C – D * E / F
◦ AB+C*DE*F-/
◦ AB*C+DE*F/-
◦ AB+C–DE*F/*
◦ AB+C*DE*F/-
What is the postfix representation of the following infix expression?
(A + B) * C – D * E / F
◦ AB+C*DE*F-/
◦ AB*C+DE*F/-
◦ AB+C–DE*F/*
◦ AB+C*DE*F/-
Consider the following postfix expression with single digit operands:
623*/42*+68*-
The top two elements of the stack after second * is evaluated, are:
◦ 6, 3
◦ 8, 1
◦ 8, 2
◦ 6, 2
Consider the following postfix expression with single digit operands:
623*/42*+68*-
The top two elements of the stack after second * is evaluated, are:
◦ 6, 3
◦ 8, 1
◦ 8, 2
◦ 6, 2
Complexity Analysis

◦ Push: O(1).
◦ Pop: O(1).
◦ Peek: O(1).
◦ Space Complexity: O(n).
Summary

◦ Stack is a LIFO data structure.

◦ Operations: Push, Pop, Peek.
◦ Implementations: Array & Linked List.
◦ Applications: Expressions, Recursion, Undo/Redo.