Contents

Basic concepts of data structures:..........................................................................................................1

Memory Management in Data Structures..............................................................................................4
Pointers..................................................................................................................................................4
Arrays..................................................................................................................................................19
Structures:...........................................................................................................................................24
Union:..................................................................................................................................................36
Polynomial..........................................................................................................................................39
Sparse Matrix......................................................................................................................................42
Strings.................................................................................................................................................46
Taking String input with space in C (4 Different Methods).................................................................48
Stack....................................................................................................................................................50
4. Stack Applications............................................................................................................................51
Stack Using Dynamic Arrays in C..........................................................................................................52
Stack using Array:................................................................................................................................59
Stack using Linked List:........................................................................................................................61
Queue:.................................................................................................................................................63
Queue Implementation using Array(static array):................................................................................65
Queue Implementation using Linked List:............................................................................................66
Applications of Queue.....................................................................................................................68
Circular Queue:....................................................................................................................................69
5. C Program: Circular Queue Using Dynamic Array......................................................................70
Example 1:.......................................................................................................................................70
Example 2:.......................................................................................................................................74
1. What is Expression Evaluation?.......................................................................................................82

Data Structures and Applications

Basic concepts of data structures:

[Link] is a Data Structure?
A data structure is a way of organizing, storing, and managing data in a computer so it can be used
efficiently. It defines the relationship between the data and the operations that can be performed on it.
2. Classification of Data Structures
🔹 A. Primitive Data Structures
These are the basic data types provided by a programming language:

1|Page
  Integer
 Float
 Character
 Boolean
 Pointer (in C/C++)
🔹 B. Non-Primitive Data Structures
These are derived from primitive data types and are used to store a large and connected set of values.
➤ Linear Data Structures
 Elements are stored in a sequential order.
 Examples:
o Array
o Linked List
o Stack
o Queue
➤ Non-Linear Data Structures
 Elements are not stored sequentially; they are arranged hierarchically or graphically.
 Examples:
o Tree
o Graph
➤ File Structures
 Used for persistent storage (on disk), e.g., file systems, indexed files.

3. Data Structure Operations

Common operations performed on data structures include:
Operation Description

Traversal Visiting each element exactly once

Insertion Adding an element at a specific position

Deletion Removing an element from the structure

Searching Finding the location of an element

Sorting Arranging elements in a specific order

Merging Combining two data structures

4. Static vs Dynamic Data Structures

2|Page
 Feature Static Dynamic
Size Fixed at compile- Can change at run-time
time
Memory Done at compile-time Done at run-time
Allocation
Example Array Linked List, Stack using pointers

5. Importance of Data Structures

 Efficiency: Optimizes memory and processing time.
 Reusability: Used across different applications.
 Maintainability: Clean code organization.
 Scalability: Handles growing data.

6. Abstract Data Types (ADT)

An ADT is a logical description of how we view the data and the operations that are allowed without
considering how they are implemented.
ADT Description

List Ordered collection of elements

Stack LIFO (Last In First Out)

Queue FIFO (First In First Out)

Tree Hierarchical data representation

Graph Network of interconnected nodes

Hash Table Key-value pair storage

Memory Management in Data Structures

 Static Allocation: Uses fixed memory (e.g., arrays).
 Dynamic Allocation: Allocates memory at runtime using:
o malloc(), calloc(), realloc(), free() in C.

Pointers
1. What is Pointers?
A pointer is a variable that stores the memory address of another variable.
Think of a pointer as a "GPS location" for a variable. Instead of holding a value directly, it tells you
where to find that value in memory.

 Declaration: int *ptr;

3|Page
  Initialization: ptr = &x;
 Dereferencing: *ptr gives the value at the address stored in ptr
 NULL Pointer: A pointer that points to nothing: ptr = NULL;
2. Uses in Data Structures:
 Linked Lists
 Trees
 Dynamic Arrays
 Graphs
3. Dynamic Memory Allocation (DMA)
Dynamic memory is allocated during runtime using specific functions in C language.
Function Purpose

malloc() Allocates single block of memory

calloc() Allocates multiple blocks and initializes to zero

realloc() Reallocates memory to resize a block

free() Frees the allocated memory

Syntax Examples:
int *p = (int*) malloc(5 * sizeof(int));
float *q = (float*) calloc(10, sizeof(float));
p = realloc(p, 10 * sizeof(int));
free(p);
DMA using malloc():
Allocate memory for an array of integers (size entered by the user), input values, and print them.
#include <stdio.h>
#include <stdlib.h>
int main() {
int *ptr;
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
// dynamically allocate memory using malloc
ptr = (int*) malloc(n * sizeof(int));
// check if memory has been allocated
if (ptr == NULL) {

4|Page
 printf("Memory allocation failed!\n");
return 1;
}
// input values
printf("Enter %d integers:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &ptr[i]);
}
// print values
printf("You entered:\n");
for(i = 0; i < n; i++) {
printf("%d ", ptr[i]);
}
// free the allocated memory
free(ptr);
return 0;
}
Output Example:
Enter the number of elements: 3
Enter 3 integers:
10
20
30
You entered:
10 20 30
Explanation:
 malloc(n * sizeof(int)) allocates memory for n integers.
 Always check if malloc() returns NULL, which means allocation failed.
 Finally, use free(ptr); to release memory back to the system.
What is calloc()?
 calloc() (contiguous allocation) allocates memory for multiple elements and initializes them
to 0.
 Syntax:
ptr = (type *) calloc(number_of_elements, size_of_each_element);

5|Page
Goal:
 Allocate memory for an array of integers using calloc().
 Take input from user and display the values.
