Q1: Stack: implementation of Operation using Array
A stack is a fundamental data structure in computer science that follows the Last In, First Out
(LIFO) principle. In a stack, elements are added and removed from the same end, which is
called the "top" of the stack. The last element added to the stack is the first one to be
removed. This makes a stack conceptually similar to a stack of plates or books.
The main operations associated with a stack are:
Push: This operation adds an element to the top of the stack.
Pop: This operation removes the element from the top of the stack.
Peek or Top: This operation returns the element at the top of the stack without removing it.
Program for Stack implementation using Array
#include <stdio.h>
#define MAX_SIZE 100
// Structure to represent a stack
struct Stack {
int arr[MAX_SIZE];
int top;
};
// Function to initialize an empty stack
void initializeStack(struct Stack *stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack *stack) {
return (stack->top == -1);
}
// Function to check if the stack is full
int isFull(struct Stack *stack) {
return (stack->top == MAX_SIZE - 1);
}
// Function to push an element onto the stack
void push(struct Stack *stack, int value) {
if (isFull(stack)) {
printf("Stack overflow! Cannot push %d.\n", value);
} else {
stack->arr[++(stack->top)] = value;
printf("%d pushed onto the stack.\n", value);
}
}
// Function to pop an element from the stack
int pop(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack underflow! Cannot pop from an empty stack.\n");
return -1; // Assuming -1 as an invalid value
} else {
int poppedValue = stack->arr[(stack->top)--];
printf("%d popped from the stack.\n", poppedValue);
return poppedValue;
}
}
// Function to peek at the top element of the stack without removing it
int peek(struct Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty. Cannot peek.\n");
return -1; // Assuming -1 as an invalid value
} else {
int topValue = stack->arr[stack->top];
printf("Top element of the stack: %d\n", topValue);
return topValue;
}
}
int main() {
// Example usage of the stack functions
struct Stack myStack;
initializeStack(&myStack);
push(&myStack, 10);
push(&myStack, 20);
push(&myStack, 30);
peek(&myStack);
pop(&myStack);
peek(&myStack);
pop(&myStack);
pop(&myStack);
return 0;
}
Q2: Evaluate the Postfix expression: 3 4 * 2 5 * + using STACK
Input Stack
34*25*+ empty Push 3
4*25*+ 3 Push 4
*2 5 * + 43 Pop 3 and 4 from the stack and perform 3*4 = 12. Push 12 into the stack.
25*+ 12 Push 2
5*+ 2 12 Push 5
*+ 5 2 12 Pop 5 and 2 from the stack and perform 5*2 = 10. Push 10 into the stack.
+ 10 12 Pop 10 and 12 from the stack and perform 10+12 = 22. Push 22 into the stack.
The result of the above expression is 22.
Q3. Covert the given Infix expression to Postfix using STACK
K + L - M*N + (O^P) * W/U/V * T + Q
Input Stack Postfix Expression
Expression
K K
+ +
L + KL
- - K L+
M - K L+ M
* -* K L+ M
N -* KL+MN
+ + K L + M N*
K L + M N* -
( +( K L + M N *-
O +( KL+MN*-O
^ +(^ K L + M N* - O
P +(^ K L + M N* - O P
) + K L + M N* - O P ^
* +* K L + M N* - O P ^
W +* K L + M N* - O P ^ W
/ +/ K L + M N* - O P ^ W *
U +/ K L + M N* - O P ^W*U
/ +/ K L + M N* - O P ^W*U/
V +/ KL + MN*-OP^W*U/V
* +* KL+MN*-OP^W*U/V/
T +* KL+MN*-OP^W*U/V/T
+ + KL+MN*-OP^W*U/V/T*
KL+MN*-OP^W*U/V/T*+
Q + KL+MN*-OP^W*U/V/T*Q
KL+MN*-OP^W*U/V/T*+Q+
The final postfix expression of infix expression(K + L - M*N + (O^P) * W/U/V * T + Q) is
KL+MN*-OP^W*U/V/T*+Q+.
Q4. Explain Circular Queue, Implement a circular queue using arrays.
In a circular queue, insertion and deletion operations are performed to add elements to the
rear and remove elements from the front, respectively. The circular nature of the queue
allows efficient utilization of space, as the front and rear pointers wrap around to the
beginning of the queue when they reach the end.
Enqueue (Insertion):The enqueue operation involves adding an element to the rear of the
circular queue.
If the queue is empty (both front and rear pointers are -1), set both front and rear
pointers to 0.
Increment the rear pointer, taking care of the circular wrap-around if necessary.
Insert the new element at the position pointed to by the rear.
Dequeue (Deletion): The dequeue operation involves removing the element from the front of
the circular queue.
If the queue is empty (both front and rear pointers are -1), indicate that the queue is
empty.
Retrieve the element at the position pointed to by the front.
If the front and rear pointers are equal after dequeuing the last element, reset the
queue to an empty state. Otherwise, increment the front pointer, taking care of the
circular wrap-around if necessary.
Program to Implement a circular queue using Arrays
#include <stdio.h>
#define MAX_SIZE 5
struct CircularQueue {
int items[MAX_SIZE];
int front, rear;
};
// Queue Initialization
void initializeQueue(struct CircularQueue *queue) {
queue->front = -1;
queue->rear = -1;
}
// Queue overflow condition
int isFull(struct CircularQueue *queue) {
return (queue->front == (queue->rear + 1) % MAX_SIZE);
}
//Queue underflow condition
int isEmpty(struct CircularQueue *queue) {
return (queue->front == -1 && queue->rear == -1);
}
// Insertion operation
void enqueue(struct CircularQueue *queue, int value) {
if (isFull(queue)) {
printf("Queue is full. Cannot enqueue %d.\n", value);
} else {
if (isEmpty(queue)) {
queue->front = 0;
queue->rear = 0;
} else {
queue->rear = (queue->rear + 1) % MAX_SIZE;
}
queue->items[queue->rear] = value;
printf("%d enqueued to the queue.\n", value);
}
}
// Deletion operation
int dequeue(struct CircularQueue *queue) {
int dequeuedValue;
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue.\n");
return -1; // Assuming -1 as an invalid value
} else {
dequeuedValue = queue->items[queue->front];
if (queue->front == queue->rear) {
// Reset the queue to empty state after dequeueing the last element
initializeQueue(queue);
} else {
queue->front = (queue->front + 1) % MAX_SIZE;
}
printf("%d dequeued from the queue.\n", dequeuedValue);
return dequeuedValue;
}
}
int main() {
struct CircularQueue myQueue;
initializeQueue(&myQueue);
enqueue(&myQueue, 10);
enqueue(&myQueue, 20);
enqueue(&myQueue, 30);
dequeue(&myQueue);
dequeue(&myQueue);
enqueue(&myQueue, 40);
enqueue(&myQueue, 50);
return 0;
}
Q5. Write a short note on Priority Queue.
A priority queue is a data structure that stores elements with associated priorities and allows
for efficient retrieval of the element with the highest (or lowest) priority. Unlike a regular
queue or stack, elements in a priority queue are not necessarily processed in the order they
were inserted; instead, they are processed based on their priority.
Key characteristics of a priority queue:
Priority-Based Ordering:
Elements in a priority queue are associated with priorities. The element with the highest (or
lowest) priority is processed first.
No Strict Ordering of Elements:
Unlike queues or stacks, elements in a priority queue do not have a strict order based on
insertion time. The order is determined by the priority assigned to each element.
Basic Operations:
Basic operations of a priority queue include insertion (enqueue), deletion (dequeue), and
peeking (retrieving the element with the highest priority without removing it).
Implementation:
Priority queues can be implemented using various data structures, such as binary heaps,
Fibonacci heaps, or balanced search trees (like binary search trees or AVL trees). The choice
of implementation depends on the specific requirements regarding time and space complexity
for the operations.
Use Cases:
Priority queues are widely used in scenarios where elements need to be processed based on
their importance or urgency. Examples include task scheduling in operating systems, network
packet scheduling, and Dijkstra's algorithm for finding the shortest path in graph algorithms.
Max and Min Priority Queues:
Depending on the application, a priority queue can be implemented as a max priority queue
(highest priority element is processed first) or a min priority queue (lowest priority element is
processed first).
Q6. Explain the Tower of Hanoi. Write a recursive Program for Tower of hanoi
The Tower of Hanoi is a classic problem in computer science and mathematics. It involves
three pegs and a number of disks of different sizes. The problem is to move the entire stack of
disks from one peg to another, obeying the following rules:
Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on
top of another stack or on an empty peg.
No disk may be placed on top of a smaller disk.
The recursive C implementation of the Tower of Hanoi:
#include <stdio.h>
// Function to move a disk from source peg to destination peg and print the move
void moveDisk(int disk, char source, char destination) {
printf("Move disk %d from peg %c to peg %c\n", disk, source, destination);
}
// Recursive function to solve Tower of Hanoi for n disks
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
if (n == 1) {
moveDisk(1, source, destination);
return;
}
// Move (n-1) disks from source to auxiliary peg using destination as a temporary peg
towerOfHanoi(n - 1, source, destination, auxiliary);
// Move the nth disk from source to destination peg
moveDisk(n, source, destination);
// Move (n-1) disks from auxiliary peg to destination peg using source as a temporary peg
towerOfHanoi(n - 1, auxiliary, source, destination);
}
int main() {
int n;
// Input the number of disks
printf("Enter the number of disks: ");
scanf("%d", &n);
// Define the pegs
char source = 'A', auxiliary = 'B', destination = 'C';
printf("Tower of Hanoi with %d disks:\n", n);
towerOfHanoi(n, source, auxiliary, destination);
return 0;
}
Q7. Explain Tail Recursion with an example.
Tail recursion is a specific form of recursion where the recursive call is the last operation
performed in the function, and the result of the recursive call is immediately returned without
any further processing. In tail-recursive functions, the recursive call is the final operation
before the function returns its result.
#include<stdio.h>
//function that will return factorial
//this function will be executed recursively
int factorial( int n, int fact )
{
if ( n==0 || n==1 )
return fact;
else
factorial( n-1, n*fact );
}
//main function to test above function
int main( ){
int n,value;
//input an integer number
printf( "Enter the number : " );
scanf( "%d", &n );
if ( n < 0 )
printf( "No factorial of negative number\n" );
else
{
value = factorial( n,1 ); /* Function for factorial of number */
printf( "Factorial of %d = %d\n",n,value );
}
return 0;
}