DSU Unit 2 Solved Question Bank

Q1 - What are the operations of the stack?

Ans –
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle,
meaning the last element added is the first to be removed. The primary operations of a
stack are:

1. Push Operation
Theory:
The push operation adds a new element to the top of the stack. Before adding, it checks if
the stack is full (to prevent overflow). If not, it increments the top pointer and inserts the
element.
Function Code:

void push(Stack* stack, int value) {

if (stack->top == MAX - 1) {
printf("Stack Overflow! Cannot push %d.\n", value);
return;
}
stack->arr[++stack->top] = value;
}

2. Pop Operation
Theory:
The pop operation removes the top element from the stack. Before removing, it checks if
the stack is empty (to avoid underflow). If not, it returns the top element and decrements the top
pointer.
Function Code:
int pop(Stack* stack) {
if (stack->top == -1) {
printf("Stack Underflow! Cannot pop.\n");
return -1;
}
return stack->arr[stack->top--];
}
3. Peek Operation
Theory:
The peek operation retrieves the top element of the stack without removing it. It checks if
the stack is empty. If it’s not empty, it returns the value at the top pointer.
Function Code:
int peek(Stack* stack) {
if (stack->top == -1) {
printf("Stack is empty! Cannot peek.\n");
return -1;
}
return stack->arr[stack->top];
}

4. IsEmpty Operation
Theory:
The isEmpty operation checks if the stack is empty by verifying if the top pointer equals
-1. It is often used before other operations like pop or peek to prevent underflow errors.
Function Code:
bool isEmpty(Stack* stack) {
return stack->top == -1;
}

5. IsFull Operation
Theory:
The isFull operation checks if the stack has reached its maximum capacity. It is
typically used before push to avoid overflow.
Function Code:
bool isFull(Stack* stack) {
return stack->top == MAX - 1;
}

Combine Example –
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

typedef struct {
int arr[MAX];
int top;
} Stack;
void initialize(Stack* stack) {
stack->top = -1;
}

bool isEmpty(Stack* stack) {

return stack->top == -1;
}

bool isFull(Stack* stack) {

return stack->top == MAX - 1;
}

void push(Stack* stack, int value) {

if (isFull(stack)) {
printf("Stack Overflow! Cannot push %d\n", value);
return;
}
stack->arr[++stack->top] = value;
printf("%d pushed onto the stack.\n", value);
}

int pop(Stack* stack) {

if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop.\n");
return -1;
}
return stack->arr[stack->top--];
}

int peek(Stack* stack) {

if (isEmpty(stack)) {
printf("Stack is empty! Cannot peek.\n");
return -1;
}
return stack->arr[stack->top];
}

int main() {
Stack stack;
initialize(&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));

return 0;
}

Code Output -

Q2 – What are the operations of a queue?

Ans -
A queue is a linear data structure that follows the First In, First Out (FIFO) principle,
meaning the element inserted first is the first to be removed. Here are the primary
operations of a queue:
1. Enqueue Operation
Theory:
The enqueue operation adds an element to the rear of the queue. It first checks if the
queue is full to avoid overflow. In a circular queue, the rear pointer wraps around when it
reaches the maximum capacity.
Function Code:
void enqueue(int queue[], int* rear, int* front, int value, int size) {
if ((*rear + 1) % size == *front) {
printf("Queue Overflow! Cannot enqueue %d.\n", value);
return;
}
if (*front == -1) *front = 0;
*rear = (*rear + 1) % size;
queue[*rear] = value;
}

2. Dequeue Operation
Theory:
The dequeue operation removes and returns the element at the front of the queue. It
checks if the queue is empty before removing. In a circular queue, the front pointer wraps around
when it reaches the maximum capacity.

Function Code:
int dequeue(int queue[], int* rear, int* front, int size) {
if (*front == -1) {
printf("Queue Underflow! Cannot dequeue.\n");
return -1;
}
int value = queue[*front];
if (*front == *rear) {
*front = -1;
*rear = -1;
} else {
*front = (*front + 1) % size;
}
return value;
}