Example code for calloc():
#include <stdio.h>
#include <stdlib.h>
int main() {
int *ptr;
int n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
// Dynamic memory allocation using calloc
ptr = (int*) calloc(n, sizeof(int));
// Check if memory allocation was successful
if (ptr == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
// Show default values (all should be 0)
printf("Default values after calloc:\n");
for(i = 0; i < n; i++) {
printf("%d ", ptr[i]);
}
// Input values
printf("\n\nEnter %d integers:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &ptr[i]);
}
// Print entered values
printf("You entered:\n");
for(i = 0; i < n; i++) {
printf("%d ", ptr[i]);
}
// Free the allocated memory

6|Page
 free(ptr);
return 0;
}
Output:
Enter number of elements: 4
Default values after calloc:
0000
Enter 4 integers:
5
15
25
35
You entered:
5 15 25 35

Key Differences from malloc():

Feature malloc() calloc()
Initializatio Garbage values Initializes all to zero
n
Syntax malloc(n * size) calloc(n, size)
2. Pointer Declaration and Initialization
int *ptr; // Declaration
int x = 10;
ptr = &x; // Initialization with address of x
 *ptr – "value at the address" (dereferencing)
 &x – "address of x"
3. Pointer Diagram
int x = 10;
int *ptr = &x;
// Memory Representation
+--------+ +------+
| x | | ptr |
| 10 | | &x |
+--------+ +------+
 ptr stores the address of x.

7|Page
  *ptr gives the value stored at that address → *ptr = 10.
4. Why Use Pointers?
Use Case Description

Dynamic memory allocation Use with malloc(), calloc(), etc.

Function arguments by reference Allows functions to modify actual values

Data structures (linked lists) Used to link nodes via addresses

Array manipulation Arrays are accessed using pointers

Efficient performance Speeds up code and reduces memory usage

5. Pointer Arithmetic
Allowed operations:
 ptr++ → Move to next memory location
 ptr + i → Move i steps forward
 ptr - i → Move i steps backward
int arr[3] = {10, 20, 30};
int *p = arr;
printf("%d", *(p + 1)); // Output: 20

6. Types of Pointers
Type Description

NULL Pointer Points to nothing → int *p = NULL;

Dangling Pointer Points to freed/deleted memory

Void Pointer Generic pointer → can store any type

Function Pointer Stores address of a function

Pointer to Pointer Pointer storing address of another pointer → int **pp;

7. Example Code
#include <stdio.h>
int main() {
int x = 25;
int *p = &x;
printf("Value of x: %d\n", x); // 25
printf("Address of x: %p\n", &x); // e.g., 0x7ffe...
printf("Pointer p: %p\n", p); // same as &x

8|Page
 printf("Value at p: %d\n", *p); // 25
return 0;
}
Example 2:
#include <stdio.h>
int main() {
// Normal Variable
int var = 10;
// Pointer Variable ptr that
// stores address of var
int* ptr = &var;
// Directly accessing ptr will
// give us an address
printf("%d", ptr);
return 0;
}
Output
0x7fffa0757dd4

Dereference a Pointer
We have to first dereference the pointer to access the value present at the memory address. This is
done with the help of dereferencing operator(*) (same operator used in declaration).
#include <stdio.h>
int main() {
int var = 10;
// Store address of var variable
int* ptr = &var;
// Dereferencing ptr to access the value

9|Page
 printf("%d", *ptr);
return 0;
}
Output
10
Special Types of Pointers
There are 4 special types of pointers that used or referred to in different contexts:
NULL Pointer
The NULL Pointers are those pointers that do not point to any memory location. They can be created
by assigning NULL value to the pointer. A pointer of any type can be assigned the NULL value.
#include <stdio.h>
int main() {
// Null pointer
int *ptr = NULL;
return 0;
}
NULL pointers are generally used to represent the absence of any address. This allows us to check
whether the pointer is pointing to any valid memory location by checking if it is equal to NULL.
Void Pointer
The void pointers in C are the pointers of type void. It means that they do not have any associated
data type. They are also called generic pointers as they can point to any type and can be typecasted to
any type.
#include <stdio.h>
int main() {
// Void pointer
void *ptr;
return 0;
}
Wild Pointers
The wild pointers are pointers that have not been initialized with something yet. These types of C-
pointers can cause problems in our programs and can eventually cause them to crash. If values are
updated using wild pointers, they could cause data abort or data corruption.
#include <stdio.h>
int main() {
// Wild Pointer
int *ptr;

10 | P a g e
 return 0;
}
Dangling Pointer
A pointer pointing to a memory location that has been deleted (or freed) is called a dangling pointer.
Such a situation can lead to unexpected behavior in the program and also serve as a source of bugs in
C programs.
#include <stdio.h>
#include <stdlib.h>
int main() {
int* ptr = (int*)malloc(sizeof(int));
// After below free call, ptr becomes a dangling pointer
free(ptr);
printf("Memory freed\n");
// removing Dangling Pointer
ptr = NULL;
return 0;
}
Output
Memory freed
Constant Pointers
In constant pointers, the memory address stored inside the pointer is constant and cannot be
modified once it is defined. It will always point to the same memory address.
Example:
#include <stdio.h>
int main() {
int a = 90;
int b = 50;
// Creating a constant pointer
int* const ptr = &a;
// Trying to reassign it to b
ptr = &b;
return 0;
}

Output

11 | P a g e
solution.c: In function ‘main’:
solution.c:11:9: error: assignment of read-only variable ‘ptr’
11 | ptr = &b;
| ^
Pointer to Function
A function pointer is a type of pointer that stores the address of a function, allowing functions to be
passed as arguments and invoked dynamically. It is useful in techniques such as callback functions,
event-driven programs.
Example:
#include <stdio.h>
int add(int a, int b) {
return a + b;
}
int main() {
// Declare a function pointer that matches
// the signature of add() fuction
int (*fptr)(int, int);
// Assign address of add()
fptr = &add;
// Call the function via ptr
printf("%d", fptr(10, 5));
return 0;
}
Output
15
Multilevel Pointers
In C, we can create multi-level pointers with any number of levels such as – ***ptr3, ****ptr4,
******ptr5 and so on. Most popular of them is double pointer (pointer to pointer). It stores the
memory address of another pointer. Instead of pointing to a data value, they point to another pointer.
Example:
#include <stdio.h>
int main() {
int var = 10;
// Pointer to int
int *ptr1 = &var;
// Pointer to pointer (double pointer)

12 | P a g e
 int **ptr2 = &ptr1;
// Accessing values using all three
printf("var: %d\n", var);
printf("*ptr1: %d\n", *ptr1);
printf("**ptr2: %d", **ptr2);
return 0;
}
Output
var: 10
*ptr1: 10
**ptr2: 10
8. Common Mistakes to Avoid
 Dereferencing a NULL or uninitialized pointer.
 Not freeing dynamically allocated memory (free()).
 Using freed memory (dangling pointer).
 Misusing pointer types (e.g., casting void pointers improperly).
What is realloc()?
 realloc() stands for reallocation.
 It is used to change the size of a previously allocated memory block (by malloc() or calloc()).
 It helps when you don’t know in advance how much memory you'll need and want to
expand or shrink it at runtime.
Syntax:
ptr = realloc(ptr, new_size);
Goal:
 Allocate memory for 3 integers.
 Store and print them.
 Use realloc() to expand it to 5 integers.
 Store and print the new values.
Example code for realloc():
#include <stdio.h>
#include <stdlib.h>
int main() {
int *ptr;
int i;

13 | P a g e
 // Step 1: Allocate memory for 3 integers
ptr = (int*) malloc(3 * sizeof(int));
if (ptr == NULL) {
printf("Memory not allocated.\n");
return 1;
}
// Step 2: Initialize the first 3 integers
printf("Enter 3 integers:\n");
for (i = 0; i < 3; i++) {
scanf("%d", &ptr[i]);
}
// Step 3: Reallocate memory to store 5 integers
ptr = (int*) realloc(ptr, 5 * sizeof(int));
if (ptr == NULL) {
printf("Memory reallocation failed.\n");
return 1;
}
// Step 4: Initialize the next 2 integers
printf("Enter 2 more integers:\n");
for (i = 3; i < 5; i++) {
scanf("%d", &ptr[i]);
}
// Step 5: Print all 5 integers
printf("The 5 integers are:\n");
for (i = 0; i < 5; i++) {
printf("%d ", ptr[i]);
}
// Step 6: Free the allocated memory
free(ptr);
return 0;
}
Output:
Enter 3 integers:
10

14 | P a g e
20
30
Enter 2 more integers:
40
50
The 5 integers are:
10 20 30 40 50
Why Use realloc()?
 Saves memory by resizing instead of allocating new blocks.
 Keeps existing values intact up to the smaller of old or new size.
 Useful for dynamic arrays, buffers, etc.

Arrays
1. What is an Array?
An array is a collection of elements (all of the same data type) stored in contiguous memory
locations.
Think of it as a row of lockers, where each locker (element) has:
 An index (position)
 A value
int arr[5]; // declares an integer array of size 5
 Index starts from 0 → arr[0] to arr[4]
 All elements are of the same type (int here)
3. Types of Arrays
Type Example Description
1D Array int a[5]; Single row of data
2D Array int mat[3][3]; Table-like (rows × columns)
Multidimensional int arr[2][3][4]; Arrays within arrays (3D and
above)
Character Array char str[10]; or char Used for strings
*s;

4. Array Initialization
int a[3] = {10, 20, 30}; // With values
int b[5] = {0}; // All elements initialized to 0
char name[] = "ChatGPT"; // Character array (string)

5. Accessing Array Elements

15 | P a g e
arr[0] = 25; // Assign 25 to first element
printf("%d", arr[2]); // Print third element

6. Memory Representation
int a[3] = {5, 10, 15};
// Memory layout (assume base address = 1000)
// Index | Value | Address
// 0 | 5 | 1000
// 1 | 10 | 1004
// 2 | 15 | 1008
Each integer takes 4 bytes.

7. Array and Pointers

 a[i] is the same as *(a + i)
 Array name itself is a pointer to the first element
int a[3] = {1, 2, 3};
printf("%d", *(a + 2)); // Output: 3
8. Limitations of Arrays
Limitation Explanation
Fixed size Size must be known at compile time
Wastes memory If declared size > needed
Insertion/Deletion Costly operations (O(n) time)
No dynamic Unlike linked lists or vectors
resizing
9. Dynamic Arrays (via malloc)
int *a;
a = (int*) malloc(n * sizeof(int)); // `n` taken at runtime
This allows flexible array creation when size is unknown at compile time.
10. Strings as Character Arrays
char name[10] = "Kavya";
 name[0] = 'K'
 Ends with a null character '\0'
What is a Dynamically Allocated Array?
A dynamically allocated array is an array whose size is determined at runtime, not at compile
time.
 Created using functions like malloc(), calloc(), or realloc()

16 | P a g e
  Memory is allocated from the heap, not the stack
 Very useful when the number of elements is not known beforehand
Why Use Dynamic Arrays?
Static Array Dynamic Array
Size must be fixed in code Size can be decided at runtime
Memory allocated at compile- Memory allocated at runtime
time
Can waste memory or overflow More flexible and scalable

1. Creating a 1D Dynamic Array using malloc()

#include <stdio.h>
#include <stdlib.h>
int main() {
int *arr;
int n, i;
printf("Enter the size of the array: ");
scanf("%d", &n);
// Allocate memory for n integers
arr = (int*) malloc(n * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed.\n");
return 1;
}
// Input elements
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Display elements
printf("Array elements are:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
// Free allocated memory
free(arr);
return 0;
17 | P a g e
}
2. Creating a 2D Dynamic Array
#include <stdio.h>
#include <stdlib.h>
int main() {
int **arr;
int i, j, rows, cols;
printf("Enter rows and columns: ");
scanf("%d %d", &rows, &cols);
// Allocate array of row pointers
arr = (int**) malloc(rows * sizeof(int*));
// Allocate each row
for(i = 0; i < rows; i++) {
arr[i] = (int*) malloc(cols * sizeof(int));
}
// Input elements
printf("Enter elements:\n");
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
scanf("%d", &arr[i][j]);
}
}
// Display elements
printf("2D Array:\n");
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
// Free memory
for(i = 0; i < rows; i++) {
free(arr[i]);
}

18 | P a g e
 free(arr);
return 0;
}
Key Points:
 Always check if memory allocation is successful (if (ptr == NULL))
 Use free() to deallocate memory and avoid memory leaks
 You can grow/shrink arrays using realloc()

