DATA STRUCTURES (PCC2011)
Module 0: Prerequisite Concepts
(C Programming Revision)
Purpose of this module:
Before studying data structures, students must be clear with basic C programming concepts.
These concepts are repeatedly used while implementing stacks, queues, linked lists, and trees.
1. Functions in C
A function is a block of code that performs a specific task.
Instead of writing the same code again and again, functions allow us to reuse code.
In data structures, almost every operation is written as a function, such as:
• insert()
• delete()
• display()
• search()
Types of Functions
1. Library functions – provided by C
Examples: printf(), scanf(), strlen()
2. User-defined functions – written by programmer
Example
int sum(int a, int b)
{
return a + b;
}
Why functions are important in Data Structures
• Programs become modular
• Easy to debug and modify
• Each operation can be handled separately
2. Recursion
Recursion is a technique in which a function calls itself to solve a problem.
Every recursive function must have:
1. Base condition – stops recursion
2. Recursive call – function calling itself
Example: Factorial
int fact(int n)
{
if(n == 0)
return 1;
else
return n * fact(n - 1);
}
Use of Recursion in Data Structures
• Tree traversal
• Linked list operations
• Expression evaluation
Advantages
• Code becomes short and clear
Disadvantages
• Extra memory required
• Can slow down execution
3. Arrays
An array is a collection of elements of the same data type stored in continuous memory
locations.
Example
int a[5] = {10, 20, 30, 40, 50};
Characteristics of Arrays
• Fixed size
• Fast access using index
• Elements stored sequentially
Limitations of Arrays
• Size cannot be changed at runtime
• Insertion and deletion are difficult
• Memory wastage may occur
Due to these limitations, dynamic data structures are required.
4. Pointers
A pointer is a variable that stores the address of another variable.
Example
int x = 10;
int *p;
p = &x;
Here, p stores the address of variable x.
Importance of Pointers in Data Structures
• Used for dynamic memory allocation
• Used to link nodes in linked lists and trees
• Makes efficient use of memory
Without pointers, implementation of most data structures is not possible.
5. Structures
A structure is a user-defined data type that allows grouping of different data types.
Example
struct student
{
int roll;
char name[20];
};
Use of Structures in Data Structures
Structures are used to create nodes.
Example of node:
struct node
{
int data;
struct node *next;
};
Each node contains:
• Data part
• Link part (pointer)
6. Dynamic Memory Allocation
In data structures, memory is allocated at runtime using:
• malloc() – allocates memory
• calloc() – allocates and initializes memory
• free() – releases memory
Example
int *p;
p = (int *)malloc(sizeof(int));
Dynamic memory allocation helps in creating dynamic data structures.
7. Control Structures Used
Common C constructs used in data structure programs:
• if–else
• switch
• for loop
• while loop
• do–while loop
• break and continue
Key Points to Remember (Module 0)
• Functions divide programs into logical parts
• Recursion is widely used in trees and linked lists
• Arrays are static in nature
• Pointers are the backbone of data structures
• Structures + pointers form nodes
DATA STRUCTURES (PCC2011)
Module I: Introduction to Data Structures
1. Introduction
In computer applications, the amount of data to be stored and processed is increasing day by day.
When data is small, simple variables are sufficient. However, when data becomes large and
complex, proper organization of data becomes necessary.
This leads to the concept of Data Structures.
2. Data
Data is a collection of raw facts and values which are processed by a computer.
Examples of data:
• Student roll numbers
• Marks of students
• Employee IDs
By itself, data has no meaning unless it is properly organized and processed.
3. Data Structure
A data structure is a method of organizing and storing data in memory so that operations such
as access, insertion, deletion, and searching can be performed efficiently.
Common examples of data structures:
• Array
• Stack
• Queue
• Linked List
• Tree
Different data structures are used depending on the nature of the problem.
4. Need for Data Structures
Data structures are required because of the following reasons:
• Efficient use of memory
• Faster data processing
• Easy searching and sorting
• Proper organization of large data
• Better program performance
Without data structures, programs become slow and difficult to manage.
5. Abstract Data Type (ADT)
An Abstract Data Type (ADT) defines:
• The type of data to be stored
• The operations that can be performed on the data
ADT does not describe how the data is stored in memory.
Example: Stack ADT
Operations defined:
• push
• pop
• peek
• isEmpty
The stack can be implemented using:
• Array
• Linked List
This separation makes programs more flexible and easier to modify.
6. Classification of Data Structures
Data structures are broadly classified as follows:
6.1 Linear Data Structures
In linear data structures, data elements are arranged in a sequential manner.
Each element has a single predecessor and a single successor (except first and last).
Examples:
• Array
• Stack
• Queue
• Linked List
6.2 Non-Linear Data Structures
In non-linear data structures, data elements are arranged in a hierarchical or graphical manner.
There is no fixed sequence.
Examples:
• Tree
• Graph
6.3 Static Data Structures
In static data structures:
• Memory size is fixed
• Memory is allocated at compile time
Example:
• Array
6.4 Dynamic Data Structures
In dynamic data structures:
• Memory size is not fixed
• Memory is allocated at runtime
Examples:
• Linked List
• Tree
7. Operations on Data Structures
The basic operations performed on data structures are:
• Insertion – adding a new element
• Deletion – removing an existing element
• Traversal – accessing each element one by one
• Searching – finding a particular element
• Sorting – arranging elements in order
• Merging – combining two data structures
These operations form the base of all data structure programs.
8. Applications of Data Structures
Data structures are widely used in real-world applications such as:
• Operating Systems
• Database Management Systems
• Compiler Design
• Computer Networks
• Artificial Intelligence
• File Handling Systems
Key Points to Remember (Module I)
• Data structures help in organizing data efficiently
• ADT defines operations without implementation
• Linear and non-linear structures are basic classifications
• Choosing the correct data structure improves performance
MU Exam-Oriented Questions (Module I)
1. Define data structure and explain its need.
2. What is ADT? Explain with example.
3. Differentiate between linear and non-linear data structures.
4. Explain operations performed on data structures.
DATA STRUCTURES (PCC2011)
Module II: Stack
1. Introduction to Stack
A stack is a linear data structure in which insertion and deletion of elements take place from
only one end, called TOP.
Stack follows the principle of LIFO (Last In First Out).
The element inserted last is the first one to be removed.
Real-life examples:
• Stack of books
• Stack of plates
• Undo/Redo operations in software
2. Stack Terminology
• TOP – Points to the topmost element of the stack
• Push – Operation to insert an element into the stack
• Pop – Operation to remove an element from the stack
• Overflow – Stack is full, insertion not possible
• Underflow – Stack is empty, deletion not possible
3. Stack as an Abstract Data Type (ADT)
The Stack ADT defines the structure and operations without specifying the implementation.
Stack ADT Operations:
• push(x)
• pop()
• peek()
• isEmpty()
• isFull()
Stack can be implemented using:
• Array
• Linked List
4. Operations on Stack
4.1 Push Operation
Push operation inserts an element at the top of the stack.
Steps:
1. Check overflow condition
2. Increment TOP
3. Insert element at TOP
4.2 Pop Operation
Pop operation removes the top element from the stack.
Steps:
1. Check underflow condition
2. Access element at TOP
3. Decrement TOP
4.3 Peek Operation
Peek operation returns the top element without removing it.
5. Array Implementation of Stack
In array implementation, stack is represented using:
• An array
• A variable TOP
Initial Condition:
TOP = -1;
Stack Size:
int stack[MAX];
Push Operation (Algorithm)
1. If TOP == MAX − 1, display “Stack Overflow”
2. Else
o TOP = TOP + 1
o stack[TOP] = item
Pop Operation (Algorithm)
1. If TOP == -1, display “Stack Underflow”
2. Else
o item = stack[TOP]
o TOP = TOP − 1
6. C Program: Stack using Array
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
void push(int item)
{
if(top == MAX - 1)
printf("Stack Overflow\n");
else
{
top++;
stack[top] = item;
printf("Inserted %d\n", item);
}
}
void pop()
{
if(top == -1)
printf("Stack Underflow\n");
else
{
printf("Deleted %d\n", stack[top]);
top--;
}
}
void display()
{
int i;
if(top == -1)
printf("Stack is empty\n");
else
{
for(i = top; i >= 0; i--){
printf("%d\n", stack[i]);
}
}
}
int main()
{
push(10);
push(20);
pop();
display();
return 0;
}
7. Multiple Stacks
Multiple stacks can be implemented in a single array to utilize memory efficiently.
Common methods:
• Dividing array into fixed parts
• Dynamic allocation approach
8. Evaluation of Arithmetic Expressions
Stack is widely used in expression evaluation.
Types of Expressions:
• Infix – A + B
• Prefix – +AB
• Postfix – AB+
Stack is mainly used to evaluate postfix and prefix expressions.
9. Applications of Stack
• Function calls and recursion
• Expression evaluation
• Undo / Redo operations
• Reversing data
• Syntax parsing
Key Points to Remember (Module II)
• Stack follows LIFO principle
• All operations occur at TOP
• Overflow and underflow must be checked
• Stack can be implemented using array or linked list
MU Exam-Oriented Questions (Module II)
1. Define stack and explain its operations.
2. Explain stack ADT.
3. Write algorithm for push and pop operations.
4. Implement stack using array in C.
5. Explain applications of stack.