ASSIGNMENT - 2

Data structure using c

Name -Aman Jee

Sap id- 500130366

Course - BCA in Cloud and Security

Question 1
Advantage of Circular Queue over Ordinary Queue

ANS -

A normal linear queue follows the FIFO (First In First Out) principle. In a linear queue,
when elements are deleted from the front, the empty spaces created at the beginning
cannot be reused again. As a result, even if there is free space in the array, insertion
may not be possible when the rear reaches the last position. This situation is called
false overflow.

A circular queue overcomes this drawback by connecting the last position of the
queue back to the first position in a circular manner. When the rear reaches the
end of the array, it starts again from the beginning if free space is available.
Therefore, memory utilization becomes efficient and wastage of space is avoided.

Another advantage of circular queue is that insertion and deletion operations can
be performed continuously without shifting elements. It is widely used in CPU
scheduling, buffering, traffic systems, and keyboard input management because
of its efficient use of memory and faster operations.

Algorithm for Insertion in Circular Queue

Check whether the queue is full.
If full, display overflow message.
If queue is empty, set FRONT = REAR = 0.
Otherwise, set REAR = (REAR + 1) % SIZE.
Insert the element at REAR position.
 Algorithm for Deletion in Circular Queue
Check whether the queue is empty.
If empty, display underflow message.
Store the deleted element.
If FRONT = REAR, set FRONT = REAR = -1.
Otherwise, set FRONT = (FRONT + 1) % SIZE.
C Program for Circular Queue
#include<stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

void insert(int value)

{
if((rear + 1) % SIZE == front)
{
printf("Queue Overflow\n");
}
else
{
if(front == -1)
front = rear = 0;
else
rear = (rear + 1) % SIZE;

queue[rear] = value;
printf("%d inserted\n", value);
}
}