Structures:
1. What is a Structure?
A structure in C is a user-defined data type that allows grouping variables of different data types
under a single name.
Think of a structure like a record or form — each field can have a different type (e.g., name: string,
age: int).

2. Why Use Structures?

 To group related data (e.g., a student’s roll number, name, and marks)
 Helps model real-world entities
 Used in complex data structures like linked lists, trees, etc.

3. Structure Syntax
struct Student {
int rollNo;
char name[50];
float marks;
};
This defines a blueprint (structure template). It doesn't allocate memory yet.
4. Declaring Structure Variables
struct Student s1, s2;
You can also combine definition + declaration:
struct Student {
int rollNo;
char name[50];
float marks;
} s1, s2;

19 | P a g e
5. Accessing Structure Members
Use the dot . operator:
[Link] = 101;
strcpy([Link], "John");
[Link] = 85.5;
printf("%d %s %.2f", [Link], [Link], [Link]);
6. Using Pointers with Structures
struct Student *ptr = &s1;
printf("%d", ptr->rollNo); // use -> operator
7. Array of Structures
struct Student students[3];

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

scanf("%d %s %f", &students[i].rollNo, students[i].name, &students[i].marks);
}

8. Nested Structures
struct Date {
int day, month, year;
};
struct Student {
int id;
char name[50];
struct Date dob;
};
Access like:
[Link] = 15;
9. Difference: Structure vs Union
Feature struct union
Memory Each member has separate All members share same
memory memory
Size Sum of all members Size of largest member
Use case Store all values together Store only one value at a time
10. Structure as Function Argument
void display(struct Student s);
display(s1); // Pass by value
20 | P a g e
Or use pointer for pass by reference:
void update(struct Student *s);
update(&s1);
Example Program
#include <stdio.h>
#include <string.h>
struct Student {
int roll;
char name[30];
float marks;
};
int main() {
struct Student s;
[Link] = 101;
strcpy([Link], "Kavya");
[Link] = 92.5;
printf("Roll: %d\nName: %s\nMarks: %.2f\n", [Link], [Link], [Link]);
return 0;
}
Example:
#include <stdio.h>
// Defining a structure
struct A {
int x;
};
int main() {
// Creating a structure variable
struct A a;
// Initializing member
a.x = 11;
printf("%d", a.x);
return 0;
}

21 | P a g e
Output
11
Explanation: In this example, a structure A is defined to hold an integer member x. A variable a of
type struct A is created and its member x is initialized to 11 by accessing it using dot operator. The
value of a.x is then printed to the console.
Structures are used when you want to store a collection of different data types, such as integers, floats,
or even other structures under a single name.
Syntax of Structure
There are two steps of creating a structure in C:
1. Structure Definition
2. Creating Structure Variables
Structure Definition
A structure is defined using the struct keyword followed by the structure name and its members. It is
also called a structure template or structure prototype, and no memory is allocated to the structure in
the declaration.
struct structure_name {
data_type1 member1;
data_type2 member2;
...
};
 structure_name: Name of the structure.
 member1, member2, ...: Name of the members.
 data_type1, data_type2, ...: Type of the members.
Be careful not to forget the semicolon at the end.
Creating Structure Variable
After structure definition, we have to create variable of that structure to use it. It is similar to the any
other type of variable declaration:
struct structure_name var;
We can also declare structure variables with structure definition.
struct structure_name {
...
}var1, var2....;
Basic Operations of Structure
Following are the basic operations commonly used on structures:
1. Access Structure Members
To access or modify members of a structure, we use the ( . ) dot operator. This is applicable when we
are using structure variables directly.

22 | P a g e
structure_name . member1;
structure_name . member2;
In the case where we have a pointer to the structure, we can also use the arrow operator to access the
members.
structure_ptr -> member1
structure_ptr -> member2
2. Initialize Structure Members
Structure members cannot be initialized with the declaration. For example, the following C program
fails in the compilation.
struct structure_name {
data_type1 member1 = value1; // COMPILER ERROR: cannot initialize members here
data_type2 member2 = value2; // COMPILER ERROR: cannot initialize members here
...
};
The reason for the above error is simple. When a datatype is declared, no memory is allocated for it.
Memory is allocated only when variables are created. So there is no space to store the value assigned.
#include <stdio.h>
// Defining a structure to represent a student
struct Student {
char name[50];
int age;
float grade;
};
int main() {
// Declaring and initializing a structure
// variable
struct Student s1 = {"Rahul",20, 18.5};
// Designated Initializing another structure
struct Student s2 = {.age = 18, .name =
"Vikas", .grade = 22};
// Accessing structure members
printf("%s\t%d\t%.2f\n", [Link], [Link],
[Link]);
printf("%s\t%d\t%.2f\n", [Link], [Link],
[Link]);
return 0;
}
Output