3. Peek (Front) Operation

Theory:
The peek operation retrieves the element at the front without removing it. It checks if the
queue is empty before accessing the front element.

Function Code:
int peek(int queue[], int* front) {
if (*front == -1) {
printf("Queue is empty! Cannot peek.\n");
return -1;
}
return queue[*front];
}

4. IsEmpty Operation
Theory:
The isEmpty operation checks if the queue has no elements by verifying if the front
pointer is -1.
Function Code:
bool isEmpty(int* front) {
return *front == -1;
}

5. IsFull Operation
Theory:
The isFull operation checks if the queue is full by comparing the rear pointer and front
pointer in a circular manner.

Function Code:
bool isFull(int* rear, int* front, int size) {
return (*rear + 1) % size == *front;
}

Combine Example –
#include <stdio.h>
#include <stdbool.h>
#define SIZE 5
typedef struct {
int arr[SIZE];
int front;
int rear;
} Queue;
void initialize(Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
bool isEmpty(Queue* queue) {
return queue->front == -1;
}
bool isFull(Queue* queue) {
return (queue->rear + 1) % SIZE == queue->front;
}
void enqueue(Queue* queue, int value) {
if (isFull(queue)) {
printf("Queue Overflow! Cannot enqueue %d.\n", value);
return;
}
if (isEmpty(queue)) queue->front = 0;
queue->rear = (queue->rear + 1) % SIZE;
queue->arr[queue->rear] = value;
printf("%d enqueued to the queue.\n", value);
}
int dequeue(Queue* queue) {
if (isEmpty(queue)) {
printf("Queue Underflow! Cannot dequeue.\n");
return -1;
}
int value = queue->arr[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front = (queue->front + 1) % SIZE;
}
return value;
}
int peek(Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty! Cannot peek.\n");
return -1;
}
return queue->arr[queue->front];
}
int main() {
Queue queue;
initialize(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
enqueue(&queue, 50);
printf("Front element is: %d\n", peek(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
printf("Dequeued element: %d\n", dequeue(&queue));
enqueue(&queue, 60);
printf("Front element is: %d\n", peek(&queue));
while (!isEmpty(&queue)) {
printf("Dequeued element: %d\n", dequeue(&queue));
}
dequeue(&queue);
return 0;
}

Code Output –

Q3- What are the types of queue?

Ans –
There are several types of queues, each with different characteristics and usage
scenarios. The most common types are:
1. Linear Queue
Theory:
A linear queue is the simplest form of a queue where elements are added to the rear and
removed from the front, following the First In, First Out (FIFO) principle. This means that the
element added first is the one that is removed first.
• Operations:
o Enqueue: Adds an element to the rear of the queue.
o Dequeue: Removes an element from the front of the queue.
o Peek: Retrieves the front element without removing it.
o IsEmpty: Checks if the queue is empty.
o IsFull: Checks if the queue is full.
• Limitations:
In a linear queue, once the rear pointer reaches the end of the array, it cannot accept new
elements even if there is space available at the front. This happens because the queue
operates linearly and doesn't reuse the empty space. This leads to inefficient use of
memory.
2. Circular Queue
Theory:
A circular queue is a more efficient version of the linear queue. In a circular queue, the rear
pointer wraps around to the beginning of the queue once it reaches the end of the array. This
allows for better memory usage by reusing empty spaces when elements are dequeued from the
front.
• Operations:
o Enqueue: Adds an element to the rear of the queue (using circular wrapping).
o Dequeue: Removes an element from the front of the queue.
o Peek: Retrieves the front element without removing it.
o IsEmpty: Checks if the queue is empty.
o IsFull: Checks if the queue is full, taking into account the circular nature.
• Key Feature:
The primary advantage of a circular queue is that once the rear pointer reaches the last
index of the array, it will move back to the first index, thus utilizing all the available
space in the array.
3. Priority Queue
Theory:
A priority queue is a type of queue where each element has an associated priority. Elements
are dequeued based on their priority, not on their order of insertion. In other words, the highest
(or lowest) priority element will be dequeued first, regardless of when it was enqueued.
• Operations:
o Enqueue: Adds an element with a given priority.
o Dequeue: Removes the element with the highest priority.
o Peek: Retrieves the element with the highest priority.
o IsEmpty: Checks if the queue is empty.
• Key Feature:
In a priority queue, the order in which elements are dequeued depends on their priority.
In many cases, the queue is implemented using a heap (binary heap), which ensures that
the highest (or lowest) priority element is always at the front.
• Types:
o Max Priority Queue: The element with the highest priority is dequeued first.
o Min Priority Queue: The element with the lowest priority is dequeued first.
4. Double-Ended Queue (Deque)
Theory:
A deque (pronounced "deck") is a double-ended queue where elements can be inserted or
removed from both the front and the rear of the queue. This allows a deque to function as both a
stack (LIFO) and a queue (FIFO).
• Operations:
o InsertFront: Adds an element to the front of the queue.
o InsertRear: Adds an element to the rear of the queue.
o DeleteFront: Removes an element from the front of the queue.
o DeleteRear: Removes an element from the rear of the queue.
o PeekFront: Retrieves the front element.
o PeekRear: Retrieves the rear element.
• Key Feature:
The main advantage of a deque is its flexibility in allowing both ends to be used for
insertion and deletion, which makes it more versatile than a regular queue or stack.
5. Circular Double-Ended Queue (CDeque)
Theory:
A circular double-ended queue (CDeque) combines the features of both a circular queue and a
deque. It allows both the front and rear pointers to wrap around and efficiently use all available
space, while supporting operations at both ends of the queue.
• Operations:
o InsertFront: Adds an element to the front.
o InsertRear: Adds an element to the rear.
o DeleteFront: Removes an element from the front.
o DeleteRear: Removes an element from the rear.
o PeekFront: Retrieves the front element.
o PeekRear: Retrieves the rear element.
o IsFull: Checks if the queue is full.
o IsEmpty: Checks if the queue is empty.
• Key Feature:
Like a circular queue, the CDeque has circular pointers for efficient memory utilization.
It also supports deque operations at both ends, giving it the flexibility of a deque with the
memory efficiency of a circular queue.

Q4 - Define Stack. What are the Applications of stack?

Ans –
Stack Definition:
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle,
meaning that the last element added to the stack is the first one to be removed. It can be
visualized as a collection of elements stacked on top of one another, where operations are
performed at only one end, known as the top.

Key Operations of Stack:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the element from the top of the stack.
3. Peek (Top): Returns the top element of the stack without removing it.
4. IsEmpty: Checks whether the stack is empty.
5. IsFull: Checks whether the stack is full (in case of a fixed-size stack).

Applications of Stack:
Stacks are widely used in various applications because of their LIFO (Last In, First Out) nature.
Here are some of the key applications:
1. Function Calls (Recursion):
• Description:
Stacks are essential in managing function calls in a program. When a function is
called, its state (such as local variables, return address, etc.) is saved onto the
stack. When the function execution is complete, the state is popped from the
stack, and the control returns to the calling function. This is known as the call
stack.
• Example:
Recursive function calls use the stack to maintain the state and return values at
each level.
2. Web Browser History:
• Description:
Web browsers use stacks to store the history of pages visited. When the user
clicks the back button, the browser pops the most recent URL from the stack and
navigates back to that page.
• Example:
The "back" and "forward" buttons in web browsers use a stack to manage
navigation history.
3. Memory Management:
• Description:
Stacks play a role in memory management in languages like C and C++. The call
stack stores the function calls and local variables. When a function returns, the
memory allocated for local variables is released automatically.
• Example:
Stack frames are created when functions are called, and they are destroyed when
functions return.

Q5 - Write the code to insert a element onto a queue

Ans –
Program Code
#include <stdio.h>
#include <stdbool.h>
#define SIZE 5

typedef struct {
int arr[SIZE];
int front;
int rear;
} Queue;

void initialize(Queue* queue) {

queue->front = -1;
queue->rear = -1;
}

bool isFull(Queue* queue) {

return queue->rear == SIZE - 1;
}

bool isEmpty(Queue* queue) {

return queue->front == -1;
}

void enqueue(Queue* queue, int value) {

if (isFull(queue)) {
printf("Queue Overflow! Cannot enqueue %d.\n", value);
return;
}
if (isEmpty(queue)) queue->front = 0;
queue->rear++;
queue->arr[queue->rear] = value;
printf("%d enqueued to the queue.\n", value);
}

int main() {
Queue queue;
initialize(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
enqueue(&queue, 50);
enqueue(&queue, 60);
return 0;
}

Program Output –
Q6 - What are the postfix and prefix forms of the expression? A+B*(C-D)/(P-R)
Ans – ( IF YOU GOT THE ANS THEN SEND ME TOO )

Expression Result
Infix A+B×(C−D)/(P−R)
Postfix ABCD−∗PR−/+
Prefix +A/∗B−CD−PR

Q7 - What are the Types of Recursion? Explain all of them?

Ans –
Types of Recursion
Recursion is a process where a function calls itself to solve a problem. There are various
types of recursion based on the structure of the recursive calls. Below are the main types of
recursion with detailed explanations:

1. Direct Recursion
Definition:
In direct recursion, a function calls itself directly within its body to solve a smaller instance of
the same problem.
• Characteristics:
o The function explicitly invokes itself.
o A base condition is used to terminate the recursion.
• Example:
Calculating the factorial of a number.
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}

2. Indirect Recursion
Definition:
In indirect recursion, a function calls another function, which in turn calls the original function,
creating a loop of function calls.
• Characteristics:
o Requires at least two functions.
o The sequence of function calls forms a cycle.
• Example:
Two functions indirectly calling each other.
void functionA(int n) {
if (n > 0) {
printf("%d ", n);
functionB(n - 1);
}
}
void functionB(int n) {
if (n > 0) {
printf("%d ", n);
functionA(n / 2);
}
}

3. Tail Recursion
Definition:
In tail recursion, the recursive call is the last operation performed by the function before it
returns.
• Characteristics:
o Optimized by compilers to reduce memory usage (tail call optimization).
o Eliminates the need for maintaining a call stack for intermediate computations.
• Example:
Calculating the factorial of a number using tail recursion.
int factorialTail(int n, int result) {
if (n == 0) return result;
return factorialTail(n - 1, result * n);
}

4. Non-Tail Recursion
Definition:
In non-tail recursion, the recursive call is not the last operation in the function. Some operations
remain to be performed after the recursive call.
• Characteristics:
o Requires the call stack to keep track of intermediate states.
o Not optimized by compilers for tail call optimization.
• Example:
Calculating the Fibonacci sequence.
int fibonacci(int n) {
if (n == 0) return 0; // Base case
if (n == 1) return 1; // Base case
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive call, followed by
addition
}
Q8 - Evaluation of a postfix expression using a stack 653+9*+
Ans –
Step-by-Step Evaluation Table

Step Input Stack Operation

1 6 6 Push 6
2 5 6, 5 Push 5
3 3 6, 5, 3 Push 3
4 + 6, 8 5+3=8
5 9 6, 8, 9 Push 9
6 * 6, 72 8 * 9 = 72
7 + 78 6 + 72 = 78

Q9 - Write an algorithm for Push and Pop operations on Stack.

Ans –
Algorithm for Push and Pop Operations on Stack

Push Operation
The Push operation inserts an element onto the top of the stack.
Algorithm:
➢ Where :
• The stack S (a container that holds elements).
• An integer x to be pushed onto the stack.
➢ Steps:
• Check for Stack Overflow: If top == MAX - 1 (stack is full), return an Overflow
error.
• Push the element: Increase the top by 1 (to move the index to the next available
position).
• Assign the value of x to S[top] (add the element at the new position).
• End.

Pop Operation
Algorithm:
➢ Where:
• The stack S (a container holding elements).
• The Pointer of Stack top
➢ Steps:
• Check for Stack Underflow: If top == -1 (stack is empty), return an Underflow
error.
• Pop the element: Retrieve the value at S[top] (the element to be removed).
• Store this value in a variable, element.
• Decrease the top by 1 (to move the index down and remove the element).
• Return the value element (the popped element).
• End.

Q10 - Convert the following expression from infix to postfix A*(B+C)/D-G

Ans -
Step-by-Step Conversion Process:
Step Input Stack Postfix Expression
1 A A
2 ∗ ∗ A
3 ( ∗( A
4 B ∗( AB
5 + ∗(+ AB
6 C ∗(+ ABC
7 ) ∗ ABC+
8 / ∗/ ABC+
9 D ∗/ ABC+D
10 − − ABC+D/∗
11 G ABC+D/∗G−

Thus, the postfix expression for A×(B+C)/D−G Is ABC+D/∗G−

Q11 - Describe Round robin technique in Queue?

Ans –
Round Robin Technique in Queue
The Round Robin (RR) technique is one of the simplest and most widely used CPU
scheduling algorithms in operating systems. It is used to assign CPU time to processes in a
cyclic order, where each process is allocated a fixed time slice or quantum. The Round Robin
technique ensures that every process gets an equal share of CPU time, making it a fair and
efficient method for process scheduling.
How Round Robin Works:
1. Queue-based Scheduling:
o Processes are maintained in a queue (typically a FIFO queue).
o The first process in the queue is allocated the CPU for a fixed time quantum (a
predefined time slice).
2. Time Quantum:
o Each process gets executed for a fixed time interval (the time quantum or time
slice), typically in the range of 10-100 milliseconds.
o After the process completes its time quantum (or when it voluntarily gives up the
CPU), it is moved to the back of the queue if it has not finished execution.
o If the process finishes before its time quantum expires, it is removed from the
queue, and the CPU is allocated to the next process in the queue.
3. Cyclic Nature:
o The CPU time is allocated to processes in a cyclic manner.
o After the last process in the queue is executed, the scheduler starts again from the
first process, giving each process another turn to execute.
4. Preemptive Scheduling:
o Round Robin is a preemptive scheduling technique. If a process does not finish
its execution within its time quantum, it is preempted and moved to the end of
the queue.
o The next process in the queue is then executed, and the cycle continues.

Advantages of Round Robin:

• Fairness: Every process gets an equal share of CPU time.
• Preemptive: It ensures that no single process can monopolize the CPU, making the
system responsive and fair to all processes.
• Simplicity: The Round Robin algorithm is simple and easy to implement.

Disadvantages of Round Robin:

• Overhead: Frequent context switching can lead to increased overhead, especially with
small time quantum values.
• Starvation of Short Processes: If the time quantum is too large, processes that are small
or very quick to finish may have to wait too long.
• Not Ideal for Interactive Systems: Round Robin is not always the best scheduling
algorithm for systems that require interactive performance (such as real-time systems or
systems with high-priority tasks).

Applications:
• Multitasking Operating Systems: Round Robin is widely used for process scheduling in
general-purpose operating systems like Linux, Windows, and macOS.
• Time-sharing Systems: It is effective for systems where multiple users are interacting
with the computer, and each user’s process needs a fair share of the CPU time.
Q12 - Define Queue, Circular Queue, Dequeue, Priority Queue?
Ans –
Queue
A queue is a linear data structure that follows the First In, First Out (FIFO) principle,
meaning the element that is inserted first will be the first one to be removed. It is similar to a
queue at a checkout counter, where customers are served in the order they arrive.
Basic Operations of a Queue:
• Enqueue: Add an element to the back of the queue.
• Dequeue: Remove an element from the front of the queue.
• Peek/Front: View the front element without removing it.
• IsEmpty: Check if the queue is empty.
• IsFull: Check if the queue is full (in case of a fixed-size queue).

Circular Queue
A circular queue is a type of queue in which the last position is connected back to the
first position, forming a circle. This overcomes the problem of wasted space in a regular queue
when elements are dequeued from the front but new elements are still added to the rear.
Key Characteristics:
• The queue is circular, meaning after reaching the last element, the next element is added
to the front if there is space.
• The front and rear pointers are used to track the positions of the elements in the queue.
• A circular queue makes better use of available space in a fixed-size queue.
Basic Operations:
• Enqueue: Add an element to the rear, wrapping around if necessary.
• Dequeue: Remove an element from the front, adjusting the pointers appropriately.
• IsFull: Check if the queue has no more space to add an element.
• IsEmpty: Check if the queue is empty (i.e., when the front equals the rear).

Deque (Double Ended Queue)

A deque (pronounced "deck") is a linear data structure that allows insertion and deletion
of elements from both ends (front and rear). It is more flexible than a standard queue because
you can perform operations at both ends.
Types of Deque:
• Front-end operations (Insert or remove elements from the front of the deque).
• Rear-end operations (Insert or remove elements from the rear of the deque).
Basic Operations:
• InsertFront: Add an element to the front of the deque.
• InsertRear: Add an element to the rear of the deque.
• DeleteFront: Remove an element from the front of the deque.
• DeleteRear: Remove an element from the rear of the deque.
• IsEmpty: Check if the deque is empty.
• IsFull: Check if the deque is full (in case of a fixed-size deque).
Use Cases:
• Deques are often used in scenarios where elements need to be processed from both ends,
like in palindrome checking, window-based algorithms, and task scheduling.
Priority Queue
A priority queue is a specialized type of queue where each element is associated with a
priority. Elements with higher priority are dequeued before elements with lower priority,
regardless of the order in which they were added to the queue.
Key Characteristics:
• Priority-based processing: Elements with higher priority are dequeued first, similar to
how important tasks might be processed before others.
• Heap Implementation: Most priority queues are implemented using a heap data
structure (min-heap or max-heap).
• Can have duplicate priorities: Multiple elements may share the same priority.
Basic Operations:
• Insert: Add an element to the priority queue with an associated priority.
• Remove: Remove the element with the highest priority.
• Peek: View the element with the highest priority without removing it.
• IsEmpty: Check if the priority queue is empty.
Types:
• Min-priority queue: The element with the smallest priority is dequeued first.
• Max-priority queue: The element with the largest priority is dequeued first.
Use Cases:
• Job scheduling: In operating systems where tasks need to be processed based on priority.

Q13 - What are enqueue and dequeue operations? Write the code for it?
Ans –
Enqueue and Dequeue Operations in Queue
In a queue, the enqueue and dequeue operations are used to add and remove elements,
respectively. A queue follows the FIFO (First In, First Out) principle, meaning the first
element added to the queue will be the first one to be removed.

Enqueue Operation
The enqueue operation is used to add an element to the rear (or back) of the queue.
The enqueue function checks if the queue is full by comparing rear to MAX - 1. If the
queue is not full, the element is added to the rear, and the rear pointer is incremented. If
the queue was empty, the front pointer is also set to 0.
Operation Code :
void enqueue(Queue* q, int value) {
if (q->rear == MAX - 1) {
printf("Queue Overflow! Cannot enqueue %d\n", value);
return;
}
if (q->front == -1) {
q->front = 0;
}
q->rear++;
q->arr[q->rear] = value;
printf("%d enqueued to the queue.\n", value);
}

Dequeue Operation
The dequeue operation removes and returns the element at the front of the queue.
The dequeue function checks if the queue is empty by checking if front = -1. If the
queue is not empty, it returns the element at the front and moves the front pointer
forward. If the queue becomes empty after the dequeue, both front and rear are reset to -
1.
Operation Code :
int dequeue(Queue* q) {
if (q->front == -1) {
printf("Queue Underflow! Cannot dequeue.\n");
return -1;
}
int dequeuedElement = q->arr[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front++;
}
return dequeuedElement;
}

Q14 - A circular queue has a size of 5 and has 3 elements 10,20 and 40 where F=2 and
R=4. After inserting 50 and 60, what is the value of F and R. Trying to insert 30 at this
stage what happens? Delete 2 elements from the queue and insert 70, 80 & 90. Show
the sequence of steps with necessary diagrams with the value of F & R.
Ans – ( Diagram Representation According to Conditions. Below Ans Is Not For Test Paper It
Just For Understanding ).

Initial State:
• Size of the circular queue = 5
• Elements in the queue = [10, 20, 40]
• Front (F) = 2
• Rear (R) = 4
The queue appears as follows:
Index 0 1 2 3 4
Value - - 10 20 40
Status Empty Empty Front Rear

Step 1: Insert 50 and 60

• Inserting 50:
o Rear (R) moves to (R + 1) % size = (4 + 1) % 5 = 0.
o Insert 50 at index 0.
• Inserting 60:
o Rear (R) moves to (R + 1) % size = (0 + 1) % 5 = 1.
o Insert 60 at index 1.
Updated queue:
Index 0 1 2 3 4
Value 50 60 10 20 40
Status Rear Front
• Front (F) = 2
• Rear (R) = 1

Step 2: Trying to Insert 30

The queue is full because the next position of the R pointer is equal to the F pointer.
• (R + 1) % size == F, i.e., (1 + 1) % 5 == 2.
• Result: Insertion fails, and "Queue Overflow" is reported.

Step 3: Delete 2 elements from the queue

• Deleting the first element (10):
o Remove the element at F = 2.
o Move F to (F + 1) % size = (2 + 1) % 5 = 3.
• Deleting the second element (20):
o Remove the element at F = 3.
o Move F to (F + 1) % size = (3 + 1) % 5 = 4.
Updated queue:
Index 0 1 2 3 4
Value 50 60 - - 40
Status Rear Front
• Front (F) = 4
• Rear (R) = 1

Step 4: Insert 70, 80, and 90

• Inserting 70:
o Rear (R) moves to (R + 1) % size = (1 + 1) % 5 = 2.
o Insert 70 at index 2.
• Inserting 80:
o Rear (R) moves to (R + 1) % size = (2 + 1) % 5 = 3.
o Insert 80 at index 3.
• Inserting 90:
o Rear (R) moves to (R + 1) % size = (3 + 1) % 5 = 4.
o Insert 90 at index 4.
Updated queue:
Index 0 1 2 3 4
Value 50 60 70 80 90
Status Rear Front
• Front (F) = 4
• Rear (R) = 3

Summary:
1. After inserting 50 and 60:
o Front (F) = 2, Rear (R) = 1.
2. Trying to insert 30:
o Queue Overflow, as the queue is full.
3. After deleting 2 elements:
o Front (F) = 4, Rear (R) = 1.
4. After inserting 70, 80, and 90:
o Front (F) = 4, Rear (R) = 3.
This step-by-step explanation illustrates the state of the queue, handling both overflow and
normal operations.

Q15 - Write a routine for IsEmpty condition of queue.?

Ans –

The routine for checking the IsEmpty condition in a queue:

IsEmpty Function:
int isEmpty(Queue* q) {
return (q->front == -1);
}

• The isEmpty function checks whether the front pointer is set to -1, which indicates
that the queue is empty.
• When the queue is initialized, both front and rear are set to -1, so the queue is
empty.
• After all elements are dequeued, the front is reset to -1 to indicate an empty queue.
Example of Usage in Context
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
typedef struct {
int arr[MAX];
int front;
int rear;
} Queue;
int isEmpty(Queue* q) {
return (q->front == -1);
}
int main() {
Queue q = {{0}, -1, -1}; // Initialize an empty queue
if (isEmpty(&q)) {
printf("Queue is empty.\n");
} else {
printf("Queue is not empty.\n");
}
return 0;
}

Q16 - Difference Overflow and Underflow With diagram and code?

Ans –

Difference Between Overflow and Underflow

Aspect Overflow Underflow

Occurs when attempting to add an
Occurs when attempting to remove an
Definition element to a data structure that is
element from an empty data structure.
full.
Happens when the rear pointer of a Happens when the front pointer of a
Cause queue or the top of a stack exceeds queue or the top of a stack is already at
the maximum size. the lowest possible position.
In a stack, if top == MAX - 1. In a In a stack, if top == -1. In a queue, if front
Condition
queue, if (rear + 1) % size == front. == -1.
Prevents further additions to the Prevents further removals from the data
Result
data structure. structure.
Aspect Overflow Underflow
Adding an element to a full queue or Removing an element from an empty
Example
stack. queue or stack.

Code with Diagrams -

Stack Overflow and Underflow
Stack Code:
#include <stdio.h>
#define MAX 5
typedef struct {
int arr[MAX];
int top;
} Stack;
int isFull(Stack* s) {
return s->top == MAX - 1;
}
int isEmpty(Stack* s) {
return s->top == -1;
}
void push(Stack* s, int value) {
if (isFull(s)) {
printf("Stack Overflow! Cannot push %d.\n", value);
return;
}
s->arr[++s->top] = value;
printf("%d pushed onto the stack.\n", value);
}
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack Underflow! Cannot pop.\n");
return -1;
}
return s->arr[s->top--];
}

int main() {
Stack s = {{0}, -1}; // Initialize stack
pop(&s); // Underflow example
push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);
push(&s, 50);
push(&s, 60); // Overflow example
return 0;
}

Stack Diagram:

1. Initial State (Empty Stack):

Index 0 1 2 3 4
Value - - - - -
Top -1

2. After Push (10, 20, 30, 40, 50):

Index 0 1 2 3 4
Value 10 20 30 40 50
Top 4

3. After Push (60): Overflow occurs as top = MAX - 1.

4. Underflow: Occurs when trying to pop from the initial empty stack.

Queue Overflow and Underflow

Queue Code:

#include <stdio.h>
#define MAX 5
typedef struct {
int arr[MAX];
int front, rear;
} Queue;
int isFull(Queue* q) {
return (q->rear + 1) % MAX == q->front;
}
int isEmpty(Queue* q) {
return q->front == -1;
}
void enqueue(Queue* q, int value) {
if (isFull(q)) {
printf("Queue Overflow! Cannot enqueue %d.\n", value);
return;
}
if (q->front == -1) {
q->front = 0;
}
q->rear = (q->rear + 1) % MAX;
q->arr[q->rear] = value;
printf("%d enqueued.\n", value);
}
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue Underflow! Cannot dequeue.\n");
return -1;
}
int dequeued = q->arr[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX;
}
return dequeued;
}
int main() {
Queue q = {{0}, -1, -1};
dequeue(&q); // Underflow example
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
enqueue(&q, 50);
enqueue(&q, 60); // Overflow example
return 0;
}

Queue Diagram:

1. Initial State (Empty Queue):

Index 0 1 2 3 4
Value - - - - -
Front -1
Rear -1
2. After Enqueue (10, 20, 30, 40, 50):

Index 0 1 2 3 4
Value 10 20 30 40 50
Front 0
Rear 4

3. After Enqueue (60): Overflow occurs because (rear + 1) % size == front.

4. Underflow: Occurs when trying to dequeue from the initial empty queue.