CEC 18CS652: Introduction to Data Structures and Algorithms

Table of contents
Module 2

Module-II:
Stacks: Introduction, Stack Operations, Stack Implementation using Arrays, Applications of
Stacks.
Queues: Introduction, Queue Operations, Queue Implementation using Arrays, Different
Types of Queues: Circular Queues, Double-Ended Queues, Priority Queues, Applications of
Queues.
Textbook 2: Ch. 6.1 to 6.3, Ch. 8.1 to 8.2.

Introduction
Stacks and Queues are linear data structures widely used in programming for organizing and manipulating data.They are
implemented using arrays or linked lists, depending on the requirements and constraints of the problem.
Stacks
A stack is a LIFO (Last In First Out — the element placed at last can be accessed at first) structure which can be
commonly found in many programming languages. This structure is named as “stack” because it resembles a real-
world stack — a stack of plates.

Stack operations
Given below are the 2 basic operations that can
be performed on a stack.
• Push: Insert an element on to the top of
the stack.
• Pop: Delete the topmost element and
return it.

Furthermore, the following additional functions

are provided for a stack in order to check its
status.
• Peek: Return the top element of the
stack without deleting it.
• isEmpty: Check if the stack is empty.
• isFull: Check if the stack is full.

Applications of stacks
• Expression Evaluation: Convert infix expressions to postfix or prefix and evaluate them.
• Backtracking: Used in algorithms like solving mazes or puzzles.
• Function Call Management: Used to implement function calls in recursion programming. The runtime stack stores
function calls, parameters, and return addresses during program execution.

1
 CEC 18CS652: Introduction to Data Structures and Algorithms

Insert/Push Operation
The push operation adds an element to the top of the stack.
Condition: Check if the stack is full (Overflow condition) before pushing.
Steps:
1. Increment the `top` index.
2. Insert the element at the position indicated by `top`.

if (top == maxSize - 1)
printf("Stack Overflow");
else {
top++;
stack[top] = value;
}

Delete/Pop Operation
The **pop operation removes the topmost element from the stack.
-Condition: Check if the stack is empty (Underflow condition) before popping.
-Steps:
1. Access the element at the `top` index.
2. Decrement the `top` index.
if (top == -1)
printf("Stack Underflow");
else {
value = stack[top];
top--;
}
Display
To display the elements of the stack:
1. Traverse the array from the `top` index to `0`.
2. Print each element.
for (i = top; i >= 0; i--)
printf("%d ", stack[i]);

Stack Implementation Using Arrays

#include <stdio.h>
#define MAX 100 // Maximum size of the stack
// Stack structure
typedef struct {
int arr[MAX];
int top;
} Stack;

// Function to push an element onto the stack

void push(Stack *stack, int value) {
if (stack->top == MAX - 1) { // Check if the stack is full
printf("Stack overflow! Unable to push %d.\n", value);
return;
}
stack->arr[++(stack->top)] = value;
printf("Pushed %d onto the stack.\n", value);
}

2
 CEC 18CS652: Introduction to Data Structures and Algorithms

// Function to pop an element from the stack

int pop(Stack *stack) {
if (stack->top == -1) { // Check if the stack is empty
printf("Stack underflow! No elements to pop.\n");
return -1; // Return -1 to indicate error
}
return stack->arr[(stack->top)--];
}

// Function to view the top element of the stack

int peek(Stack *stack) {
if (stack->top == -1) { // Check if the stack is empty
printf("Stack is empty. No top element.\n");
return -1; // Return -1 to indicate error
}
return stack->arr[stack->top];
}

int main() {
Stack stack;
stack.top = -1; // Initialize the stack manually
// Example operations on the stack
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("Top element is: %d\n", peek(&stack));
printf("Popped element: %d\n", pop(&stack));
printf("Popped element: %d\n", pop(&stack));
printf("Popped element: %d\n", pop(&stack));
printf("Popped element: %d\n", pop(&stack)); // Attempt to pop from an empty
stack
return 0;
}

Evaluating an Expression Based on Precedence Rules

In mathematical and programming contexts, operators have a hierarchy of precedence:
-Parentheses: First priority.
- Exponentiation (if supported, e.g., `^`): Right-to-left.
- Multiplication (`*`) and Division (`/`)**: Left-to-right.
- Addition (`+`) and Subtraction (`-`)**: Left-to-right.