23 | P a g e
Rahul 20 18.50
Vikas 18 22.00
We can initialize structure members in 4 ways which are as follows:
Default Initialization
By default, structure members are not automatically initialized to 0 or NULL. Uninitialized structure
members will contain garbage values. However, when a structure variable is declared with an
initializer, all members not explicitly initialized are zero-initialized.
struct structure_name s = {0}; // Both x and y are initialized to 0
Initialization using Assignment Operator
struct structure_name str;
str.member1 = value1;
....
Note: We cannot initialize the arrays or strings using assignment operator after variable declaration.
Initialization using Initializer List
struct structure_name str = {value1, value2, value3 ....};
In this type of initialization, the values are assigned in sequential order as they are declared in the
structure template.
Initialization using Designated Initializer List
Designated Initialization allows structure members to be initialized in any order.
struct structure_name str = { .member1 = value1, .member2 = value2, .member3 = value3 };
3. Copy Structure
Copying structure is simple as copying any other variables. For example, s1 is copied into s2 using
assignment operator.
s2 = s1;
But this method only creates a shallow copy of s1 i.e. if the structure s1 have some dynamic resources
allocated by malloc, and it contains pointer to that resource, then only the pointer will be copied
to s2. If the dynamic resource is also needed, then it has to be copied manually (deep copy).
#include <stdio.h>
#include <stdlib.h>
struct Student {
int id;
char grade;
};
int main() {
struct Student s1 = {1, 'A'};
// Create a copy of student s1
struct Student s1c = s1;

24 | P a g e
 printf("Student 1 ID: %d\n", [Link]);
printf("Student 1 Grade: %c", [Link]);
return 0;
}
Output
Student 1 ID: 1
Student 1 Grade: A
4. Passing Structure to Functions
Structure can be passed to a function in the same way as normal variables. Though, it is recommended
to pass it as a pointer to avoid copying a large amount of data.
#include <stdio.h>
// Structure definition
struct A {
int x;
};

// Function to increment values

void increment(struct A a, struct A* b) {
a.x++;
b->x++;
}
int main() {
struct A a = { 10 };
struct A b = { 10 };
// Passing a by value and b by pointer
increment(a, &b);
printf("a.x: %d \tb.x: %d", a.x, b.x);
return 0;
}

Output
a.x: 10 b.x: 11
5. typedef for Structures
The typedef keyword is used to define an alias for the already existing datatype. In structures, we have
to use the struct keyword along with the structure name to define the variables. Sometimes, this

25 | P a g e
increases the length and complexity of the code. We can use the typedef to define some new shorter
name for the structure.
#include <stdio.h>
// Defining structure
typedef struct {
int a;
} str1;
// Another way of using typedef with structures
typedef struct {
int x;
} str2;
int main() {
// Creating structure variables using new names
str1 var1 = { 20 };
sr2 var2 = { 314 };
printf("var1.a = %d\n", var1.a);
printf("var2.x = %d\n", var2.x);
return 0;
}
Output
var1.a = 20
var2.x = 314
Explanation: In this code, str1 and str2 are defined as aliases for the unnamed structures, allowing
the creation of structure variables (var1 and var2) using these new names. This simplifies the syntax
when declaring variables of the structure.
Size of Structures
Technically, the size of the structure in C should be the sum of the sizes of its members. But it may
not be true for most cases. The reason for this is Structure Padding.
Structure padding is the concept of adding multiple empty bytes in the structure to naturally align
the data members in the memory. It is done to minimize the CPU read cycles to retrieve different data
members in the structure.
Nested Structures
In C, a nested structure refers to a structure that contains another structure as one of its members. This
allows you to create more complex data types by grouping multiple structures together, which is
useful when dealing with related data that needs to be grouped within a larger structure.
There are two ways in which we can nest one structure into another:

26 | P a g e
  Embedded Structure Nesting: The structure being nested is also declared inside the parent
structure.
 Separate Structure Nesting: Two structures are declared separately and then the member
structure is nested inside the parent structure.
Accessing Nested Members
We can access nested Members by using the same ( . ) dot operator two times as shown:
str_parent . str_child . member;
Example
#include <stdio.h>
// Child structure declaration
struct child {
int x;
char c;
};
// Parent structure declaration
struct parent {
int a;
struct child b;
};
int main() {
struct parent p = { 25, 195, 'A' };
// Accessing and printing nested members
printf("p.a = %d\n", p.a);
printf("p.b.x = %d\n", p.b.x);
printf("p.b.c = %c", p.b.c);
return 0;
}
Output
p.a = 25
p.b.x = 195
p.b.c = A
Explanation: In this code, the structure parent contains another structure child as a member.
The parent structure is then initialized with values, including the values for the child structure's
members.
Structure Pointer

27 | P a g e
A pointer to a structure allows us to access structure members using the ( -> ) arrow operator instead
of the dot operator.
#include <stdio.h>
// Structure declaration
struct Point {
int x, y;
};
int main() {
struct Point p = { 1, 2 };
// ptr is a pointer to structure p
struct Point* ptr = &p;
// Accessing structure members using structure pointer
printf("%d %d", ptr->x, ptr->y);
return 0;
}
Output
12
Explanation: In this example, ptr is a pointer to the structure Point. It holds the address of the
structure variable p. The structure members x and y are accessed using the -> operator, which is used
to dereference the pointer and access the members of the structure.
Self-Referential Structures
The self-referential structures are those structures that contain references to the same type as
themselves i.e. they contain a member of the type pointer pointing to the same structure type.
Example:
struct str {
int mem1;
// Reference to the same type
struct str* next;
};
Such kinds of structures are used in different data structures such as to define the nodes of linked lists,
trees, etc.
Uses of Structure in C
C structures are used for the following:
1. The structure can be used to define the custom data types that can be used to create some
complex data types such as dates, time, complex numbers, etc. which are not present in the
language.
2. It can also be used in data organization where a large amount of data can be stored in different
fields.

28 | P a g e
 3. Structures are used to create data structures such as trees, linked lists, etc.
4. They can also be used for returning multiple values from a function.

Union:
1. What is a Union?
A union is a user-defined data type in C similar to a structure, but with a key difference:
All members share the same memory location.
A union allows storing different data types in the same memory space, but only one member can
hold a valid value at a time.
2. Syntax of Union
union Item {
int i;
float f;
char ch;
};
This creates a union named Item that can store an int, float, or char — but only one at a time.
3. Declaring Union Variables
union Item item1, item2;
Or combine with definition:
union Item {
int i;
float f;
char ch;
} item1, item2;
4. Accessing Union Members
Use the dot operator (.) for normal access, or arrow operator (->) when using pointers.
item1.i = 10;
printf("%d", item1.i);
5. Memory Allocation in Union
In a union, memory is shared. So the size of the union is equal to the size of its largest member.
Example:
union Test {
int a; // 4 bytes
float b; // 4 bytes
char c; // 1 byte

29 | P a g e
};
Total size of union Test = 4 bytes (not 9 like in structures).
6. Example Program
#include <stdio.h>
union Data {
int i;
float f;
char str[20];
};
int main() {
union Data data;
data.i = 10;
printf("data.i = %d\n", data.i);
data.f = 220.5;
printf("data.f = %.2f\n", data.f);
// Previous values are now overwritten
data.i = 30;
printf("data.i = %d\n", data.i);
return 0;
}
Output:
data.i = 10
data.f = 220.50
data.i = 30
Note: Only one member has a valid value at a time. Setting one member overwrites the previous one.
7. Union vs Structure
Feature Structure Union
Memory Separate memory for each Shared memory among all members
member
Size Sum of all member sizes Size of largest member
Usage Store multiple values at once Store one value at a time
Access All members can be used together Only one member is meaningful

8. Use Cases of Unions

 Memory-saving applications
 Embedded systems

30 | P a g e
  Situations where only one value is used at a time
 Variant data types in protocol design, device drivers

Polynomial
1. What is a Polynomial?
A polynomial is a mathematical expression consisting of variables, coefficients, and powers:
Example:
P(x) = 4x³ + 3x² + 2x + 1
Each term has:
 Coefficient (like 4, 3, 2, 1)
 Exponent/power (3, 2, 1, 0)
2. Why Represent Polynomials in Data Structures?
To store, evaluate, add, subtract, and multiply polynomials using code.
3. Polynomial Representation
A. Using Array
We can use an array of structures where each structure holds:
 coefficient
 exponent
struct Term {
int coeff;
int expo;
};
Example for 4x³ + 2x + 5:
Index Coeff Expo

0 4 3

1 2 1

