Module2 Stacks ,Queues and Recursion

Stack Data Structure

A Stack is a linear data structure that follows a particular order in which the operations
are performed. The order may be LIFO(Last In First Out) or FILO(First In Last
Out). LIFO implies that the element that is inserted last, comes out first
and FILO implies that the element that is inserted first, comes out last.
It behaves like a stack of plates, where the last plate added is the first one to be
removed.

Pushing an element onto the stack is like adding a new plate on top.
Popping an element removes the top plate from the stack.



Working of Stack
Stack works on the LIFO pattern. As we can observe in the below figure there are five
memory blocks in the stack; therefore, the size of the stack is 5.
Suppose we want to store the elements in a stack and let's assume that stack is empty.
We have taken the stack of size 5 as shown below in which we are pushing the
elements one by one until the stack becomes full.
Data Structures and its Applications(B24CS302)

Since our stack is full as the size of the stack is 5. In the above cases, we can observe
that it goes from the top to the bottom when we were entering the new element in the
stack. The stack gets filled up from the bottom to the top.
When we perform the delete operation on the stack, there is only one way for entry
and exit as the other end is closed. It follows the LIFO pattern, which means that the
value entered first will be removed last. In the above case, the value 5 is entered first,
so it will be removed only after the deletion of all the other elements.
o Stacks adhere strictly to the Last-In-First-Out (LIFO) principle for insertion and
deletion of elements.
o Envision a vertical stack with the top portion being the active end for additions
and removals.
o Initially, when a stack is created, it is marked as empty with the top pointer set
to a sentinel value like -1
o During insertion (push operation), the element is placed at the current top
position after incrementing the top pointer.
o This push process continues until the stack's predetermined capacity is reached,
after which insertions aren't possible.
o For removal (pop operation), the element at the current top is retrieved and
returned.
o Simultaneously, the top pointer is decremented, removing that topmost element
from the stack.
o A pop attempt on an empty stack triggers an underflow condition, indicating an
erroneous operation.
o The stack grows upwards during pushes and shrinks downwards during pops,
maintaining the LIFO order.
o This disciplined addition and removal from a single end is a fundamental stack
property across its operations.
Algorithm of Stack
o A stack can be implemented using an array or a linked list data structure
o For an array implementation, we need to define a fixed size for the stack initially

Page 1 of 69
Data Structures and its Applications(B24CS302)

We maintain a 'top' variable that keeps track of the index of the topmost element
in the stack
o

o Initially, 'top' is set to -1, indicating an empty stack

o The following operations can be performed on a stack:
o Push Operation:
o Check if the stack is full (top == size - 1)
o If full, return an error (stack overflow)
o If not full, increment 'top' and insert the new element at the new
'top' index
o Pop Operation:
o Check if the stack is empty (top == -1)
o If empty, return an error (stack underflow)
o If not empty, retrieve the element at the 'top' index
o Decrement 'top' to remove the topmost element
o Peek Operation:
o Check if the stack is empty (top == -1)
o If empty, return an error
o If not empty, return the element at the 'top' index (without removing
it)
o isEmpty Operation:
o Check if 'top' is equal to -1
o If yes, return true (stack is empty)
o If no, return false (stack is not empty)
o isFull Operation:
o Check if 'top' is equal to size - 1
o If yes, return true (stack is full)
o If no, return false (stack is not full)
Algorithm for Stack Implementation
Initialize an array 'stack' of size 'n'
Initialize 'top' to -1
function push(item):
if top == n - 1:
print("Stack Overflow")
else:
top = top + 1
stack[top] = item

function pop():
if top == -1:
print("Stack Underflow")
else:
item = stack[top]
top = top - 1
return item

function peek():
if top == -1:
Page 2 of 69
Data Structures and its Applications(B24CS302)

print("Stack is empty")
else:
return stack[top]

function isEmpty():
return top == -1

function isFull():
return top == n - 1
This algorithm outlines the basic operations and their implementation for a stack data
structure using an array. The time complexity for push, pop, and peek operations is
O(1) as they involve constant time operations. However, the space complexity is O(n),
where 'n' is the fixed size of the array used to implement the stack.
The following are some common operations implemented on the stack:

Push (item): Inserts a new element 'item' onto the top of the stack. However,
attempting a push will result in an overflow error condition if the stack is
o

already at its maximum capacity.

o pop( ): Removes and returns the topmost element from the stack. But if the stack
is empty, attempting a pop will trigger an underflow error, as there are no
elements to remove.
o peek( ): Retrieves the value of the topmost element without removing it from the
stack. If the stack is empty, it indicates an error state.
o isEmpty( ): Checks if the stack is empty by verifying if the top pointer points to a
sentinel value (e.g., -1). Returns true if the stack is empty; otherwise, it is false.
o isFull( ): Determines if the stack has reached its maximum capacity by checking
if the top pointer is at the last valid index. Returns true if full, false if not.
o size( ): Returns the number of elements currently present in the stack.
o top( ): Accesses and returns the value of the topmost element without removing
it, similar to peek(). An alias for peek().
o display( ): Outputs all elements in the stack, typically by traversing from top to
bottom.
Additionally, some advanced operations include:
o clear( ): Removes all elements from the stack, resetting it to an empty state.
o reverse( ): Reverses the order of elements in the stack.
o contains(item): Checks if the given 'item' exists in the stack, returning true or
false.
These operations cover the essential functionality for manipulating and working with
stack data structures effectively. The specific implementation details may vary based
on the underlying data structure (e.g., array or linked list) and the programming
language.

PUSH operation
The steps involved in the PUSH operation is given below:
o Before inserting an element in a stack, we check whether the stack is full.
Page 3 of 69
Data Structures and its Applications(B24CS302)

If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o

o When we initialize a stack, we set the value of top as -1 to check that the stack is
empty.
o When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new position
of the top.
o The elements will be inserted until we reach the max size of the stack.

POP operation

The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is
empty.
o If we try to delete the element from the empty stack, then
the underflow condition occurs.
o If the stack is not empty, we first access the element which is pointed by
the top
o Once the pop operation is performed, the top is decremented by 1,
i.e., top=top-1.

Page 4 of 69
Data Structures and its Applications(B24CS302)

Implementation of Stack
C Program
Example
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

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