Example:
For the expression `A + B * C ^ D - E`:
1. `C ^ D` (Exponentiation is evaluated first).
2. `B * (Result of C ^ D)` (Multiplication).
3. `A + (Result of B * C ^ D)` (Addition).
4. `(Result of A + ...) - E` (Subtraction).

3
 CEC 18CS652: Introduction to Data Structures and Algorithms

C Function for Stack and Input Precedence

int precedence(char operator, int isStack) {
if (operator == '^') return (isStack ? 4 : 3); // Exponentiation
if (operator == '*' || operator == '/') return 2; // Multiplication / Division
if (operator == '+' || operator == '-') return 1; // Addition / Subtraction
return 0; // For non-operators
}

Infix, Postfix, and Prefix Notation:

- Infix: Operators are placed between operands (e.g., `A + B`). It is intuitive for humans but requires parentheses and
precedence rules for evaluation.
- Postfix: Operators follow operands (e.g., `AB+`). No parentheses are needed, and it’s efficient for stack-based
computations in machines.
- Prefix: Operators precede operands (e.g., `+AB`). Like postfix, it eliminates parentheses and simplifies parsing.
Why They Are Needed:
Infix: Human-friendly for writing and understanding expressions.
Postfix/Prefix: Ideal for compilers and calculators as they are easier to evaluate programmatically, avoiding ambiguity
caused by operator precedence or parentheses.

Converting Between Different Expression Forms

Infix Expression:
The provided infix expression is
((A + (B - C) * D) ^ E + F)
a) Prefix Expression for `((A + (B - C) * D) ^ E + F)`:
1. Start from the innermost parenthesis: `(B - C)` → `-BC`.
2. Multiply: `-BC * D` → `*-BCD`.
3. Add: `A + (*-BCD)` → `+A*-BCD`.
4. Raise to `E`: `(+A*-BCD) ^ E` → `^+A*-BCDE`.
5. Add `F`: `( ^ + A * - BCD E + F)` → `+^+A*-BCDEF`.
Final Prefix: `+^+A*-BCDEF`
(b) Postfix Expression for `((A + (B - C) * D) ^ E + F)`:
1. Start from `(B - C)` → `BC-`.
2. Multiply: `BC- * D` → `BC-D*`.
3. Add: `A + (BC-D*)` → `ABC-D*+`.
4. Raise to `E`: `(ABC-D*+) ^ E` → `ABC-D*+E^`.
5. Add `F`: `(ABC-D*+E^ + F)` → `ABC-D*+E^F+`.
Final Postfix: `ABC-D*+E^F+`.

Infix Expression:
The provided infix expression is
`X ^ Y ^ Z - M + N + P * I / Q`
(a) Postfix Expression for `X ^ Y ^ Z - M + N + P * I / Q`:
1. Exponentiation: `X ^ Y ^ Z` → `XYZ^^`.
2. Subtract `M`: `XYZ^^ - M` → `XYZ^^M-`.
3. Add `N`: `XYZ^^M- + N` → `XYZ^^M-N+`.
4. Multiply and divide: `P * I / Q` → `PI*Q/`.
5. Add: `(Result of XYZ^^M-N+) + (PI*Q/)` → `XYZ^^M-N+PI*Q/+`.
Final Postfix**: `XYZ^^M-N+PI*Q/+`.
(b) Prefix Expression for** `X ^ Y ^ Z - M + N + P * I / Q`:
1. Exponentiation: `X ^ Y ^ Z` → `^X^YZ`.
2. Subtract `M`: `^X^YZ - M` → `-^X^YZM`.
3. Add `N`: `-^X^YZM + N` → `+ -^X^YZM N`.
4. Multiply and divide: `P * I / Q` → `/ * PIQ`.

4
 CEC 18CS652: Introduction to Data Structures and Algorithms

5. Add: `(+ - ^ X ^ Y Z M N) + (/ * P I Q)` → `+ + -^X^YZM N / * PIQ`.

Final Prefix**: `+ + -^X^YZM N / * PIQ`.

General Procedure for Conversion