2 5 0
B. Using Linked List
Each node represents a term:
struct Poly {
int coeff;
int expo;
struct Poly *next;

31 | P a g e
};
Example:
4x³ → 2x¹ → 5
Each node contains coeff, expo, and a link to the next term.
This is more efficient for sparse polynomials.

4. Polynomial Operations
A. Polynomial Addition
 Traverse both polynomials.
 If exponents match, add coefficients.
 If exponents differ, copy the term with higher exponent.
B. Polynomial Multiplication
 Multiply every term of P1 with every term of P2.
 Combine like terms (same exponent).
5. Example – Polynomial using Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int coeff;
int expo;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int c, int e) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->coeff = c;
newNode->expo = e;
newNode->next = NULL;
return newNode;
}
// Function to display the polynomial
void display(struct Node* head) {
while (head != NULL) {
printf("%dx^%d", head->coeff, head->expo);

32 | P a g e
 head = head->next;
if (head != NULL)
printf(" + ");
}
printf("\n");
}
// Simple main function to create and display a polynomial
int main() {
struct Node *poly = NULL, *temp;
// Create 3x^3 + 4x^2 + 5
poly = createNode(3, 3);
poly->next = createNode(4, 2);
poly->next->next = createNode(5, 0);
printf("Polynomial: ");
display(poly);
return 0;
}
Output:
Polynomial: 3x^3 + 4x^2 + 5x^0
Benefits of Linked List Representation:
 No unused memory
 Easy insertion of new terms
 Efficient for sparse polynomials

Sparse Matrix
What is a Sparse Matrix?
A sparse matrix is a matrix that contains mostly zeros.
For example:
Matrix A:
[0 0 3]
[0 0 0]
[5 0 0]
In this matrix:
 Total elements = 3 × 3 = 9

33 | P a g e
  Non-zero elements = 2
Since most elements are 0, this is a sparse matrix.
Why Use Sparse Matrices?
 Saves memory: No need to store all the zeros.
 Improves performance: Useful in scientific computing, graphs, AI (neural networks), etc.
 Efficient for large datasets with few non-zero values.
Representation of Sparse Matrix
1. Normal 2D Array Representation
int mat[3][3] = {
{0, 0, 3},
{0, 0, 0},
{5, 0, 0}
};
Problem: Wastes memory storing many zeroes.
2. Triplet (Array of Tuples) Representation
Only store: (row, column, value) for non-zero elements.
Row Col Value

0 2 3

2 0 5
We can also add the matrix size at the top:
Row Col Value

3 3 2

0 2 3

2 0 5
Memory-efficient
3. Linked List Representation
Each node stores:
 Row index
 Column index
 Value
 Pointer to next node
Best for dynamic sparse matrices or when insertion/deletion is frequent.
Example: Sparse Matrix to Triplet Representation in C
#include <stdio.h>

34 | P a g e
int main() {
int mat[3][3] = {
{0, 0, 3},
{0, 0, 0},
{5, 0, 0}
};
int i, j, count = 0;
// Count non-zero elements
for(i = 0; i < 3; i++) {
for(j = 0; j < 3; j++) {
if(mat[i][j] != 0)
count++;
}
}
// Create triplet array: rows = count + 1 (header row)
int triplet[count + 1][3];
// Header: rows, columns, non-zero count
triplet[0][0] = 3;
triplet[0][1] = 3;
triplet[0][2] = count;
int k = 1;
for(i = 0; i < 3; i++) {
for(j = 0; j < 3; j++) {
if(mat[i][j] != 0) {
triplet[k][0] = i;
triplet[k][1] = j;
triplet[k][2] = mat[i][j];
k++;
}
}
}
// Display triplet
printf("Triplet representation:\n");

35 | P a g e
 for(i = 0; i <= count; i++) {
printf("%d %d %d\n", triplet[i][0], triplet[i][1], triplet[i][2]);
}
return 0;
}
Output:
Triplet representation:
332
023
205
Summary Table
Feature Dense Matrix Sparse Matrix (Triplet)
Memory Usage High (stores all) Low (stores only non-zeros)
Storage Format 2D array Triplet or Linked List
Ideal For Mostly non-zero Mostly zero data
data

Strings
A string is a sequence of characters terminated by a null character '\0'. Unlike many modern
languages, in C, strings are arrays of characters.
1. Declaration and Initialization
char str1[] = "Hello"; // Automatically null-terminated
char str2[6] = "Hello"; // Same as above (5 chars + '\0')
char str3[] = {'H', 'e', 'l', 'l', 'o', '\0'}; // Manual declaration
Without '\0', it's not a proper C string.
2. Input and Output
Output:
printf("%s", str1);
Input:
char name[20];
scanf("%s", name); // Reads input until first space
To read full lines (with spaces), use:
fgets(name, 20, stdin);
3. Common String Functions (from <string.h>)

36 | P a g e
Function Description

strlen(s) Returns length (excluding '\0')

strcpy(dest, src) Copies string

strcat(dest, src) Concatenates

strcmp(s1, s2) Compares strings (returns 0 if equal)

strrev(s) (non-standard) Reverses string

strchr(s, c) Finds first occurrence of c in s

strstr(s1, s2) Finds substring s2 in s1

4. String Traversal Example
char str[] = "Kohila";
int i = 0;
while (str[i] != '\0') {
printf("%c\n", str[i]);
i++;
}
5. Mutable vs Immutable Strings
 In C, strings declared as arrays are mutable:
char str[] = "Hi";
str[0] = 'B'; // Valid
 But string literals are read-only:
char *str = "Hi";
str[0] = 'B'; // ❌ Undefined Behavior
6. String as Pointers vs Arrays
char str1[] = "Hello"; // Stored in stack, modifiable
char *str2 = "Hello"; // Stored in read-only memory, not modifiable
7. String with Dynamic Memory
char *str = (char *)malloc(20 * sizeof(char));
strcpy(str, "Dynamic");
Always remember to free(str); after use.
8. String Example Program
#include <stdio.h>
#include <string.h>
int main() {

37 | P a g e
 char str1[20] = "Hello";
char str2[20] = "World";
strcat(str1, str2);
printf("Concatenated: %s\n", str1);
printf("Length: %lu\n", strlen(str1));
return 0;
}

Taking String input with space in C (4 Different Methods)

We can take string input in C using scanf("%s", str). But, it accepts string only until it finds the first
space.
There are 4 methods by which the C program accepts a string with space in the form of user input.
Let us have a character array (string) named str[]. So, we have declared a variable as char str[20].
Method 1 : Using gets
Syntax : char *gets(char *str)
#include <stdio.h>
int main()
{
char str[20];
gets(str);
printf("%s", str);
return 0;
}
Note : gets() has been removed from c11. So it might give you a warning when implemented.
We see here that it doesn't bother about the size of the array. So, there is a chance of Buffer Overflow.
Method 2 : To overcome the above limitation, we can use fgets as :
Syntax : char *fgets(char *str, int size, FILE *stream)
Example : fgets(str, 20, stdin); as here, 20 is MAX_LIMIT according to declaration.
#include <stdio.h>
#define MAX_LIMIT 20
int main()
{
char str[MAX_LIMIT];
fgets(str, MAX_LIMIT, stdin);
printf("%s", str);
return 0;
}

38 | P a g e
Method 3 : Using %[^\n]%*c inside scanf
Example : scanf("%[^\n]%*c", str);
#include <stdio.h>
int main()
{
char str[20];
scanf("%[^\n]%*c", str);
printf("%s", str);
return 0;
}
Explanation : Here, [] is the scanset character. ^\n tells to take input until newline doesn't get
encountered. Then, with this %*c, it reads newline character and here used * indicates that this
newline character is discarded.
Method 4 : Using %[^\n]s inside scanf.
Example : scanf("%[^\n]s", str);
#include <stdio.h>