void delete()
{
if(front == -1)
{
printf("Queue Underflow\n");
}
else
{
printf("%d deleted\n", queue[front]);

if(front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
}
}

void display()
{
int i;

if(front == -1)
{
printf("Queue is empty\n");
}
else
{
printf("Queue elements are:\n");

i = front;

while(i != rear)
{
printf("%d ", queue[i]);
i = (i + 1) % SIZE;
}

printf("%d\n", queue[rear]);
}
}

int main()
{
insert(10);
insert(20);
insert(30);

display();

delete();

display();

return 0;
}
 Question 2
Applications of Stack and Evaluation of Postfix Expression
ANS -

A stack is a linear data structure that follows the LIFO (Last In First Out) principle.
The element inserted last is deleted first. Stacks are widely used in computer
science because they provide efficient insertion and deletion from one end called
TOP.
Stacks are used in function calling and recursion where function addresses are
stored in memory. They are also used in expression conversion and evaluation
such as infix to postfix conversion. Web browsers use stacks to implement
backward and forward navigation. Undo and redo operations in text editors also
use stack structure. Syntax checking in compilers and parenthesis matching are
additional important applications.

Algorithm for Postfix Evaluation

Scan the postfix expression from left to
right.
If operand occurs, push it into stack.
If operator occurs, pop two operands.
Perform the operation.
Push the result back into stack.
Repeat until expression ends.
Final value in stack is the answer.
Evaluation of Postfix Expression: ABC-D*+E5F*+

A + ((B - C) * D) + (E + (5 * F))
Stepwise evaluation:

Push A
Push B
Push C
Operator (-) → perform B - C
Push D
Operator (*) → multiply result
with D
Operator (+) → add A
Push E
Push 5
Push F
Operator (*) → 5 × F
Operator (+) → add with E
expression
Question 3
Breadth First Search and Depth First Search

ANS -
 Breadth First Search (BFS) and Depth First Search (DFS) are
important graph traversal algorithms used to visit all vertices of a
graph.
Breadth First Search explores vertices level by level. It first visits all
neighboring vertices before moving to the next level. BFS uses a
queue for traversal. It is useful in finding the shortest path in
unweighted graphs and in network broadcasting systems.
For example, if a graph starts from vertex A connected to B and C,
BFS first visits A, then B and C, and afterward their neighboring
vertices.
BFS Algorithm
Start from source vertex.
Mark it visited.
Insert it into queue.
Remove vertex from queue.
Visit all unvisited adjacent vertices.
Repeat until queue becomes empty.

Depth First Search works differently. It first

moves deeply along one path before
backtracking. DFS uses stack or recursion. It is
useful in maze solving, cycle detection, and
topological sorting.
For example, starting from A, DFS may visit A →
B → D completely before returning to another
branch.
 DFS Algorithm
Start from source vertex.
Mark it visited.
Visit one adjacent unvisited vertex recursively.
Continue until no unvisited vertex remains.
Backtrack and continue traversal.
The main difference between BFS and DFS is their
traversal approach. BFS explores level by level while
DFS explores depth wise. BFS generally requires more
memory because of queue storage, whereas DFS
requires less memory in many cases due to recursion or
stack usage.

Question 4
Insertion Sort and Selection Sort Algorithms

ANS -

Insertion Sort is a sorting technique in which elements are inserted into their
proper position one by one. It works similarly to arranging playing cards in hand.
At each step, the current element is compared with previous elements and placed
at the correct position.

Algorithm for Insertion Sort

Assume first element is sorted.
Take next element as key.
Compare key with previous elements.
Shift larger elements one position ahead.
Insert key at correct position.
Repeat for all elements.
 Algorithm for Selection Sort
Find smallest element in array.
Swap it with first position.
Find next smallest element.
Swap with next position.
Continue until array becomes sorted.

Insertion sort performs efficiently for small or partially sorted

data because fewer shifts are required. Selection sort
performs fewer swaps but always searches entire unsorted
part for minimum element. Therefore, insertion sort is
generally faster for practical small datasets while selection
sort is simpler and performs fixed comparisons.

Question 5(a)
Linked List and Different Types of Linked List
ANS -

A linked list is a dynamic linear data structure made up of nodes where each node contains
data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous
memory allocation. Memory is allocated dynamically during execution.
Linked lists are useful when frequent insertion and deletion operations are required because
elements can be modified without shifting other elements.
There are several types of linked lists.

A singly linked list contains one pointer that points to the next node. Traversal is possible only in forward
direction.
A doubly linked list contains two pointers. One points to the next node and the other points to the previous
node. Therefore, traversal can occur in both directions.
A circular linked list connects the last node back to the first node, forming a circle. This structure is useful in
circular scheduling systems.
A circular doubly linked list combines properties of both doubly and circular linked lists. Each node has two
links and the last node connects to the first node.
Question 5(b)
Doubly Linked List with Advantages and Disadvantages
ANS -

A doubly linked list is a linked structure where every

node contains data, previous pointer, and next
pointer. It allows traversal in both forward and
backward directions.
The major advantage of doubly linked list is easy
backward traversal. Deletion operation becomes
simpler because previous node information is directly
available. It is used in browser navigation, undo-redo
operations, and music playlist systems.
However, doubly linked lists require extra memory
because every node stores two pointers. The
implementation is also more complex compared to
singly linked lists.

Question 6(a)

Tree Data Structure and Applications

ANS -
A tree is a non-linear hierarchical data structure consisting of
nodes connected by edges. The topmost node is called root
node. Nodes connected below root are child nodes.
Trees are used in database indexing, file systems, decision
making, routing algorithms, and compiler design. They
provide fast searching and hierarchical organization of data.
A Binary Tree is a tree in which each node has at most two
children called left child and right child.

The level of a binary tree represents the position of nodes from

the root. Root exists at level 0 and its children at level 1.
A complete binary tree is a binary tree in which all levels are
completely filled except possibly the last level, and the last level
is filled from left to right.
Degree of a tree means the maximum number of children
possessed by any node in the tree.

Question 6(b)

Binary Search Tree Representation

ANS -

Elements:

100, 85, 45, 55, 110, 20, 70, 65

 100
/ \
85 110
/
45
/ \
20 55
\
70
/
65
Array Representation

Index : 0 1 2 3 4 5 6 7
Value :100 85 110 45 - - - 20
Linked Representation
Each node contains:

[Left Pointer | Data | Right Pointer]