- Infix to Postfix:
- Scan the infix expression left to right.
- Push operators onto a stack, respecting precedence and associativity rules.
- Append operands directly to the output.
- Pop operators when encountering `)`.

- Infix to Prefix:
- Reverse the infix expression.
- Apply the infix-to-postfix method on the reversed expression.
- Reverse the resulting postfix expression.

C Function to Convert Infix to Postfix

void infixToPostfix(char infix[], char postfix[]) {
Stack s = {{0}, -1};
int i = 0, j = 0;
while (infix[i] != '\0') {
char token = infix[i++];
if (isalnum(token)) {
postfix[j++] = token;
} else if (token == '(') {
push(&s, token);
} else if (token == ')') {
while (s.top != -1 && s.stack[s.top] != '(')
postfix[j++] = pop(&s);
pop(&s); // Remove '('
} else {
while (s.top != -1 && precedence(s.stack[s.top]) >= precedence(token))
postfix[j++] = pop(&s);
push(&s, token);
}
}
while (s.top != -1) {
postfix[j++] = pop(&s);
}
postfix[j] = '\0';
}

5
 CEC 18CS652: Introduction to Data Structures and Algorithms

C Program to Evaluate Postfix Expression

int evaluatePostfix(char postfix[]) {
Stack s = {{0}, -1};
int i = 0;
while (postfix[i] != '\0') {
char token = postfix[i++];
if (isdigit(token)) {
push(&s, token - '0');
} else {
int b = pop(&s);
int a = pop(&s);
switch (token) {
case '+': push(&s, a + b); break;
case '-': push(&s, a - b); break;
case '*': push(&s, a * b); break;
case '/': push(&s, a / b); break;
case '^': push(&s, a ^ b); break;
}
}
}
return pop(&s);
}

Additional Problems:
Convert the following infix to prefix : (A-B/C)*(A/K-L)
Convert the following infix to postfix : A+B*(C^D-E)^(F+G*H)-I
Convert the following postfix to prefix: ABC/-AK/L-*
Convert the following prefix to postfix: *-A/BC-/AKL

6
 CEC 18CS652: Introduction to Data Structures and Algorithms

Queues
Introduction

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One
end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-
First-Out methodology, i.e., the data item stored first will be accessed first.

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and Structures. For the sake of
simplicity, we shall implement queues using one-dimensional array.

More About Queues:

1. Unlike arrays, where insertion and deletion can happen at any end.
2. In Queues, insertion (Enqueue) and deletion (Dequeue) can happen at only one end each.
3. Insertion happens at the rear end and deletion happens at the front
4. Queues follow FIFO First in First out structure, i.e. the element added first (Enqueued) will go out of the
queue first(Dequeued)
5. Unlike stack, which follows, LIFO, last in first out, and stack where both insertion and deletion happens as
one end. For queue insertion(Enqueue) and deletion(Dequeue) happens at opposite ends.
Queue Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the
memory. Here we shall try to understand the basic operations associated with queues −
• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient. These are −
• peek() − Gets the element at the front of the queue without removing it.
• isfull() − Checks if the queue is full.
• isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the
queue we take help of rear pointer.
Representation of Queue
Queue as a data structure can be represented in two ways.
• Stack as an Array (Most popular)
• Stack as a struct (Popular)
• Stack as a Linked List.
Applications and uses for Queues
• Heavily used in almost all applications of the operating system, to schedule processes, moving them
in or out of process scheduler.
• FCFS, SJF etc
• Asynchronously i.e. when data resource may be the same but not received at the same rate.
• Anything that has to do with process and schedule, in the system or code.

7
 CEC 18CS652: Introduction to Data Structures and Algorithms

Linear Queues
.
Queue Implementation using Array
Before we implement actual operations, first follow the below steps to create an empty queue.
• Step 1 Include header files and define a constant 'SIZE' with specific value.
• Step 2 Declare user defined functions which are used in queue implementation.
• Step 3 Create 1 dimensional array with above defined SIZE (INT QUEUE[SIZE])
• Step 4 Define two int variables 'FRONT' & 'REAR' and initialize both with '-1'.
• Step 5 Then implement main method by using suitable function calls to perform operation selected by the
user on queue.