int main() {
char str[100];
scanf("%[^\n]s",str);
printf("%s",str);
return 0;
}
Explanation : Here, [] is the scanset character. ^\n tells to take input until newline doesn't get
encountered. Here we used ^ (XOR -Operator ) which gives true until both characters are different.
Once the character is equal to New-line ('\n'), ^ (XOR Operator ) gives false to read the string. So we
use "%[^\n]s" instead of "%s". So to get a line of input with space we can go with scanf("%[^\
n]s",str);

Stack
1. What is a Stack?
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
 The last element added (pushed) is the first one removed (popped).
Real-life analogy: A stack of plates – you add or remove from the top only.
2. Basic Operations
Operation Description

push(x) Add an element x to the top

39 | P a g e
Operation Description

pop() Remove the top element

peek() View the top element (without removing)

isEmpty() Check if the stack is empty

isFull() Check if the stack is full (for fixed-size stacks)

3. Implementation Methods
Using Arrays (Static Stack)
 Fixed size
 Simple to implement
#define MAX 100
int stack[MAX];
int top = -1;
void push(int x) {
if (top == MAX - 1) printf("Overflow");
else stack[++top] = x;
}
int pop() {
if (top == -1) printf("Underflow");
else return stack[top--];
}
Using Linked List (Dynamic Stack)
 No size limitation
 Each node points to the next
struct Node {
int data;
struct Node* next;
};
void push(struct Node** top, int x);
int pop(struct Node** top);

Stack Applications
1. Expression Evaluation & Conversion
o Infix → Postfix/Prefix
o Evaluate Postfix expressions

40 | P a g e
 2. Function Call Management
o Recursive function calls (call stack)
3. Undo Mechanism
o Editors (undo, redo)
4. Backtracking
o Solving mazes, puzzles
5. Syntax Parsing
o Compilers
6. Parentheses Matching
o Validating expressions
5. Common Stack Problems
Problem Concept Used

Balanced Parentheses Stack push/pop

Reverse a String Push all chars

Evaluate Postfix Expression Stack operands

Next Greater Element Monotonic Stack

Implement Stack using Queues Queues + logic

Implement Two Stacks in One Array Dual pointers

Design a Min Stack (getMin in O(1)) Extra stack

6. Complexity
Operation Time Complexity

Push O(1)

Pop O(1)

Peek O(1)

Stack Using Dynamic Arrays in C

1. Concept Overview
In a static array, the size of the stack is fixed.
In a dynamic array-based stack, we allocate memory during runtime and resize it (using malloc,
realloc) as needed.
Benefits:
 Efficient memory usage
 Flexible size (no overflow unless memory is full)
Key Functions for Dynamic Memory

41 | P a g e
  malloc() – Allocates memory
 realloc() – Reallocates/resizes existing memory
 free() – Frees memory
2. Structure of Dynamic Stack
typedef struct {
int *arr; // dynamically allocated array
int top; // index of top element
int capacity; // current allocated size
} Stack;
3. Dynamic Stack Operations
Operation Explanation

createStack(n) Initializes a stack of size n using malloc

push(x) Adds element x. If full, doubles size using realloc

pop() Removes top element, optional shrink

peek() Returns top element

isEmpty() Checks if top == -1

freeStack() Frees memory

4. C Program: Stack Using Dynamic Array

#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *arr;
int top;
int capacity;
} Stack;
// Create stack
void createStack(Stack *s, int size) {
s->capacity = size;
s->top = -1;
s->arr = (int *)malloc(s->capacity * sizeof(int));
}
// Push operation with resizing

42 | P a g e
void push(Stack *s, int value) {
if (s->top == s->capacity - 1) {
s->capacity *= 2;
s->arr = (int *)realloc(s->arr, s->capacity * sizeof(int));
printf("Stack resized to %d\n", s->capacity);
}
s->arr[++s->top] = value;
printf("Pushed: %d\n", value);
}
// Pop operation
int pop(Stack *s) {
if (s->top == -1) {
printf("Stack Underflow!\n");
return -1;
}
return s->arr[s->top--];
}
// Peek operation
int peek(Stack *s) {
if (s->top == -1) {
printf("Stack is Empty\n");
return -1;
}
return s->arr[s->top];
}
// Display
void display(Stack *s) {
if (s->top == -1) {
printf("Stack is Empty\n");
return;
}
printf("Stack: ");
for (int i = 0; i <= s->top; i++)
printf("%d ", s->arr[i]);

43 | P a g e
 printf("\n");
}
// Free memory
void freeStack(Stack *s) {
free(s->arr);
}
int main() {
Stack s;
createStack(&s, 2); // initial size 2
push(&s, 10);
push(&s, 20);
push(&s, 30); // triggers resize
display(&s);
printf("Popped: %d\n", pop(&s));
printf("Top Element: %d\n", peek(&s));
display(&s);
freeStack(&s); // important
return 0;
}
Output
Pushed: 10
Pushed: 20
Stack resized to 4
Pushed: 30
Stack: 10 20 30
Popped: 30
Top Element: 20
Stack: 10 20
Example 2:
#include <stdio.h>
#include <stdlib.h>

// Structure for Stack

typedef struct {

44 | P a g e
 int *arr; // Dynamic array
int top; // Index of top element
int capacity; // Current maximum capacity
} Stack;
// Function to create stack
Stack* createStack(int capacity) {
Stack *stack = (Stack*) malloc(sizeof(Stack));
stack->capacity = capacity;
stack->top = -1;
stack->arr = (int*) malloc(capacity * sizeof(int));
return stack;
}
// Check if stack is empty
int isEmpty(Stack *stack) {
return stack->top == -1;
}
// Check if stack is full
int isFull(Stack *stack) {
return stack->top == stack->capacity - 1;
}
// Resize stack (double capacity)
void resize(Stack *stack) {
stack->capacity *= 2;
stack->arr = (int*) realloc(stack->arr, stack->capacity * sizeof(int));
printf("Stack resized to capacity %d\n", stack->capacity);
}
// Push operation
void push(Stack *stack, int value) {
if (isFull(stack)) {
resize(stack);
}
stack->arr[++stack->top] = value;
printf("%d pushed\n", value);
}

45 | P a g e
// Pop operation
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack Underflow!\n");
return -1;
}
return stack->arr[stack->top--];
}
// Peek operation
int peek(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return -1;
}
return stack->arr[stack->top];
}
// Display stack
void display(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
printf("Stack elements: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->arr[i]);
}
printf("\n");
}
// Main function
int main() {
Stack *stack = createStack(2); // Start with capacity = 2

push(stack, 10);
push(stack, 20);

46 | P a g e
 push(stack, 30); // Will trigger resize
display(stack);
printf("Top element: %d\n", peek(stack));
printf("Popped: %d\n", pop(stack));
display(stack);
free(stack->arr);
free(stack);
return 0;
}
Output:
10 pushed
20 pushed
Stack resized to capacity 4
30 pushed
Stack elements: 10 20 30
Top element: 30
Popped: 30
Stack elements: 10 20
Advantages of Dynamic Stack
 Auto-resizing as elements grow.
 Prevents overflow common in static stacks.
 Optimizes memory when the size isn’t known at compile time.
Drawbacks
 Slightly slower than static stack due to realloc.
 realloc may fail if memory is fragmented.

Stack using Array:

#include <stdio.h>
#define MAX 5 // maximum size of stack
int stack[MAX], top = -1;
// Function to push element
void push(int x) {
if (top == MAX - 1) {
printf("Stack Overflow! Cannot push %d\n", x);

47 | P a g e
 } else {
stack[++top] = x;
printf("%d pushed into stack\n", x);
}
}
// Function to pop element
void pop() {
if (top == -1) {
printf("Stack Underflow! Nothing to pop\n");
} else {
printf("%d popped from stack\n", stack[top--]);
}
}
// Function to display stack
void display() {
if (top == -1) {
printf("Stack is empty\n");
} else {
printf("Stack elements: ");
for (int i = top; i >= 0; i--) {
printf("%d ", stack[i]);
}
printf("\n");
}
}
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}