void push(int item) {

if (top == MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = item;
}

int pop() {
if (top == -1) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}

Page 5 of 69
Data Structures and its Applications(B24CS302)

int peek() {
if (top == -1) {
printf("Stack is empty\n");
return -1;
}
return stack[top];
}

int isEmpty() {
return top == -1;
}

int isFull() {
return top == MAX_SIZE - 1;
}

int main( ) {
push(10);
push(20);
push(30);
printf("Top element: %d\n", peek());
printf("Popped element: %d\n", pop());
printf("Top element: %d\n", peek());
return 0;
}

Stack using Array

Stack is a linear data structure which follows LIFO principle. To implement a stack
using an array, initialize an array and treat its end as the stack’s top.
Implement push (add to end), pop (remove from end), and peek (check end) operations,
handling cases for an empty or full stack.
Step-by-step approach:
1. Initialize an array to represent the stack.
2. Use the end of the array to represent the top of the stack.
3. Implement push (add to end), pop (remove from the end), and peek (check end)
operations, ensuring to handle empty and full stack conditions.
Here are the following operations of implement stack using array:

Push Operation in Stack:

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.
Before pushing the element to the stack, we check if the stack is full .
If the stack is full (top == capacity-1) , then Stack Overflows and we cannot insert


the element to the stack.



Page 6 of 69
Data Structures and its Applications(B24CS302)

Otherwise, we increment the value of top by 1 (top = top + 1) and the new value
is inserted at top position .


 The elements can be pushed into the stack till we reach the capacity of the stack.

Top or Peek Operation in Stack:

Returns the top element of the stack.

Before returning the top element from the stack, we check if the stack is empty.
If the stack is empty (top == -1), we simply print “Stack is empty”.


Otherwise, we return the element stored at index = top .




isEmpty Operation in Stack:

Returns true if the stack is empty, else false.=
Check for the value of top in stack.
If (top == -1) , then the stack is empty so return true .


Otherwise, the stack is not empty so return false .




isFull Operation in Stack :

Returns true if the stack is full, else false.
Check for the value of top in stack.
If (top == capacity-1), then the stack is full so return true .


Otherwise, the stack is not full so return false.




Implementation of stack using Fixed Sized Array

In this implementation, we use a fixed sized array. We take capacity as argument when
we create a stack. We create an array with size equal to given capacity. If number of
elements go beyond capacity, we throw an overflow error.

// C program to create a stack with given capacity

#include <stdio.h>
#include <stdlib.h>

struct Stack {
int top, cap;
int *a;
};

struct Stack* createStack(int cap) {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->cap = cap;
stack->top = -1;
stack->a = (int*)malloc(cap * sizeof(int));
return stack;
}

voiddeleteStack(struct Stack* stack) {

free(stack->a);
Page 7 of 69
Data Structures and its Applications(B24CS302)

free(stack);
}

intisFull(struct Stack* stack) {

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

intisEmpty(struct Stack* stack) {

return stack->top < 0;
}

int push(struct Stack* stack, int x) {

if (isFull(stack)) {
printf("Stack Overflow\n");
return 0;
}
stack->a[++stack->top] = x;
return 1;
}

int pop(struct Stack* stack) {

if (isEmpty(stack)) {
printf("Stack Underflow\n");
return 0;
}
return stack->a[stack->top--];
}

int peek(struct Stack* stack) {

if (isEmpty(stack)) {
printf("Stack is Empty\n");
return 0;
}
return stack->a[stack->top];
}

int main( ) {
struct Stack* s = createStack(5);
push(s, 10);
push(s, 20);
push(s, 30);
printf("%d popped from stack\n", pop(s));

printf("Top element is: %d\n", peek(s));

printf("Elements present in stack: ");

while (!isEmpty(s)) {
printf("%d ", peek(s));
Page 8 of 69
Data Structures and its Applications(B24CS302)

pop(s);
}
deleteStack(s);
return 0;
}

Output
30 popped from stack
Top element is: 20
Elements present in stack: 20 10

Stack - Linked List Implementation

To implement a stack using a singly linked list, we follow the LIFO (Last In, First Out)
principle by inserting and removing elements from the head of the list, where each node
stores data and a pointer to the next node.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

Page 9 of 69
Data Structures and its Applications(B24CS302)

// Node structure
struct Node {
int data;
struct Node* next;
};

// Check if stack is empty

intisEmpty(struct Node* head) {
return head == NULL;
}

// Push an element onto stack

void push(struct Node** head, intnew_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head;
*head = new_node;
}

// Pop the top element

void pop(struct Node** head) {
if (isEmpty(*head)) return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}

// Return the top element

int peek(struct Node* head) {
if (!isEmpty(head)) return head->data;
return INT_MIN;
}

int main() {
struct Node* head = NULL;

push(&head, 11);
push(&head, 22);
push(&head, 33);
push(&head, 44);

printf("%d\n", peek(head));

pop(&head);
pop(&head);

printf("%d\n", peek(head));

Page 10 of 69
Data Structures and its Applications(B24CS302)

return 0;
}

Benefits of implementing a stack using a singly linked list

Dynamic memory allocation: The size of the stack can be increased or decreased
dynamically by adding or removing nodes from the linked list, without the need to


allocate a fixed amount of memory for the stack upfront.

Efficient memory usage: Since nodes in a singly linked list only have a next
pointer and not a prev pointer, they use less memory than nodes in a doubly


linked list.
Easy implementation: Implementing a stack using a singly linked list is
straightforward and can be done using just a few lines of code.


Versatile: Singly linked lists can be used to implement other data structures such
as queues, linked lists, and trees.


Real time examples of stack

Stacks are used in various real-world scenarios where a last-in, first-out (LIFO) data
structure is required. Here are some examples of real-time applications of stacks:

Function Call Stack: When a function is called, its return address and parameters
are pushed onto the stack. The stack ensures functions execute and return in


reverse order..

Undo/Redo Operations: In apps like text or image editors, actions are pushed onto
a stack. Undo removes the last action, while redo restores it.


Browser History: Browsers use stacks to track visited pages. Visiting a page
pushes its URL onto the stack, and the "Back" button pops the last URL to go to


the previous page.

Expression Evaluation: In compilers, expressions are converted to postfix notation

and evaluated using a stack.


Call Stack in Recursion: Recursive function calls are pushed onto the stack. Once
recursion ends, the stack is popped to return to the previous function call.


Advantages of Using Stacks:

Maintaining Order: Stacks naturally keep track of the order in which elements are
added and removed following the In First Out (LIFO) principle. This feature is


beneficial for tasks that require processing or backtracking.

Page 11 of 69
Data Structures and its Applications(B24CS302)

Efficient Operations: Key stack operations such as push, pop and peek have a time
complexity of O(1), ensuring insertion and removal of elements.


Memory Management Support: Stacks play a role in managing function call

stacks during recursion, assisting in allocating and deallocating memory for


variables.

Reverse Functionality: Stacks enable the reversal of strings, expressions or

sequences by popping elements in the order from which they were pushed.


Expression Conversion Aid: Stacks are essential for converting expressions

between infix, prefix and postfix notations. A function for compilers and


expression evaluators.

Undo/Redo Capability: Stacks' Last In First Out nature makes them ideal for
implementing undo/redo features in text editors, graphic tools or interactive


applications.

 Disadvantages Associated with Stacks:

Size Limitation Restriction: In array-based implementations, stacks come with a

fixed size set during initialization; this can result in stack overflow if the size is


underestimated.

Limited Access Scope: Elements within a stack can only be accessed from the
position, making it inefficient to search for or access elements located towards


the bottom sections of the stack.

One-way operations: Stacks permit adding and removing elements from an end
(top) which restricts their versatility when compared to data structures such, as


queues or doubly linked lists.

Extra memory usage: When using linked lists each node needs memory for
holding the pointer, which could lead to space inefficiency, for stacks that are


large.

Polish Notation
Algebraic expressions can be written using three separate but equivalent notations
namely infix, postfix, and prefix notations.

Infix Notation

The operator symbol is placed between its two operands in most arithmetic
operations. This is called infix expression.
For example, (A + B) ;here the operator + is placed between the two operands a and
b.

Although we find it simple to write expressions in infix notation, computers find it

difficult to parse. So, the computer normally evaluates arithmetic expressions written

Page 12 of 69
 Data Structures and its Applications(B24CS302)

in infix notation after converting them into postfix notation. The stack is the primary
tool used to complete the given task in each phase.

Prefix Notation (Polish Notation)

Computers perform better when expressions are written in prefix and postfix
notations.
Prefix notation refers to the notation in which the operator is placed before its two
operand.

For example, if A + B is an expression in infix notation, then +AB is the equivalent

expression in prefix notation.

Postfix Notation (Reverse Polish Notation)

In postfix notation, the operator is placed after the operands. For example, if an
expression is written in infix notation as A + B, it can be written in postfix notation
as AB+.
The evaluation of a postfix and prefix expressions are always performed from left to
right.

Evaluation of a Postfix Expression

Steps to Evaluate a Postfix Expression

1. Use a Stack: A stack is used to store operands temporarily.

2. Traverse the Expression:
o If the current character is an operand, push it onto the stack.
o If the current character is an operator, pop the top two elements from the
stack, apply the operator, and push the result back onto the stack.
3. Final Result: After processing the entire expression, the stack will contain a single
element, which is the result.

The following algorithm is used to evaluate the value of a postfix expression.

1. Add a ) at the end of the post fix expression
2. Scan every character of the postfix expression and repeat Steps 3 and 4 until ) is
encountered
3. If an operand is encountered, out it on the STACK.
4. If an operator O is encountered, then

POP the two top elements of STACK as A(topmost element) and B(next-to-top
element).
1. Evaluate B O A.
2. Push the result of evaluation on the STACK.
5. SET RESULT equal to the topmost element of the STACK.

Example
Consider the following postfix notation
823*8+2/–
. The equivalent infix expression is
Page 13 of 69
Data Structures and its Applications(B24CS302)

8 – ((2 * 3) + 8) / 2
.
The following table shows the procedure for evaluating the expression by simulating
the above algorithm.
Symbol
STACK
Scanned

8 8

2 8, 2

3 8, 2, 3

* 8, 6

8 8, 6, 8

+ 8, 14

2 8, 14, 2

/ 8, 7

– 1

The final number in the stack, 1, is the value of the postfix expression.
For example, the postfix expression 5 6 + means 5 + 6.

Example 1 :
Evaluate the postfix expression: 2 3 1 * + 9 -
1. Initial Stack: Empty
2. Process 2: Push 2 → Stack: [2]
3. Process 3: Push 3 → Stack: [2, 3]
4. Process 1: Push 1 → Stack: [2, 3, 1]
5. Process *: Pop 3 and 1, compute 3 * 1 = 3, push 3 → Stack: [2, 3]
6. Process +: Pop 2 and 3, compute 2 + 3 = 5, push 5 → Stack: [5]
7. Process 9: Push 9 → Stack: [5, 9]
8. Process -: Pop 5 and 9, compute 5 - 9 = -4, push -4 → Stack: [-4]
Result: -4

Explanation:
1. Stack Operations: A stack is used to store operands. Push operands onto the stack
and pop them when an operator is encountered.
2. Operators: Perform the operation on the two most recent operands popped from
the stack.

Page 14 of 69
Data Structures and its Applications(B24CS302)

3. Result: The final result is the only value left in the stack after processing the
entire expression.
Example 2:
For the postfix expression 53+82-*:
 Push 5, 3.
 Encounter +: Pop 5 and 3, compute 5 + 3 = 8, push 8.
 Push 8, 2.
 Encounter -: Pop 8 and 2, compute 8 - 2 = 6, push 6.
 Encounter *: Pop 8 and 6, compute 8 * 6 = 48.
The result is 48.

//Implementation of evaluating a postfix expression in C using a stack:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

#define MAX 100