enQueue(value) - Inserting value into the queue

Step 1: IF REAR = MAX – 1, Write OVERFLOW,
Step 2: IF FRONT = -1 and REAR = -1, SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
Step 3: Set QUEUE[REAR] = NUM

deQueue() - Deleting a value from the Queue

Step 1: IF FRONT = -1 or FRONT > REAR, Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
Step 2: EXIT

display () - Displays the elements of a Queue

Step 1: IF (FRONT == REAR), display "Queue is EMPTY!!!"
ELSE
SET i = FRONT + 1
Step 2: REPEAT TILL REAR (I <= REAR)
DISPLAY 'QUEUE[i]'
i=i++

Implementation
#include<stdio.h>
#define SIZE 10
void enQueue(int);
void deQueue();
void display();
int queue[SIZE], front = -1, rear = -1;
void main(){
int value, choice;
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);

8
 CEC 18CS652: Introduction to Data Structures and Algorithms

switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}
void deQueue(){
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",queue[i]); } }

Limitations of This Implementation

Consider a queue, with size 5. We have entered 5 elements but have later deleted first 2 elements. Now there is a
problem. We have free space but, space won’t be used as we can’t traverse again. This problem

9
 CEC 18CS652: Introduction to Data Structures and Algorithms

What is Circular Queue?

A circular queue is a linear data structure in which the operations are
performed based on FIFO (First In First Out) principle and the last position is
connected back to the first position to make a circle.
Graphical representation of a circular queue is as given.

Circular Queue Implementation using Array

Implement a circular queue data structure using an array, we first perform

the following steps before we implement actual operations.
• Step 1 - Include all the header files which are used in the program
and define a constant 'MAX' with specific value.
• Step 2 - Declare all user defined functions used in circular queue
implementation.
• Step 3 - Create a one dimensional array with above defined SIZE (int cQueue[MAX])
• Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1, rear = -1)
• Step 5 - Implement main method by displaying menu of operations list and make suitable function calls to perform
operation selected by the user on circular queue.

enQueue(value) - Inserting value into the Circular Queue

Step 1: IF (REAR+1)%MAX = FRONT
Write " OVERFLOW "
Goto step 4
[End OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT

deQueue() - Deleting a value from the Circular Queue

Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]
Step 4: EXIT

10
 CEC 18CS652: Introduction to Data Structures and Algorithms

display() - Displays the elements of a Circular Queue

Step 1: IF FRONT = REAR = -1
Write " EMPTY "
Goto Step 4
[END of IF]
Step 2: SET VAL = FRONT
Step 3: WHILE VAL <= REAR
PRINT QUEUE[VAL]
VAL=(VAL+1) % MAX
Step 4: EXIT

Implementation
#include <stdio.h>
# define max 6
int queue[max]; // array declaration
int front=-1;
int rear=-1;