48 | P a g e
Output:
10 pushed into stack
20 pushed into stack
30 pushed into stack
Stack elements: 30 20 10
30 popped from stack
Stack elements: 20 10

Stack using Linked List:

#include <stdio.h>
#include <stdlib.h>
// Define stack node
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL;
// Push operation
void push(int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->next = top;
top = newNode;
printf("%d pushed into stack\n", x);
}
// Pop operation
void pop() {
if (top == NULL) {
printf("Stack Underflow! Nothing to pop\n");
} else {
printf("%d popped from stack\n", top->data);
struct Node* temp = top;
top = top->next;
free(temp);

49 | P a g e
 }
}
// Display stack
void display() {
if (top == NULL) {
printf("Stack is empty\n");
} else {
printf("Stack elements: ");
struct Node* temp = top;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}
Output:
10 pushed into stack
20 pushed into stack
30 pushed into stack
Stack elements: 30 20 10
30 popped from stack
Stack elements: 20 10

50 | P a g e
 Queue:
1. What is a Queue?
A queue is a linear data structure that follows the FIFO (First In, First Out) principle.
 The first element added is the first one removed.
 Think of a queue at a ticket counter – first person to arrive is the first to be served.
2. Basic Operations
Operation Description

enqueue(x) Adds an element x to the rear

dequeue() Removes an element from the front

peek() Returns the front element

isEmpty() Checks if the queue is empty

isFull() Checks if the queue is full (array-based)

3. Types of Queues
Type Description
Linear Queue Basic FIFO queue using array or linked list
Circular Queue Last position connects back to the first to form a circle – better space
utilization
Double-Ended Queue Insertion and deletion possible at both ends
(Deque)
Priority Queue Elements are dequeued based on priority, not arrival time
Multiple Queues Two or more queues implemented in one array
4. Queue Implementations
Array-based Queue (Static)
#define MAX 100
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int x) {
if (rear == MAX - 1) printf("Overflow");
else {
if (front == -1) front = 0;
queue[++rear] = x;
}
}
int dequeue() {
if (front == -1 || front > rear) printf("Underflow");
else return queue[front++];

51 | P a g e
}
Linked List-based Queue (Dynamic)
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node *front, *rear;
};

Queue Implementation using Array(static array):

#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int x) {
if (rear == MAX - 1) {
printf("Queue Overflow!\n");
} else {
if (front == -1) front = 0;
queue[++rear] = x;
printf("%d enqueued\n", x);
}
}
void dequeue() {
if (front == -1 || front > rear) {
printf("Queue Underflow!\n");
} else {
printf("%d dequeued\n", queue[front++]);
}
}
void display() {
if (front == -1 || front > rear) {
printf("Queue is Empty\n");

52 | P a g e
 } else {
printf("Queue: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
return 0;
}
Output:
10 enqueued
20 enqueued
30 enqueued
Queue: 10 20 30
10 dequeued
Queue: 20 30

Queue Implementation using Linked List:

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node *front = NULL, *rear = NULL;

53 | P a g e
void enqueue(int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
printf("%d enqueued\n", x);
}
void dequeue() {
if (front == NULL) {
printf("Queue Underflow!\n");
return;
}
printf("%d dequeued\n", front->data);
struct Node* temp = front;
front = front->next;
if (front == NULL) rear = NULL;
free(temp);
}
void display() {
if (front == NULL) {
printf("Queue is Empty\n");
} else {
printf("Queue: ");
struct Node* temp = front;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");

54 | P a g e
 }
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
return 0;
}
Output:
10 enqueued
20 enqueued
30 enqueued
Queue: 10 20 30
10 dequeued
Queue: 20 30
Applications of Queue

CPU scheduling (Round Robin, FCFS)

Printer job scheduling
Breadth-First Search (BFS) in Graphs
Buffer management (keyboard buffer, IO buffer)
Order processing systems

6. Queue Operations Complexity

Operation Time Complexity

Enqueue O(1)

Dequeue O(1)

Peek O(1)
(For both array and linked list)

Circular Queue:
1. What is a Circular Queue?

A Circular Queue is a linear data structure that overcomes the limitations of a regular queue by
treating the array as circular.

55 | P a g e
  Front and Rear wrap around when reaching the end of the array.
 Efficient use of space (avoids shifting elements).
Think of it like a ring buffer — when you reach the end, you continue from the beginning.
2. Why Use Dynamic Arrays?
 In a static queue, size is fixed — can lead to overflow even if there's space.
 Dynamic Circular Queue resizes itself when full using realloc.
3. Circular Queue Concepts
Term Meaning

Front Index of first element

Rear Index of last element

Wrap-around (index + 1) % capacity for next pos

Full condition (rear + 1) % capacity == front

Empty condition front == -1

5. C Program: Circular Queue Using Dynamic Array

Example 1:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *arr;
int front, rear;
int capacity;
} CircularQueue;
// Create queue
void createQueue(CircularQueue *q, int size) {
q->capacity = size;
q->arr = (int *)malloc(q->capacity * sizeof(int));
q->front = q->rear = -1;
}
// Check if full
int isFull(CircularQueue *q) {
return (q->front == (q->rear + 1) % q->capacity);
}

56 | P a g e
// Check if empty
int isEmpty(CircularQueue *q) {
return (q->front == -1);
}
// Resize queue
void resizeQueue(CircularQueue *q) {
int newCapacity = q->capacity * 2;
int *newArr = (int *)malloc(newCapacity * sizeof(int));
int i = q->front, j = 0;
while (1) {
newArr[j++] = q->arr[i];
if (i == q->rear) break;
i = (i + 1) % q->capacity;
}
free(q->arr);
q->arr = newArr;
q->capacity = newCapacity;
q->front = 0;
q->rear = j - 1;
printf("Queue resized to %d\n", newCapacity);
}
// Enqueue
void enqueue(CircularQueue *q, int value) {
if (isFull(q)) {
resizeQueue(q);
}
if (isEmpty(q)) {
q->front = q->rear = 0;
} else {
q->rear = (q->rear + 1) % q->capacity;
}
q->arr[q->rear] = value;
printf("Enqueued: %d\n", value);
}

57 | P a g e
// Dequeue
int dequeue(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue Underflow!\n");
return -1;
}
int val = q->arr[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1; // queue becomes empty
} else {
q->front = (q->front + 1) % q->capacity;
}
return val;
}
// Display queue
void display(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is Empty\n");
return;
}
printf("Queue: ");
int i = q->front;
while (1) {
printf("%d ", q->arr[i]);
if (i == q->rear) break;
i = (i + 1) % q->capacity;
}
printf("\n");
}
// Free memory
void freeQueue(CircularQueue *q) {
free(q->arr);
}

58 | P a g e
// Main
int main() {
CircularQueue q;
createQueue(&q, 3); // initial capacity
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30); // triggers resize
enqueue(&q, 40);
display(&q);
printf("Dequeued: %d\n", dequeue(&q));
printf("Dequeued: %d\n", dequeue(&q));
display(&q);
enqueue(&q, 50);
enqueue(&q, 60);
display(&q);
freeQueue(&q);
return 0;
}
Output
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue resized to 6
Enqueued: 40
Queue: 10 20 30 40
Dequeued: 10
Dequeued: 20
Queue: 30 40
Enqueued: 50
Enqueued: 60
Queue: 30 40 50 60
Example 2:
#include <stdio.h>
#include <stdlib.h>