// Stack structure
typedefstruct {
int top;
int items[MAX];
} Stack;

// Stack operations
void push(Stack *s, int value) {
if (s->top == MAX - 1) {
printf("Stack Overflow\n");
exit(1);
}
s->items[++(s->top)] = value;
}

int pop(Stack *s) {

if (s->top == -1) {
printf("Stack Underflow\n");
exit(1);
}
return s->items[(s->top)--];
}

// Function to evaluate postfix expression

intevaluatePostfix(char *expression) {
Stack stack;
stack.top = -1;

for (inti = 0; expression[i] != '\0'; i++) {

Page 15 of 69
Data Structures and its Applications(B24CS302)

charch = expression[i];

if (isdigit(ch)) {
push(&stack, ch - '0'); // Convert char to int
} else {
int val2 = pop(&stack);
int val1 = pop(&stack);

switch (ch) {
case '+': push(&stack, val1 + val2); break;
case '-': push(&stack, val1 - val2); break;
case '*': push(&stack, val1 * val2); break;
case '/': push(&stack, val1 / val2); break;
case '^': push(&stack, pow(val1, val2)); break;
default: printf("Invalid operator: %c\n", ch); exit(1);
}
}
}
return pop(&stack);
}

int main( )
{
char expression[] = "53+82-*"; // Example postfix expression
printf("Result of postfix evaluation: %d\n", evaluatePostfix(expression));
return 0;
}

Conversion of an Infix Expression into a Postfix Expression

For the sake of simplicity, we will only use the +, –, *, /, and % operators. The
order of precedence of these operators is as follows:
 Higher priority
*, /, %
 Lower priority
+, –
The algorithm below converts an infix expression to a postfix expression.
1. Push "(" on to the stack, and add ")" to the end of infix expression.
2. Repeat until each character in the infix notation is scanned
 IF a "(" is encountered, push it on the stack.
 IF an operand is encountered, add it to the postfix expression.
 IF a ")" is encountered, then
1. Repeatedly pop from stack and add it to the postfix expression until a
"(" is encountered.

Page 16 of 69
Data Structures and its Applications(B24CS302)

2. Discard the "(" . That is, remove the "(" from stack and do not add it to
the postfix expression.
IF an
Infix Stack Postfix operator O is


Charact Expression encountered, then