int main(){
int choice=1,x; // variables declaration
while(choice<4 && choice!=0) // while loop
{
printf("\n Press 1: Insert an element");
printf("\nPress 2: Delete an element");
printf("\nPress 3: Display the element");
printf("\nEnter your choice");
scanf("%d", &choice);
switch(choice){
case 1:
printf("Enter the element which is to be inserted");
scanf("%d", &x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
display();
}
}
return 0;
}

// function to insert an element in a circular queue

void enqueue(int element){
if(front==-1 && rear==-1){ // condition to check queue is empty
front=0;
rear=0;
queue[rear]=element;}

11
 CEC 18CS652: Introduction to Data Structures and Algorithms

else if((rear+1)%max==front){ // condition to check queue is full

printf("Queue is overflow.."); }
else{
rear=(rear+1)%max; // rear is incremented
queue[rear]=element;} // assigning a value to the queue at the rear position.

// function to delete the element from the queue

int dequeue(){
if((front==-1) && (rear==-1)){ // condition to check queue is empty
printf("\nQueue is underflow..");}
else if(front==rear){
printf("\nThe dequeued element is %d", queue[front]);
front=-1;
rear=-1;}
else{
printf("\nThe dequeued element is %d", queue[front]);
front=(front+1)%max;}
}

// function to display the elements of a queue

void display(){
int i=front;
if(front==-1 && rear==-1){
printf("\n Queue is empty..");}
else{
printf("\nElements in a Queue are :");
while(i<=rear){
printf("%d,", queue[i]);
i=(i+1)%max;}
}
}

Priority Queues
A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has
some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the
elements in a priority queue will determine the order in which elements are removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either arranged in an
ascending or descending order.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following characteristics:
• Every element in a priority queue has some priority associated with it.
• An element with the higher priority will be deleted before the deletion of the lesser priority.
• If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.

12
 CEC 18CS652: Introduction to Data Structures and Algorithms

Types of Priority Queue

There are two types of priority queue:
• Ascending order priority queue: In ascending order priority queue, a lower priority number is given as a
higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in an ascending order like
1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as the highest priority in a priority queue.
• Descending order priority queue: In descending order priority queue, a higher priority number is given as a
higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in descending order like 5,
4, 3, 2, 1; therefore, the largest number, i.e., 5 is given as the highest priority in a priority queue

Representation of priority queue

Now, we will see how to represent the priority queue through a one-way list.
We will create the priority queue by using the list given below in which INFO list contains the data elements, PRN list
contains the priority numbers of each data element available in the INFO list, and LINK basically contains the address
of the next node.

13
CEC 18CS652: Introduction to Data Structures and Algorithms

Here is a simple code in C 2D matrix: C program to store temperature of two cities of a week and display it.

#include <stdio.h>
const int CITY = 2;
const int WEEK = 7;
int main(){
int temperature[CITY][WEEK];
// Using nested loop to store values in a 2d array
for (int i = 0; i < CITY; ++i){
for (int j = 0; j < WEEK; ++j){
printf("City %d, Day %d: ", i + 1, j + 1);
scanf("%d", &temperature[i][j]);
}
}
printf("\nDisplaying values: \n\n");
// Using nested loop to display vlues of a 2d array
for (int i = 0; i < CITY; ++i){
for (int j = 0; j < WEEK; ++j){
printf("City %d, Day %d = %d\n", i + 1, j + 1, temperature[i][j]);
}
}
return 0;}

Three-dimensional array:
C Program to store and print 12 values entered by the user
#include <stdio.h>
int main(){
int test[2][3][2];
printf("Enter 12 values: \n");
for (int i = 0; i < 2; ++i){
for (int j = 0; j < 3; ++j){
for (int k = 0; k < 2; ++k){
scanf("%d", &test[i][j][k]);
}
}
}
// Printing values with proper index.

14
CEC 18CS652: Introduction to Data Structures and Algorithms

printf("\nDisplaying values:\n");
for (int i = 0; i < 2; ++i){
for (int j = 0; j < 3; ++j){
for (int k = 0; k < 2; ++k){
printf("test[%d][%d][%d] = %d\n", i, j, k, test[i][j][k]);
}
}
}
return 0;}

Sum of two matrices:

C program to find the sum of two matrices of order 2*2

#include <stdio.h>
int main(){
float a[2][2], b[2][2], result[2][2];
// Taking input using nested for loop
printf("Enter elements of 1st matrix\n");
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j){
printf("Enter a%d%d: ", i + 1, j + 1);
scanf("%f", &a[i][j]);
}
// Taking input using nested for loop
printf("Enter elements of 2nd matrix\n");
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j){
printf("Enter b%d%d: ", i + 1, j + 1);
scanf("%f", &b[i][j]);
}
// adding corresponding elements of two arrays
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j){
result[i][j] = a[i][j] + b[i][j];
}

// Displaying the sum

printf("\nSum Of Matrix:");
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j){
printf("%.1f\t", result[i][j]);
if (j == 1)
printf("\n");
}
return 0;}

Matrix Subtraction 2 D (dimensional)