59 | P a g e
typedef struct {
int *arr; // dynamic array
int size; // capacity
int front; // front index
int rear; // rear index
int count; // number of elements
} CircularQueue;
// Function to create queue
CircularQueue* createQueue(int size) {
CircularQueue *q = (CircularQueue*) malloc(sizeof(CircularQueue));
q->size = size;
q->arr = (int*) malloc(sizeof(int) * size);
q->front = 0;
q->rear = -1;
q->count = 0;
return q;
}
// Check if queue is full
int isFull(CircularQueue *q) {
return q->count == q->size;
}
// Check if queue is empty
int isEmpty(CircularQueue *q) {
return q->count == 0;
}
// Enqueue operation
void enqueue(CircularQueue *q, int value) {
if (isFull(q)) {
printf("Queue Overflow! Cannot insert %d\n", value);
return;
}
q->rear = (q->rear + 1) % q->size; // circular increment
q->arr[q->rear] = value;

60 | P a g e
 q->count++;
printf("Inserted %d\n", value);
}
// Dequeue operation
int dequeue(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue Underflow!\n");
return -1;
}
int value = q->arr[q->front];
q->front = (q->front + 1) % q->size; // circular increment
q->count--;
return value;
}
// Peek front element
int peek(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
}
return q->arr[q->front];
}
// Display queue elements
void display(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return;
}
printf("Queue elements: ");
for (int i = 0; i < q->count; i++) {
int index = (q->front + i) % q->size;
printf("%d ", q->arr[index]);
}
printf("\n");

61 | P a g e
}
// Free memory
void freeQueue(CircularQueue *q) {
free(q->arr);
free(q);
}
// Main function
int main() {
int n;
printf("Enter size of queue: ");
scanf("%d", &n);
CircularQueue *q = createQueue(n);
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
display(q);
printf("Dequeued: %d\n", dequeue(q));
display(q);

enqueue(q, 40);
enqueue(q, 50);
display(q);

printf("Front element: %d\n", peek(q));

freeQueue(q);
return 0;
}
Output:
Enter size of queue: 3
Inserted 10
Inserted 20
Inserted 30
Queue elements: 10 20 30

62 | P a g e
Dequeued: 10
Queue elements: 20 30
Inserted 40
Inserted 50
Queue Overflow! Cannot insert 50
Queue elements: 20 30 40
Front element: 20

Advantages of Dynamic Circular Queue

 No overflow unless memory is exhausted
 Efficient memory reuse due to circular nature
 Resizable based on need

Limitations
 realloc can be costly
 Needs careful pointer/index management

Use Cases
 Streaming data (like audio/video buffers)
 CPU scheduling
 Producer-consumer problems
 Circular buffers in embedded systems

Real-World Applications
Queue Type Applications

Linear Queue Printer Spooler, Order Processing

Circular Queue CPU Scheduling, Memory Buffer

Deque Palindrome Checker, Browser Navigation

Priority Queue Emergency Rooms, OS Task Scheduling

Multiple Queues Multithreading, Multi-level Scheduling

1. Linear Queue

63 | P a g e
Concept:
 Elements are inserted at the rear and removed from the front.
 Once an element is dequeued, that space is not reused (in arrays).
Features:
 FIFO behavior.
 Easy to implement using arrays or linked lists.
Limitation:
 Inefficient space usage in static arrays.
Used in:
 Print queues
 Ticket booking systems

2. Circular Queue
Concept:
 Overcomes space inefficiency in linear queue.
 Rear and front wrap around to the beginning when they reach the end.
Features:
 Space reused efficiently.
 Implemented using arrays with modulo operation.
Limitation:
 Fixed size unless dynamically resized.
Used in:
 CPU scheduling
 Memory management (buffers, circular buffers)

3. Double-Ended Queue (Deque)

Concept:
 Insertion and deletion allowed from both front and rear.
Variants:
 Input-restricted deque: insertion only at one end.
 Output-restricted deque: deletion only at one end.
Features:
 Flexible access at both ends.
Used in:

64 | P a g e
  Task scheduling (both ends may prioritize tasks)
 Sliding window algorithms
 Palindrome checking

4. Priority Queue
Concept:
 Each element has a priority.
 Higher priority elements are dequeued first — regardless of arrival order.
Features:
 Can be implemented with arrays, linked lists, or heaps.
 Supports:
o Insertion in any order
o Deletion of highest-priority element
Used in:
 Dijkstra's algorithm
 Emergency rooms
 Job scheduling systems

5. Circular Deque
Concept:
 A combination of circular queue and deque.
 Allows insertion and deletion from both ends with wrap-around capability.
Features:
 Highly efficient in space
 Perfect for use cases where access at both ends is needed
Used in:
 Real-time simulations
 OS resource allocation

6. Multiple Queues
Concept:
 Two or more queues are implemented in a single data structure (often in a single array).
Features:
 Each queue maintains its own front and rear.

65 | P a g e
  Helps manage multiple user queues in limited memory.
Used in:
 Multi-level CPU scheduling
 Multiple user requests in real-time systems

7. Input-Restricted Deque
Concept:
 Insertion only at rear
 Deletion allowed from both ends

8. Output-Restricted Deque
Concept:
 Deletion only from front
 Insertion allowed at both ends

Quick Comparison Table

Insertions Allowed Deletions Allowed Wrap- Priority
Queue Type
From From around Support

Linear Queue Rear Front ❌ ❌

Circular Queue Rear (circular) Front (circular) ✅ ❌

Deque Front & Rear Front & Rear Optional ❌

Input-Restricted Rear Front & Rear Optional ❌

Output-
Front & Rear Front Optional ❌
Restricted

Priority Queue Any (by priority) Highest priority ❌ ✅

Multiple Queues Multiple ends Multiple ends Optional Optional

1. What is Expression Evaluation?

It is the process of computing the result of a mathematical expression.
Types of expressions:
Expression Type Example Order

Infix A+B Operators between operands

Prefix +AB Operator before operands

Postfix AB+ Operator after operands

66 | P a g e
Expression Type Example Order

2. Why Use Stacks for Evaluation?

Stacks are perfect for evaluating expressions because of their LIFO nature. They help:
 Track operands and operators.
 Handle parentheses in infix.
 Evaluate postfix/prefix expressions.

3. Evaluation Techniques
A. Postfix Evaluation (Reverse Polish Notation)
Steps:
1. Scan expression left to right.
2. If operand → push onto stack.
3. If operator → pop two operands, apply operator, push result back.
4. At end → Top of stack is the result.
Example:
Postfix: 5 3 + 2 *
Steps:
 Push 5 → Push 3 → + → (5+3=8) → Push 8
 Push 2 → * → (8*2=16)
Result = 16

B. Prefix Evaluation (Polish Notation)

Steps:
1. Scan expression right to left.
2. If operand → push onto stack.
3. If operator → pop two operands, apply operator, push result back.
4. At end → Top of stack is result.
Example:
Prefix: * + 5 3 2
Steps:
 Push 2 → Push 3 → Push 5 → + (5+3=8) → Push 8 → * (8*2=16)
Result = 16

4. C Program: Postfix Expression Evaluation

67 | P a g e
#include <stdio.h>
#include <ctype.h> // for isdigit
#include <stdlib.h>

#define MAX 100

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

// Push to stack
void push(int val) {
stack[++top] = val;
}

// Pop from stack

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

// Evaluate postfix
int evaluatePostfix(char *expr) {
int i;
for (i = 0; expr[i] != '\0'; i++) {
char ch = expr[i];

if (isdigit(ch)) {
push(ch - '0'); // Convert char digit to int
}
else {
int b = pop();
int a = pop();
switch (ch) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;

68 | P a g e
 case '/': push(a / b); break;
}
}
}
return pop();
}

int main() {
char expr[] = "53+2*"; // equivalent to (5 + 3) * 2
printf("Result = %d\n", evaluatePostfix(expr));
return 0;
}
Output:
Result = 16

5. Infix to Postfix Conversion

To evaluate infix directly, it’s easier to:
1. Convert to postfix using stack
2. Evaluate using postfix method

Applications
 Compilers and interpreters (e.g., JavaScript, Python)
 Calculator programs
 Symbolic math (Mathematica, Wolfram Alpha)
 Reverse Polish notation calculators (HP calculators)

Summary Table
Expression Notation Evaluation Direction Conversion Needed

Infix A+B Operator precedence Yes (to postfix)

Prefix +AB Right to Left No

Postfix AB+ Left to Right No

69 | P a g e
70 | P a g e