er 1. R
Scanned e
p
( ea
te
A ( A dl
y
+ (+ A

( (+( A

B (+( AB

* (+(* AB

C (+(* ABC

) ABC*+
pop from stack and add each operator (popped from the stack) to the
postfix expression which has the same precedence or a higher
precedence than O.
2. Push the operator O to the stack.
3. Repeatedly pop from the stack and add it to the postfix expression until the stack
is empty.
Example
Convert the infix expression A + ( B * C ) into postfix expression.

Page 17 of 69
Data Structures and its Applications(B24CS302)

//C Program: Infix to Postfix Conversion

#include <stdio.h>
#include <ctype.h> // for isalnum()
#include <string.h> // for strlen()

#define MAX 100

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

// push function
void push(char c) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = c;
}
}

// pop function
char pop() {
if (top == -1) {
return -1;
} else {
return stack[top--];
}
}

// precedence function
int precedence(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return 0;
Page 18 of 69
Data Structures and its Applications(B24CS302)

// Infix to Postfix Conversion

void infixToPostfix(char infix[]) {
char postfix[MAX];
int i, k = 0;
char ch;

for (i = 0; infix[i] != '\0'; i++) {

ch = infix[i];

// If operand → add to postfix

if (isalnum(ch)) {
postfix[k++] = ch;
}
// If '(' → push to stack
else if (ch == '(') {
push(ch);
}
// If ')' → pop until '('
else if (ch == ')') {
while ((stack[top] != '(') && (top != -1)) {
postfix[k++] = pop();
}
pop(); // remove '('
}
// If operator
else {
while (precedence(stack[top]) >= precedence(ch)) {
postfix[k++] = pop();
}
push(ch);
}
}

// pop remaining operators

while (top != -1) {
postfix[k++] = pop();
}

postfix[k] = '\0'; // null terminate string

printf("Postfix Expression: %s\n", postfix);
}

// main function
int main() {
char infix[MAX];
printf("Enter an infix expression: ");
scanf("%s", infix);

Page 19 of 69
Data Structures and its Applications(B24CS302)

infixToPostfix(infix);

return 0;
}

Output
Input: A+B*C
Output: ABC*+
Input: (A+B)*C
Output: AB+C*

Convert Infix To Prefix Notation

Page 20 of 69
Data Structures and its Applications(B24CS302)

Given an infix expression consisting of operators (+, -, *, /, ^) and operands (lowercase

characters), the task is to convert it to a prefix expression.
Infix Expression: The expression of type a 'operator' b (a+b, where + is an operator)
i.e., when the operator is between two operands.
Prefix Expression: The expression of type 'operator' a b (+ab where + is an operator)
i.e., when the operator is placed before the operands.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

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

// Function to push an element onto the stack

void push(char c) {
stack[++top] = c;
}

// Function to pop an element from the stack

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

// Function to check precedence of operators

int precedence(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return 0;
}

Page 21 of 69
Data Structures and its Applications(B24CS302)

// Function to check if a character is an operator

intisOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

// Function to reverse a string

void reverse(char* expr) {
intlen = strlen(expr);
for (inti = 0; i<len / 2; i++) {
char temp = expr[i];
expr[i] = expr[len - i - 1];
expr[len - i - 1] = temp;
}
}

// Function to convert infix to prefix

voidinfixToPrefix(char* infix, char* prefix) {
reverse(infix); // Reverse the infix expression
int j = 0;

for (inti = 0; infix[i] != '\0'; i++) {

char c = infix[i];

if (isalnum(c)) { // If operand, add to prefix

prefix[j++] = c;
} else if (c == ')')
{
// If closing parenthesis, push to stack
push(c);
} else if (c == '(')
{
// If opening parenthesis, pop until ')'
while (top != -1 && stack[top] != ')')
{
prefix[j++] = pop();
}
pop(); // Remove ')'
}
else if (isOperator(c))
{
// If operator
while (top != -1 && precedence(stack[top]) >= precedence(c)) {
prefix[j++] = pop();
}
push(c);
}
}

Page 22 of 69
Data Structures and its Applications(B24CS302)

// Pop remaining operators

while (top != -1) {
prefix[j++] = pop();
}

prefix[j] = '\0'; // Null-terminate the prefix expression

reverse(prefix); // Reverse to get the final prefix expression
}

int main() {
char infix[MAX], prefix[MAX];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPrefix(infix, prefix);
printf("Prefix expression: %s\n", prefix);
return 0;
}
Prefix to Infix Conversion

Infix : An expression is called the Infix expression if the operator appears in between
the operands in the expression. Simply of the form (operand1 operator operand2).
Example : (A+B) * (C-D)
Prefix : An expression is called the prefix expression if the operator appears in the
expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )

Given a Prefix expression, convert it into a Infix expression.

Computers usually does the computation in either prefix or postfix (usually postfix). But
for humans, its easier to understand an Infix expression rather than a prefix. Hence
conversion is need for human understanding.

Examples:
Input : Prefix : *+AB-CD
Output : Infix : ((A+B)*(C-D))

Input : Prefix : *-A/BC-/AKL

Output : Infix : ((A-(B/C))*((A/K)-L))

Page 23 of 69
Data Structures and its Applications(B24CS302)

Algorithm for Prefix to Infix:

Read the Prefix expression in reverse order (from right to left)

If the symbol is an operand, then push it onto the Stack


If the symbol is an operator, then pop two operands from the Stack


Create a string by concatenating the two operands and the operator between


them.
string = (operand1 + operator + operand2) and
Push the resultant string back to Stack
Repeat the above steps until the end of Prefix expression.


At the end stack will have only 1 string i.e resultant string



// Convert prefix to Infix expression

prefix to infix in C
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node{
char* data;
struct Node* next;
};
typedef struct Node NODE;

NODE* push(NODE* top, char* item){

NODE* newNode;
newNode=(NODE*)malloc(sizeof(NODE));
newNode->next=NULL;
newNode->data=item;
if(top==NULL){

Page 24 of 69
Data Structures and its Applications(B24CS302)

top=newNode;
}
else{
newNode->next=top;
top=newNode;
}
return top;
}
char pop(NODE* top){
NODE* temp=top;
int i, returnValue;
if(top==NULL){
return top;
returnValue='\0';
}
else{
top=top->next;
returnValue=temp->data;
free(temp);
}
return returnValue;
}

void display(NODE* top){

NODE* temp=top;
while(temp->next!=NULL){
printf("%c",temp->data);
temp=temp->next;
}
printf("\n");
}
int isOperator(char c){
switch(c)
{
case '*':
case '/':
case '+':
case '-':
return 1;
}
return 0;
}

char* prefix_to_infix(char* expression){

NODE* top;
top=(NODE*)malloc(sizeof(NODE));
top->next=NULL;

Page 25 of 69
Data Structures and its Applications(B24CS302)

int i;
for(i=strlen(expression)-1;i>=0;i--)
{
if(isOperator(expression[i])){
char a=pop(top);
char b=pop(top);

char temp[5]={'(',a,expression[i],b,')'};
push(top,temp);
}
else{
top=push(top, expression[i]);
}
}
return top->data;
}

int main(){
NODE* top;
top=(NODE*)malloc(sizeof(NODE));
top->next=NULL;
char expression[30];
gets(expression);

puts(prefix_to_infix(expression));
}

Postfix to Prefix Conversion

Postfix: An expression is called the postfix expression if the operator appears in the
expression after the operands. Simply of the form (operand1 operand2 operator).
Example : AB+CD-* (Infix : (A+B) * (C-D) )
Prefix : An expression is called the prefix expression if the operator appears in the
expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Problem Statement
Given a Postfix expression, convert it into a Prefix expression.
Instead of converting Postfix → Infix → Prefix, we can directly convert Postfix → Prefix.
This method is both efficient (fewer steps) and intuitive, since computers naturally
evaluate expressions in Postfix form.
Examples:
Input : Postfix : AB+CD-*
Output : Prefix : *+AB-CD
Explanation : Postfix to Infix : (A+B) * (C-D)
Infix to Prefix : *+AB-CD

Input : Postfix : ABC/-AK/L-*

Page 26 of 69
Data Structures and its Applications(B24CS302)

Output : Prefix : *-A/BC-/AKL

Explanation : Postfix to Infix : ((A-(B/C))*((A/K)-L))
Infix to Prefix : *-A/BC-/AKL

Algorithm for Postfix to Prefix:

We use a stack to build the prefix expression step by step:
 Read the Postfix expression from left to right
 If the symbol is an operand, then push it onto the Stack
 If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator before them.
string = operator + operand2 + operand1
And push the resultant string back to Stack
 Repeat the above steps until end of Postfix expression.

Code for Postfix to Prefix in C

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 20
charstr[MAX], stack[MAX];
int top = -1;
void push (char c)
{
stack[++top] = c;
}
char pop ()
{
return stack[top--];
}
// A utility function to check if the given character is operand
intcheckIfOperand (char ch)
{
return (ch>= 'a' &&ch<= 'z') || (ch>= 'A' &&ch<= 'Z');
}
//function to check if it is an operator
intisOperator (char x)
{
switch (x)
{
case '+':
Page 27 of 69
Data Structures and its Applications(B24CS302)

case '-':
case '/':
case '*':
return 1;
}
return 0;
}
voidpostfixToprfix ()
{
int n, i, j = 0;
char c[20];
char a, b, op;

printf ("Enter the postfix expression\n");

scanf ("%s", str);
n = strlen (str);
for (i = 0; i< MAX; i++)
stack[i] = '\0';
printf ("Prefix expression is: ");
for (i = n - 1; i>= 0; i--)
{
if (isOperator (str[i]))
{
push (str[i]);
}
else
{
c[j++] = str[i];
while ((top != -1) && (stack[top] == '#'))
{
a = pop ();
c[j++] = pop ();
}
push ('#');
}
}
c[j] = '\0';

i = 0;
j = strlen (c) - 1;
char d[20];

while (c[i] != '\0')

{
d[j--] = c[i++];
}
printf ("%s\n", d);
}
Page 28 of 69
Data Structures and its Applications(B24CS302)

int main ()
{
postfixToprfix ();
return 0;
}
Output
Enter the postfix expression
ab+cd-*
Prefix expression is: *+ab-cd
Queue in C

A queue is a linear data structure that follows the First In First Out (FIFO) order of
insertion and deletion. It means that the element that is inserted first will be the first
one to be removed and the element that is inserted last will be removed at last.

Representation of Queue in C

In C, the queue can be represented as the structure that contains one array of fixed
size, index pointer to the front, and index pointer to the end.
structQueue {
typearr[MAX_SIZE];
int back;
int front;
}
The front pointer initial value will be -1 and the back pointer initial value will be 0. The
front pointer will always point to one element before the element that is to be dequeue
while the back pointer will point to the next empty element after the element that is just
enqueued.

Basic Operations of Queue in C

Following are the basic operations of a Queue that are used frequently to manipulate
the elements present inside the queue:

Page 29 of 69
Data Structures and its Applications(B24CS302)

Operati Time Space

on Description Complexity Complexity

Enqueu Inserts an element in the queue through rear

O(1) O(1)
e pointer.

Dequeu Removes an element from the queue through

O(1) O(1)
e front pointer.

Peek Returns the front element of the queue. O(1) O(1)

Returns true is the queue is full otherwise

O(1) O(1)
IsFull returns false.

Returns true is the queue is empty otherwise

O(1) O(1)
IsEmpty returns false.

Implementation of a Queue in C

We can implement a queue in C using either an array or a linked list. In this article, we
will use the array data structure to store the elements. The insertion in the queue is
done at the back of the queue and the deletion is done at the front. So we maintain two
index pointers front and rear pointers to keep track of the front and back of the queue.
The queue consists of two basic operations enqueuewhich adds elements to the queue
(insertion) from the rear pointer and dequeue(deletion) which removes elements from
the queue through the front pointer.

C Program To Implement a Queue

#include <stdbool.h>
#include <stdio.h>
#define MAX_SIZE 100

// Defining the Queue structure

typedefstruct {
int items[MAX_SIZE];
int front;
int rear;
} Queue;

// Function to initialize the queue

voidinitializeQueue(Queue* q)
{
q->front = -1;

Page 30 of 69
Data Structures and its Applications(B24CS302)

q->rear = 0;
}

// Function to check if the queue is empty

boolisEmpty(Queue* q)
{
return (q->front == q->rear - 1);
}

// Function to check if the queue is full

boolisFull(Queue* q) { return (q->rear == MAX_SIZE); }

// Function to add an element to the queue (Enqueue

// operation)
voidenqueue(Queue* q, int value)
{
if (isFull(q)) {
printf("Queue is full\n");
return;
}
q->items[q->rear] = value;
q->rear++;
}

// Function to remove an element from the queue (Dequeue

// operation)
voiddequeue(Queue* q)
{
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}
q->front++;
}

// Function to get the element at the front of the queue

// (Peek operation)
int peek(Queue* q)
{
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1; // return some default value or handle
// error differently
}
return q->items[q->front + 1];
}

// Function to print the current queue

Page 31 of 69
Data Structures and its Applications(B24CS302)

voidprintQueue(Queue* q)
{
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}

printf("Current Queue: ");

for (inti = q->front + 1; i< q->rear; i++) {
printf("%d ", q->items[i]);
}
printf("\n");
}

int main( )
{
Queue q;
initializeQueue(&q);

// Enqueue elements
enqueue(&q, 10);
printQueue(&q);

enqueue(&q, 20);
printQueue(&q);

enqueue(&q, 30);
printQueue(&q);

// Peek front element

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

// Dequeue an element
dequeue(&q);
printQueue(&q);

// Peek front element after dequeue

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

return 0;
}

Output
Current Queue: 10
Current Queue: 10 20
Current Queue: 10 20 30
Front element: 10
Current Queue: 20 30
Page 32 of 69
Data Structures and its Applications(B24CS302)

Front element after dequeue: 20

What is Circular Queue?

A circular queue is a type of queue in which the last position is connected back to
the first position to make a circle. It is also known as a Ring Buffer. In a normal
queue, once the queue becomes full, we cannot insert the next element even if there
is a space in front of the queue. But using a circular queue, we can use the space to
insert elements.

It is a linear data structure that follows the FIFO mechanism. The circular queue is a
more efficient way to implement a queue in a fixed size array. In a circular queue, the
last element points to the first element making a circular link.

Representation of Circular Queue

Following is the representation of a circular queue, where the front is the index of the
first element, and the rear is the index of the last element.

Operations on Circular Queue

There are mainly four operations that can be performed on a circular queue:
 Enqueue: Insert an element into the circular queue.
 Dequeue: Delete an element from the circular queue.
 Front: Get the front element from the circular queue.
 Rear: Get the last element from the circular queue.

Circular Queue using Array

Following is the implementation of a circular queue using an array:

 Enqueue Operation on Circular Queue
 Enqueue operation is used for inserting an element into the circular queue. The
steps to perform the enqueue operation are as follows:

Algorithm for Enqueue Operation

Following are the steps to perform the enqueue operation on a circular queue:

Page 33 of 69
Data Structures and its Applications(B24CS302)

1.Initialize an array or any data structure to store the elements of the circular queue.
2.Initialize two variables front and rear.
3.Check if the circular queue is full.
4.If it is not full, and if the front is -1, set the front to 0.
5.Increment the rear by 1 and store it in the rear index.
6.Update the rear index using rear = (rear + 1) % SIZE.

//C Program
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
// Check if the queue is full
intisFull() {
if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
return 0;
}
// Check if the queue is empty
intisEmpty() {
if(front == -1) return 1;
return 0;
}
// Adding an element
voidenQueue(int element) {
if(isFull()) printf("\n Queue is full!! \n");
else {
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Display the queue
void display() {
inti;
if(isEmpty()) printf(" \n Empty Queue\n");
else {
printf("\n Items -> ");
for(i = front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
}
}
int main() {
enQueue(1);
enQueue(2);
enQueue(3);
Page 34 of 69
Data Structures and its Applications(B24CS302)

enQueue(4);
enQueue(5);
display();
return 0;
}

Output
The output obtained is as follows −
Inserted -> 1
Inserted -> 2
Inserted -> 3
Inserted -> 4
Inserted -> 5
Items -> 1 2 3 4 5
 Dequeue Operation on Circular Queue
 Dequeue operation is used for deleting an element from the circular queue. The
steps to perform the dequeue operation are as follows:

Algorithm for Dequeue Operation

Following are the steps to perform the dequeue operation on a circular queue:
1.Check if the circular queue is empty.
2.If the queue is not empty, store the element at the front index.
3.If the front and rear are equal, set the front and rear to -1.
4.Else, increase the front index by 1 using the formula front = (front + 1) % SIZE.
5.At last print the deleted element.

Following are the programs to remove a element from the circular queue −
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
// Check if the queue is full
intisFull( ) {
if( (front == rear + 1) || (front == 0 && rear == SIZE-1))
return 1;
return 0;
}
// Check if the queue is empty
intisEmpty( ) {
if(front == -1) return 1;
return 0;
}
// Adding an element
voidenQueue(int element) {
if(isFull( ))
printf("\n Queue is full!! \n");
Page 35 of 69
Data Structures and its Applications(B24CS302)

else {
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Deleting an element
intdeQueue( ) {
int element;
if(isEmpty()) {
printf("\n Queue is empty!! \n");
return(-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
} else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return(element);
}
}
// Display the queue
void display( ) {
inti;
if(isEmpty( ))
printf(" \n Empty Queue\n");
else {
printf("\n Items -> ");
for(i = front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
}
}
int main( ) {
enQueue(1);
enQueue(2);
enQueue(3);
display( );
deQueue( );
display( );
return 0;
}
Front Operation on Circular Queue
Page 36 of 69
Data Structures and its Applications(B24CS302)

Front operation is used to get the front element from the circular queue. The steps to
perform the front operation are as follows:

Algorithm for Front Operation

1.Check if the circular queue is empty.
2.If not empty, print the front index element/

//Code for Front Operation in Circular Queue

#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
// Check if the queue is full
intisFull() {
if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
return 0;
}
// Check if the queue is empty
intisEmpty() {
if(front == -1) return 1;
return 0;
}
// Adding an element
voidenQueue(int element) {
if(isFull()) printf("\n Queue is full!! \n");
else {
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Display the queue
void display() {
inti;
if(isEmpty()) printf(" \n Empty Queue\n");
else {
printf("\n Front -> %d ",front);
printf("\n Items -> ");
for(i = front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
}
}
int main(){
enQueue(1);
Page 37 of 69
Data Structures and its Applications(B24CS302)

enQueue(2);
enQueue(3);
display();
return 0;
}
Output
The output obtained is as follows −
Inserted -> 1
Inserted -> 2
Inserted -> 3
Front -> 0
Items -> 1 2 3
Rear Operation on Circular Queue
Rear operation is used to get the last element from the circular queue. The steps to
perform the rear operation are as follows:
Algorithm for Rear Operation
1.Check if the circular queue is empty..
2.If it is not empty, print the element at the rear index.
Code for Rear Operation in Circular Queue
Following are the programs to look a at the rear element−
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
// Check if the queue is full
intisFull() {
if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
return 0;
}
// Check if the queue is empty
intisEmpty() {
if(front == -1) return 1;
return 0;
}
// Adding an element
voidenQueue(int element) {
if(isFull()) printf("\n Queue is full!! \n");
else {
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Display the queue
void display() {
inti;
if(isEmpty()) printf(" \n Empty Queue\n");
Page 38 of 69
Data Structures and its Applications(B24CS302)

else {
printf("\n Items -> ");
for(i = front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
printf("\n Rear -> %d \n",rear);
}
}
int main( ){
enQueue(1);
enQueue(2);
enQueue(3);
display( );
return 0;
}

Output
The output obtained is as follows −
Inserted -> 1
Inserted -> 2
Inserted -> 3
Items -> 1 2 3
Rear -> 2

Circular Queue using Linked List

Following are the implementation of a circular queue using a linked list:

//C Program
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* link;
};

struct Node* front = NULL;

struct Node* rear = NULL;

// Check if the queue is empty

intisEmpty() {
return front == NULL;
}

// Adding an element
Page 39 of 69
Data Structures and its Applications(B24CS302)

voidenQueue(int value) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = value;
newNode->link = NULL;
if(isEmpty()) {
front = newNode;
} else {
rear->link = newNode;
}
rear = newNode;
rear->link = front;
printf("\n Inserted -> %d", value);
}

// Deleting an element
intdeQueue( ) {
int value;
if(isEmpty( )) {
printf("\n Queue is Empty!!");
return -1;
} else {
struct Node* temp = front;
value = temp->data;
if(front == rear) {
front = rear = NULL;
} else {
front = front->link;
rear->link = front;
}
free(temp);
return value;
}
}

// Display the queue

void display( ) {
struct Node* temp = front;
if(isEmpty( )) {
printf("\n Queue is Empty!!\n");
} else {
printf("\n Front -> ");
do {
printf("%d ", temp->data);
temp = temp->link;
} while(temp != front);
printf("\n");
}
}
Page 40 of 69
Data Structures and its Applications(B24CS302)

int main( ) {
enQueue(14);
enQueue(22);
enQueue(6);
// Display elements present in the queue
printf("Initial Queue ");
display( );
// Deleting elements from queue
printf("\nElement Removed = %d", deQueue( ));
// Display elements present in the queue
printf("\nQueue after deletion an element: ");
display( );
// Inserting elements to queue
enQueue(9);
//Showing the rear of the queue
printf("\nRear Element = %d", rear->data);
enQueue(20);
//Showing the front of the queue
printf("\nFront Element = %d", front->data);
printf("\nFinal Queue ");
display();
return 0;
}

Applications of Circular Queue

Following are some of the applications of a circular queue:

 Memory Management: Circular queues are used in memory management to
manage the memory efficiently. It is used to allocate memory to the processes
when they are in need of memory.
 Buffer Management: These queues are also useful in buffer management.
Consider a situation where data is produced at a faster rate than it is consumed.
In such cases, a circular queue is used to store the data temporarily.
 Operating System: Suppose your system has a lot of processes to execute. In such
cases, for the better management of processes, the operating system uses a
circular queue to allocate the CPU to the processes.
 Traffic Management: Traffic singals are controlled by the circular queue. Let's say
there are three signals, red, yellow, and green. The signals are in a circular
queue. When the green signal is on, the next signal will be yellow, and then red.
This process will continue in a circular manner.
 Multimedia Player: When we play songs in a multimedia player, the songs are
played in a circular manner. Once the last song is played, the first song will be
played next. This is done using a circular queue.

Implementing Circular Queue using Linked List in C

Page 41 of 69
Data Structures and its Applications(B24CS302)

The task is to implement the circular queue with the following operations using
a circular linked list.
Operations on Circular Queue:
Front: Get the front item from the queue.
Rear: Get the last item from the queue.


enQueue(value): This function is used to insert an element into the circular



queue. In a circular queue, the new element is always inserted at



the Rear position.

deQueue( ): This function is used to delete an element from the circular queue. In
a queue, the element is always deleted from the front position.


Operations:
Front( ): return the front node's value if not null. Otherwise return -1.
Rear( ): return the rear node's value if not null. Otherwise return -1.
EnQueue(int value): Create a new node and set its value. If front is null, then
set front = rear = newNode. Otherwise, set tail->next = newNode, tail =
newNode, tail->next = front.
DeQueue( ): If list is empty, return -1. Otherwise get the front node's
value and remove it from the list. If the list contains only one node, then set front =
rear = null.
Otherwise update head = head->next and rear->next = head.

//C Program to implement a circular Queue using an array

#include <stdio.h>
#include <stdlib.h>int *queue;
int front = -1;

Page 42 of 69
Data Structures and its Applications(B24CS302)

int rear = -1;

int Size;
void Enqueue(int element)
{
if ((rear + 1) % Size== front)
{
printf(“Queue Overflow\n”);
return;
}
if (front == -1)
{
front = 0;
}
rear = (rear + 1) % Size;
queue[rear] = element;
printf(“Enqueued %d\n”, element);
}intDequeue() {
if (front == -1) {
printf(“Queue Underflow\n”);
return -1; // Error code
}
int element = queue[front];
if (front == rear) {
front = rear = -1; // Queue becomes empty
} else {
front = (front + 1) % Size;
}
return element;
}int Peek() {
if (front == -1) {
printf(“Queue is Empty\n”);
return -1; // Error code
}
return queue[front];
}
intIsEmpty() {
return (front == -1);
}
intIsFull() {
return ((rear + 1) % Size== front);
}
void DisplayQueue() {
if (front == -1) {
printf(“Queue is Empty\n”);
return;
}

Page 43 of 69
Data Structures and its Applications(B24CS302)

printf(“Queue elements: “);

inti = front;
while (1) {
printf(“%d “, queue[i]);
if (i == rear) {
break;
}
i = (i + 1) % Size;
}
printf(“\n”);
}
int main() {
printf(“Enter the maximum size of the queue: “);
scanf(“%d”, &Size);
// Dynamically allocate memory for the queue
queue = (int *)malloc(Size* sizeof(int));
int choice, element;
do {
printf(“\nMain Menu:\n”);
printf(” 1. Enqueue\n”);
printf(” 2. Dequeue\n”);
printf(” 3. Peek\n”);
printf(” 4. Check if Empty\n”);
printf(” 5. Check if Full\n”);
printf(” 6. Display Queue\n”);
printf(” 7. Exit\n”);
printf(“Enter your choice: “);
scanf(“%d”, &choice);
switch (choice) {
case 1:
printf(“Enter element to enqueue: “);
scanf(“%d”, &element);
Enqueue(element);
break;
case 2:
element = Dequeue();
if (element != -1) {
printf(“Dequeued element: %d\n”, element);
}
break;
case 3:
element = Peek();
if (element != -1) {
printf(“Front element: %d\n”, element);
}
break;

Page 44 of 69
Data Structures and its Applications(B24CS302)

case 4:
printf(“Is queue empty? %s\n”, IsEmpty() ? “Yes” : “No”);
break;
case 5:
printf(“Is queue full? %s\n”, IsFull() ? “Yes” : “No”);
break;
case 6:
DisplayQueue();
break;
case 7:
printf(“Exiting…\n”);
break;
default:
printf(“Invalid choice!\n”);
}
} while (choice != 7);
// Free the dynamically allocated memory
free(queue);
return 0;
}

Output:
Enter the maximum size of the queue: 10

Main Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Check if Empty
5. Check if Full
6. Display Queue
7. Exit
Enter your choice: 6
Queue is Empty

Main Menu:
1. Enqueue
2. Dequeue
3. Peek
4. Check if Empty
5. Check if Full
6. Display Queue
7. Exit
Enter your choice:

Page 45 of 69
Data Structures and its Applications(B24CS302)

To implement a circular queue using dynamic arrays in C, follow these steps:

1. Dynamic Memory Allocation: Use malloc to allocate memory for the queue. This
allows the size of the queue to be flexible.
2. Front and Rear Pointers: Maintain two pointers, front and rear, to track the
positions of the first and last elements in the queue.
3. Enqueue Operation: To add an element, increment the rear pointer and insert the
element at that position. If the queue is full, you may need to resize the array.
4. Dequeue Operation: To remove an element, increment the front pointer. If the
queue becomes empty, reset the pointers.
5. Wrap Around: Use the modulo operator to wrap around the pointers when they
reach the end of the array, creating a circular effect.
This implementation allows efficient use of space and maintains the FIFO order of
elements.

// C program for insertion and deletion in Circular Queue

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Queue {
struct Node *front, *rear;
};

struct Node* createNode(intnewdata);

// Function to insert element in a Circular queue

voidenQueue(struct Queue* q, int value) {
struct Node* newNode = createNode(value);

if (q->front == NULL)
q->front = newNode;
else
q->rear->next = newNode;

q->rear = newNode;
q->rear->next = q->front;
}

// Function to delete element from Circular Queue

intdeQueue(struct Queue* q) {
Page 46 of 69
Data Structures and its Applications(B24CS302)

// if queue is empty
if (q->front == NULL) {
return -1;
}

int value;

// If this is the last node to be deleted

if (q->front == q->rear) {
value = q->front->data;
free(q->front);
q->front = q->rear = NULL;
} else {
struct Node* temp = q->front;
value = temp->data;
q->front = q->front->next;
q->rear->next = q->front;
free(temp);
}

return value;
}

voidprintQueue(struct Queue* q) {
if (q->front == NULL) return;

struct Node* curr = q->front;

do {
printf("%d ", curr->data);
curr = curr->next;
} while (curr != q->front);
printf("\n");
}

// Function to return the front value

int front(struct Queue* q) {
struct Node* front = q->front;

if (front == NULL) {
return -1;
}

return front->data;
}

// Function to return the rear value

int rear(struct Queue* q) {
Page 47 of 69
Data Structures and its Applications(B24CS302)

struct Node* rear = q->rear;

if (rear == NULL) {
return -1;
}

return rear->data;
}

struct Queue* createQueue() {

struct Queue* q =
(struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}

struct Node* createNode(intnewdata) {

struct Node* newnode
= (struct Node*)malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->next = NULL;
returnnewnode;
}
int main( ) {
struct Queue* q = createQueue( );
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
enQueue(q, 20);
printf("Front value: %d\n", front(q));
printf("Rear value: %d\n", rear(q));
printQueue(q);
printf("Deleted value = %d\n", deQueue(q));
printf("Deleted value = %d\n", deQueue(q));
printQueue(q);
return 0;
}

Data Structure - Priority Queue

Priority Queue is more specialized data structure than Queue. Like ordinary queue,
priority queue has same method but with a major difference. In Priority queue items
are ordered by key value so that item with the lowest value of key is at front and
item with the highest value of key is at rear or vice versa. So we're assigned priority
to item based on its key value. Lower the value, higher the priority. Following are the
principal methods of a Priority Queue.
Basic Operations
 insert / enqueue − add an item to the rear of the queue.

Page 48 of 69
Data Structures and its Applications(B24CS302)

remove / dequeue − remove an item from the front of the queue.

Priority Queue Representation


We're going to implement Queue using array in this article. There is few more
operations supported by queue which are following.
 Peek − get the element at front of the queue.
 isFull − check if queue is full.
 isEmpty − check if queue is empty.
Insert / Enqueue Operation
Whenever an element is inserted into queue, priority queue inserts the item
according to its order. Here we're assuming that data with high value has low
priority.

Insert / Enqueue Operation

Whenever an element is inserted into queue, priority queue inserts the item
according to its order. Here we're assuming that data with high value has low
priority.

void insert(int data)

{
inti = 0;
if(!isFull())
{

Page 49 of 69
Data Structures and its Applications(B24CS302)

// if queue is empty, insert the data

if(itemCount == 0)
{
intArray[itemCount++] = data;
}
Else
{
// start from the right end of the queue
for(i = itemCount - 1; i>= 0; i-- )
{
// if data is larger, shift existing item to right end
if(data >intArray[i])
{
intArray[i+1] = intArray[i];
}
Else
{
break;
}
} // insert the data
intArray[i+1] = data;
itemCount++;
}
}
}

Remove / Dequeue Operation

Whenever an element is to be removed from queue, queue get the element using
item count. Once element is removed. Item count is reduced by one.

#include <stdio.h>
Page 50 of 69
Data Structures and its Applications(B24CS302)

#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
intintArray[MAX];
intitemCount = 0;
int peek( )
{
returnintArray[itemCount - 1];
}
boolisEmpty( )
{
returnitemCount == 0;
}
boolisFull( )
{
returnitemCount == MAX;
}
int size( )
{
returnitemCount;
}
void insert(int data)
{
inti = 0;
if(!isFull( ))
{
// if queue is empty, insert the data
if(itemCount == 0)
{
intArray[itemCount++] = data;
}
Else
{
// start from the right end of the queue
for(i = itemCount - 1; i>= 0; i-- )

{
// if data is larger, shift existing item to right end
if(data >intArray[i])
{
intArray[i+1] = intArray[i];
}
else{
break;
}
}
// insert the data
Page 51 of 69
Data Structures and its Applications(B24CS302)

intArray[i+1] = data;
itemCount++;
}
}
}
intremoveData( )
{
returnintArray[--itemCount];
}
int main( )
{
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);

if(isFull( ))
{
printf("Queue is full!\n");
}
// remove one item
intnum = removeData();
printf("Element removed: %d\n",num);
// As queue is full, elements will not be inserted.
insert(17);
insert(18);
printf("Element at front: %d\n",peek());
printf("----------------------\n");
printf("index : 5 4 3 2 1 0\n");
printf("----------------------\n");
printf("Queue: ");
while(!isEmpty())
{
int n = removeData();
printf("%d ",n);
}
}

Recursion in C

Page 52 of 69
Data Structures and its Applications(B24CS302)

Some computer programming languages allow a module or function to call itself. This
technique is known as recursion. In recursion, a function α either calls itself directly or
calls a function β that in turn calls the original function α. The function α is called
recursive function.
Example − a function calling itself.
int function(int value) {
if(value < 1)
return;
function(value - 1);

printf("%d ",value);
}
Example − a function that calls another function which in turn calls it again.
int function1(int value1) {
if(value1 < 1)
return;
function2(value1 - 1);
printf("%d ",value1);
}
int function2(int value2) {
function1(value2);
}

Properties
A recursive function can go infinite like a loop. To avoid infinite running of recursive
function, there are two properties that a recursive function must have −
 Base criteria − There must be at least one base criteria or condition, such that,
when this condition is met the function stops calling itself recursively.
 Progressive approach − The recursive calls should progress in such a way that
each time a recursive call is made it comes closer to the base criteria.

Implementation

Many programming languages implement recursion by means of stacks.

Page 53 of 69
Data Structures and its Applications(B24CS302)

Whenever a function (caller) calls another function (callee) or itself as callee, the caller
function transfers execution control to the callee. This transfer process may also involve
some data to be passed from the caller to the callee.
This implies, the caller function has to suspend its execution temporarily and resume
later when the execution control returns from the callee function. Here, the caller
function needs to start exactly from the point of execution where it puts itself on hold. It
also needs the exact same data values it was working on. For this purpose, an activation
record (or stack frame) is created for the caller function.

This activation record keeps the information about local variables, formal parameters,
return address and all information passed to the caller function.

Analysis of Recursion

One may argue why to use recursion, as the same task can be done with iteration. The
first reason is, recursion makes a program more readable and because of latest
enhanced CPU systems, recursion is more efficient than iterations.

Time Complexity
In case of iterations, we take number of iterations to count the time complexity.
Likewise, in case of recursion, assuming everything is constant, we try to figure out the
number of times a recursive call is being made. A call made to a function is Ο(1), hence
the (n) number of times a recursive call is made makes the recursive function Ο(n).

Space Complexity

Space complexity is counted as what amount of extra space is required for a module to
execute. In case of iterations, the compiler hardly requires any extra space. The
compiler keeps updating the values of variables used in the iterations. But in case of
recursion, the system needs to store activation record each time a recursive call is
made. Hence, it is considered that space complexity of recursive function may go higher
than that of a function with iteration.

Page 54 of 69
Data Structures and its Applications(B24CS302)

Example 1:

// C program for Recursion Data Structure finding factorial of a number

#include <stdio.h>
int factorial(int n) {
// Base case: factorial of 0 is 1
if (n == 0)
return 1;
// Recursive case: multiply n with factorial of (n-1)
return n * factorial(n - 1);
}
int main() {
// case 1
int number = 6;
printf("Number is: %d\n" , 6);
//case 2
if (number < 0) {
printf("Error: Factorial is undefined for negative numbers.\n");
return 1;
}
int result = factorial(number);
//print the output
printf("Factorial of %d is: %d\n", number, result);
return 0;
}
Output
Number is: 6
Factorial of 6 is: 720

Example 2 :
Tower of Hanoi
Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and
more than one rings is as depicted −

These rings are of different sizes and stacked upon in an ascending order, i.e. the
smaller one sits over the larger one. There are other variations of the puzzle where the
number of disks increase, but the tower count remains the same.
Rules
Page 55 of 69
Data Structures and its Applications(B24CS302)

The mission is to move all the disks to some another tower without violating the
sequence of arrangement. A few rules to be followed for Tower of Hanoi are −
 Only one disk can be moved among the towers at any given time.
 Only the "top" disk can be removed.
 No large disk can sit over a small disk.
Following is an animated representation of solving a Tower of Hanoi puzzle with three
disks.

Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This
presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.
Algorithm
To write an algorithm for Tower of Hanoi, first we need to learn how to solve this
problem with lesser amount of disks, say → 1 or 2. We mark three towers with
name, source, destination and aux (only to help moving the disks). If we have only one
disk, then it can easily be moved from source to destination peg.
If we have 2 disks −
 First, we move the smaller (top) disk to aux peg.
 Then, we move the larger (bottom) disk to destination peg.
 And finally, we move the smaller disk from aux to destination peg.

So now, we are in a position to design an algorithm for Tower of Hanoi with more than
two disks. We divide the stack of disks in two parts. The largest disk (n th disk) is in one
part and all other (n-1) disks are in the second part.
Our ultimate aim is to move disk n from source to destination and then put all other
(n1) disks onto it. We can imagine to apply the same in a recursive way for all given set
of disks.
The steps to follow are −
Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest

Page 56 of 69
Data Structures and its Applications(B24CS302)

Step 3 − Move n-1 disks from aux to dest

A recursive algorithm for Tower of Hanoi can be driven as follows −
START
Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF

END Procedure
STOP

#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
if(n == 1){
printf("Move disk 1 from %c to %c\n", from, to);
}
else{
hanoi(n-1, from, via, to);
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n-1, via, to, from);
}
}
int main() {
int n = 3;
char from = 'A';
char to = 'B';
char via = 'C';
//calling hanoi() method
hanoi(n, from, via, to);
}
Output
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Fibonacci Series Using Recursion

Page 57 of 69
Data Structures and its Applications(B24CS302)

Fibonacci series generates the subsequent number by adding two previous numbers.
Fibonacci series starts from two numbers F0 & F1. The initial values of F0 & F1 can be
taken 0, 1 or 1, 1 respectively.
Fibonacci series satisfies the following conditions −
Fn = Fn-1 + Fn-2
Hence, a Fibonacci series can look like this −
F8 = 0 1 1 2 3 5 8 13
or, this −
F8 = 1 1 2 3 5 8 13 21

Fibonacci Iterative Algorithm

First we try to draft the iterative algorithm for Fibonacci series.
Procedure Fibonacci(n)
declare f0, f1, fib, loop
set f0 to 0
set f1 to 1
<b>display f0, f1</b>
for loop ← 1 to n
fib ← f0 &plus; f1
f0 ← f1
f1 ← fib
<b>display fib</b>
end for
end procedure

Fibonacci Recursive Algorithm

Let us learn how to create a recursive algorithm Fibonacci series. The base criteria of
recursion.
START
Procedure Fibonacci(n)
declare f0, f1, fib, loop

set f0 to 0
set f1 to 1

display f0, f1

for loop ← 1 to n

fib ← f0 &plus; f1
f0 ← f1
f1 ← fib

display fib
end for
END

Page 58 of 69
Data Structures and its Applications(B24CS302)

Example 3:
#include <stdio.h>
intfibbonacci(int n)
{
if(n == 0)
{
return 0;
}
else if(n == 1)
{
return 1;
}
else
{
return (fibbonacci(n-1) + fibbonacci(n-2));
}
}
int main( )
{
int n = 5;
printf("Number is: %d", n);
printf("\nFibonacci series upto number %d are: ", n);
for(inti = 0;i<n;i++)
{
printf("%d ",fibbonacci(i));
}
}

Example 4:
//Recursive Binary search
#include <stdio.h>

// Recursive Binary Search Function

int binarySearch(int arr[], int low, int high, int key) {
if (low <= high) {
int mid = (low + high) / 2;

if (arr[mid] == key)
return mid; // element found
else if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key); // search left half
else
return binarySearch(arr, mid + 1, high, key); // search right half
}
return -1; // element not found
}

int main() {
Page 59 of 69
Data Structures and its Applications(B24CS302)

int arr[] = {2, 4, 6, 8, 10, 12, 14};

int n = sizeof(arr) / sizeof(arr[0]);
int key = 10;

int result = binarySearch(arr, 0, n - 1, key);

if (result != -1)
printf("Element %d found at index %d\n", key, result);
else
printf("Element %d not found in array\n", key);

return 0;
}
Applications of Recursion

Recursion is widely used to solve different kinds of problems from simple ones like
printing linked lists to being extensively used in AI. Some of the common uses of
recursion are:
 Tree-Graph Algorithms
 Mathematical Problems
 Divide and Conquer
 Dynamic Programming
 In Postfix to Infix Conversion
 Searching and Sorting Algorithms

Advantages of Recursion
The advantages of using recursive methods over other methods are:
 Recursion can effectively reduce the length of the code.
 Some problems are easily solved by using recursion like the tower of Hanoi and
tree traversals.
 Data structures like linked lists, trees, etc. are recursive by nature so recursive
methods are easier to implement for these data structures.

Disadvantages of Recursion
 As with almost anything in the world, recursion also comes with certain
limitations some of which are:
 Recursive functions make our program a bit slower due to function call overhead.
 Recursion functions always take extra space in the function call stack due to
separate stack frames.
 Recursion methods are difficult to understand and implement.

Recursive Implementation of Binary Search in C

Create a function that takes an array, left index, right index, and the key to be
searched.


Page 60 of 69
 Data Structures and its Applications(B24CS302)

Check if the subarray has elements to search i.e. left < right. If not, return -1.
Calculate the midpoint mid.


Compare the key with arr[mid].



If the key matches the middle element, return mid.



If the key is smaller, call the function again for the left subarray by passing right


= mid - 1.


If the key is larger, call the function again for the right subarray by passing left =
mid + 1.


The Maze Problem

Maze Solver in C
This project is a simple Maze Solver implemented in C using a recursive
backtracking algorithm. The program takes a 2D maze grid as input and finds a path
from the top-left corner to the bottom-right corner if it exists.
Features
 Recursive backtracking to explore all possible paths.
 Prints the solution path if one exists.
 Handles mazes represented as a 2D array with walls and open paths.
Maze Representation
 The maze is represented as a 2D grid where:
o 0 indicates a passable cell.
o 1 indicates a wall.
Example:
01000
01010
00010
11000
00010
Algorithm
The algorithm uses recursive backtracking to explore the maze:
1. Starts at the top-left corner of the maze.
2. Marks the current cell as part of the solution path.
3. Recursively tries to move in four directions: right, down, left, and up.
4. Backtracks if no valid path is found.
5. Stops when it reaches the bottom-right corner.

C implementation

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
const char direction[] = "DLRU";
constintdr[ ] = {1, 0, 0, -1};
constint dc[ ] = {0, -1, 1, 0};
Page 61 of 69
Data Structures and its Applications(B24CS302)

constint n = 4; // Define n as the size of the maze

boolisValid(int r, int c, int maze[n][n])
{
return r >= 0 && c >= 0 && r < n && c < n && maze[r][c];
}
void solve(int r, int c, int maze[n][n], char currentPath[], char ans[][100], int* count)
{
if (r == n - 1 && c == n - 1)
{
strcpy(ans[*count], currentPath);
(*count)++;
return;
}
maze[r][c] = 0;
for (inti = 0; i< 4; i++)
{
intnextr = r + dr[i];
intnextc = c + dc[i];

if (isValid(nextr, nextc, maze)) {

currentPath[strlen(currentPath)] = direction[i];
solve(nextr, nextc, maze, currentPath, ans, count);
currentPath[strlen(currentPath) - 1] = '\0';
}
}
maze[r][c] = 1;
}
voidfindPath(int maze[n][n])
{
if (maze[0][0] == 1) {
charcurrentPath[100];
charans[100][100];
int count = 0;
currentPath[0] = '\0';
solve(0, 0, maze, currentPath, ans, &count);

if (count == 0)
printf("-1");
else {
for (inti = 0; i< count; i++) {
printf("%s ", ans[i]);
}
}
}
}
int main( )
{
int maze[4][4] = { {1, 0, 0, 0},
Page 62 of 69
 Data Structures and its Applications(B24CS302)

{1, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 1} };
findPath(maze);
return 0;
}

Implementation of Multiple Stacks as Queues

When multiple stacks need to function as separate queues within a single memory
array, a strategic implementation is required. This can be done using fixed
partitioning or dynamic partitioning methods.
Here’s a detailed explanation and implementation:
1. Concept of Multiple Stacks as Queues
To implement multiple queues using stacks:
 Each queue uses two stacks.
o Stack 1 (Input Stack): Used for enqueue operations (pushing elements).
o Stack 2 (Output Stack): Used for dequeue operations (retrieving elements).
 Queues are managed independently.

2. Operations in Each Queue

1. Enqueue:
o Push the element into Stack 1.
2. Dequeue:
o If Stack 2 is empty, transfer all elements from Stack 1 to Stack 2.
o Pop the top element from Stack 2.

3. Implementation of Two Queues Using Stacks

//C implementation of two independent queues managed by stacks.

Code
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
// Structure to represent a stack
typedefstruct
{
intarr[MAX];
int top;
} Stack;
// Function to initialize a stack
void initStack(Stack *s)
{
s->top = -1;

Page 63 of 69
Data Structures and its Applications(B24CS302)

}
// Function to check if a stack is full
int isFull(Stack *s) {
return s->top == MAX – 1;
}
// Function to check if a stack is empty
int isEmpty(Stack *s) {
return s->top == -1;
}
// Function to push an element onto a stack
void push(Stack *s, int value)
{
if (isFull(s))
{
printf(“Stack Overflow\n”);
} else {
s->arr[++(s->top)] = value;
}
}
// Function to pop an element from a stack
int pop(Stack *s) {
if (isEmpty(s)) {
printf(“Stack Underflow\n”);
return -1;
} else {
return s->arr[(s->top)–];
}
}
// Function to get the top element of a stack
int peek(Stack *s) {
if (isEmpty(s)) {
printf(“Stack is empty\n”);
return -1;
} else {
return s->arr[s->top];
}
}
// Structure to represent a queue using two stacks
typedef struct {
Stack stack1;
Stack stack2;
} Queue;
// Initialize the queue
voidinitQueue(Queue *q) {
initStack(&(q->stack1));
initStack(&(q->stack2));
}
// Enqueue operation
Page 64 of 69
 Data Structures and its Applications(B24CS302)

void enqueue(Queue *q, int value) {

push(&(q->stack1), value);
printf(“Enqueued: %d\n”, value);
}
// Dequeue operation
int dequeue(Queue *q) {
if (isEmpty(&(q->stack2))) {
while (!isEmpty(&(q->stack1))) {
push(&(q->stack2), pop(&(q->stack1)));
}
}
return pop(&(q->stack2));
}
// Display elements in the queue
void displayQueue(Queue *q) {
// Transfer elements from stack1 to stack2 for printing
while (!isEmpty(&(q->stack1))) {
push(&(q->stack2), pop(&(q->stack1)));
}
printf(“Queue elements: “);
while (!isEmpty(&(q->stack2))) {
int value = pop(&(q->stack2));
printf(“%d “, value);
push(&(q->stack1), value);
}
printf(“\n”);
}
// Main function to demonstrate the working of multiple queues
int main( )
{
Queue queue1, queue2;
initQueue(&queue1);
initQueue(&queue2);
// Enqueue and dequeue operations for Queue 1
enqueue(&queue1, 10);
enqueue(&queue1, 20);
enqueue(&queue1, 30);
printf(“Dequeued from Queue 1: %d\n”, dequeue(&queue1));
displayQueue(&queue1);
// Enqueue and dequeue operations for Queue 2
enqueue(&queue2, 40);
enqueue(&queue2, 50);
printf(“Dequeued from Queue 2: %d\n”, dequeue(&queue2));
displayQueue(&queue2);
return 0;
}

4. Explanation of the Code

Page 65 of 69
 Data Structures and its Applications(B24CS302)

1. Stack Management:
o Each queue uses two stacks (stack1 and stack2).
o push and pop functions manage stack operations.
2. Queue Operations:
o enqueue: Pushes the element onto stack1.
o dequeue:
 Transfers all elements from stack1 to stack2 if stack2 is empty.
 Pops the top element from stack2.
3. Multiple Queues:
o Two queues (queue1 and queue2) are implemented independently, using
separate stack pairs.

Sample Output
Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued from Queue 1: 10
Queue elements: 20 30
Enqueued: 40
Enqueued: 50
Dequeued from Queue 2: 40
Queue elements: 50

6. Advantages of This Approach

 Efficient use of memory for multiple queues.
 Separation of queue logic using stacks simplifies debugging.
 Suitable for scenarios where the queue size grows dynamically.

7. Applications of Multiple Stacks as Queues

 Process Scheduling: Managing independent task queues.
 Simulation: Modeling scenarios requiring FIFO behavior.
 Communication Systems: Handling multiple message queues in parallel.
This implementation provides a robust framework to manage multiple stack-based
queues within a shared memory space.

Programming Examples
Example1 :
//factorial using recursion
#include <stdio.h>
int factorial(int n) {
if (n == 0) // Base case
return 1;
else
return n * factorial(n - 1); // Recursive call
}
Page 66 of 69
Data Structures and its Applications(B24CS302)

int main( ) {
intnum = 5;
printf("Factorial of %d is %d\n", num, factorial(num));
return 0;
}
Example 2 :
Code: Evaluating a Prefix Expression
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

// Stack structure
typedefstruct {
int data[MAX];
int top;
} Stack;

// Stack operations
void push(Stack *stack, int value) {
stack->data[++stack->top] = value;
}

int pop(Stack *stack) {

return stack->data[stack->top--];
}
// Function to evaluate a prefix expression
int evaluatePrefix(char* expression) {
Stack stack;
stack.top = -1;

int length = strlen(expression);

// Traverse the expression from right to left
for (int i = length - 1; i>= 0; i--) {
// Skip spaces
if (expression[i] == ' ') continue;

// If the character is an operand, push it onto the stack

if (isdigit(expression[i])) {
int operand = 0;
int multiplier = 1;

// Handle multi-digit numbers

while (i>= 0 &&isdigit(expression[i])) {
operand = (expression[i] - '0') * multiplier + operand;
multiplier *= 10;
Page 67 of 69
Data Structures and its Applications(B24CS302)

i--;
}
i++; // Adjust for the extra decrement
push(&stack, operand);
}
// If the character is an operator, pop two operands and apply the operator
else {
int operand1 = pop(&stack);
int operand2 = pop(&stack);

switch (expression[i]) {
case '+': push(&stack, operand1 + operand2); break;
case '-': push(&stack, operand1 - operand2); break;
case '*': push(&stack, operand1 * operand2); break;
case '/': push(&stack, operand1 / operand2); break;
}
}
}
// The final result is the only element left in the stack
return pop(&stack);
}
int main() {
char expression[] = "- + * 2 3 * 5 4 9"; // Example prefix expression
printf("Prefix Expression: %s\n", expression);
int result = evaluatePrefix(expression);
printf("Result: %d\n", result);
return 0;
}

Page 68 of 69