#include <stdio.h>
int main(){
int rowCount, columnCount, i, j;
int firstMatrix[10][10], secondMatrix[10][10], resultMatrix[10][10];

15
CEC 18CS652: Introduction to Data Structures and Algorithms

printf("Number of rows of matrices to be subtracted : ");

scanf("%d", &rowCount);
printf("Number of columns matrices to be subtracted : ");
scanf("%d", &columnCount);
printf("Elements of first matrix : \n");
for (i = 0; i < rowCount; i++)
for (j = 0; j < columnCount; j++)
scanf("%d", &firstMatrix[i][j]);
printf("Elements of second matrix : \n");
for (i = 0; i < rowCount; i++)
for (j = 0; j < columnCount; j++)
scanf("%d", &secondMatrix[i][j]);
printf("Difference of entered matrices : \n");
for (i = 0; i < rowCount; i++){
for (j = 0; j < columnCount; j++){
resultMatrix[i][j] = firstMatrix[i][j] - secondMatrix[i][j];
printf("%d\t",resultMatrix[i][j]);}
printf("\n");
}
return 0;}

Matrix multiplication in C language

#include <stdio.h>
// function to get matrix elements entered by the user
void getM (int matrix[][10], int row, int column) {
printf("\nEnter elements: \n");
for (int i = 0; i < row; ++i) {
for (int j = 0; j < column; ++j) {
printf("Enter a%d%d: ", i + 1, j + 1);
scanf("%d", &matrix[i][j]);
}
}
}
// function to multiply two matrices
void multiplyM (int first[][10], int second[][10],
int result[][10], int r1, int c1, int r2, int c2) {
// Initializing elements of matrix mult to 0.
for (int i = 0; i < r1; ++i) {
for (int j = 0; j < c2; ++j) {
result[i][j] = 0;
}
}
// Multiplying first and second matrices and storing it in result
for (int i = 0; i < r1; ++i) {
for (int j = 0; j < c2; ++j) {

16
CEC 18CS652: Introduction to Data Structures and Algorithms

for (int k = 0; k < c1; ++k) {

result[i][j] += first[i][k] * second[k][j];
}
}
}
}
// function to display the matrix
void displayM(int result[][10], int row, int column) {
printf("\nOutput Matrix:\n");
for (int i = 0; i < row; ++i) {
for (int j = 0; j < column; ++j) {
printf("%d ", result[i][j]);
if (j == column - 1)
printf("\n");
}
}
}
int main() {
int first[10][10], second[10][10], result[10][10], r1, c1, r2, c2;
printf("Enter rows and column for the first matrix: ");
scanf("%d %d", &r1, &c1);
printf("Enter rows and column for the second matrix: ");
scanf("%d %d", &r2, &c2);
// Taking input until
// 1st matrix columns is not equal to 2nd matrix row
while (c1 != r2) {
printf("Error! Enter rows and columns again.\n");
printf("Enter rows and columns for the first matrix: ");
scanf("%d%d", &r1, &c1);
printf("Enter rows and columns for the second matrix: ");
scanf("%d%d", &r2, &c2);
}
getM (first, r1, c1); // get elements of the first matrix
getM (second, r2, c2); // get elements of the second matrix
multiplyM (first, second, result, r1, c1, r2, c2); // multiply two matrices.
displayM(result, r1, c2);
return 0;}

Find Transpose of a Matrix

The transpose of a matrix is a new matrix that is obtained by exchanging the rows and columns. In
this program, the user is asked to enter the number of rows r and columns c. Their values should
be less than 10 in this program. Then, the user is asked to enter the elements of the matrix (of
order r*c).
#include <stdio.h>
int main() {
int a[10][10], transpose[10][10], r, c, i, j;
printf("Enter rows and columns: ");
scanf("%d %d", &r, &c);
// Assigning elements to the matrix
printf("\nEnter matrix elements:\n");
for (i = 0; i < r; ++i)

17
CEC 18CS652: Introduction to Data Structures and Algorithms

for (j = 0; j < c; ++j) {

printf("Enter element a%d%d: ", i + 1, j + 1);
scanf("%d", &a[i][j]);
}
// Displaying the matrix a[][]
printf("\nEntered matrix: \n");
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j) {
printf("%d ", a[i][j]);
if (j == c - 1)
printf("\n");
}
// Finding the transpose of matrix a
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j) {
transpose[j][i] = a[i][j];
}
// Displaying the transpose of matrix a
printf("\nTranspose of the matrix:\n");
for (i = 0; i < c; ++i)
for (j = 0; j < r; ++j) {
printf("%d ", transpose[i][j]);
if (j == r - 1)
printf("\n");
}
return 0;}

18