PROGRAM 15

Write a program to implement Stack using Array and Linked List

Stack Using Array
Algorithm (Stack Using Array)
1. Start
2. Initialize stack array and set top = -1
3. Display menu of operations
4. For push operation, increment top and insert element
5. For pop operation, remove element at top and decrement top
6. Display stack elements
7. Repeat until exit
8. Stop
Time Complexity
 Time Complexity for Push (Insertion): O(1)
o Reason: You are simply placing an element at the current top index and
incrementing the index. There is no shifting or traversing required.
 Time Complexity for Pop (Deletion): O(1)
o Reason: You just decrement the top index to remove the element from view.
No traversal is needed.
 Time Complexity for Display: O(n)
o Reason: To print the entire stack, you must visit every element from the top
down to the 0th index.
Space Complexity:
 Auxiliary Space Complexity: O(1) per operation.
o Reason: The operations themselves do not require any extra memory. (Note:
The total space complexity to store the stack array itself is O(n), where n is the
maximum capacity).
C Program
#include <stdio.h>
int stack[5], top = -1;
void push(int val) {
if (top == 4) printf("Stack Overflow!\n");
else stack[++top] = val;
}
void pop() {
if (top == -1) printf("Stack Underflow!\n");
else printf("Popped: %d\n", stack[top--]);
}
void display() {
if (top == -1) {
printf("Stack is empty!\n");
return;
}
 printf("Stack (Top to Bottom): ");
for (int i = top; i >= 0; i--) printf("%d ", stack[i]);
printf("\n");
}
int main() {
int choice, val;
while(1) {
printf("\[Link] [Link] [Link] [Link] | Choice: ");
scanf("%d", &choice);
if (choice == 1) {
printf("Enter value: ");
scanf("%d", &val);
push(val);
}
else if (choice == 2) pop();
else if (choice == 3) display();
else break;
}
return 0;
}
Output

Stack Using Linked List

Algorithm (Stack Using Linked List)
1. Start
2. Initialize top pointer as NULL
3. Insert elements at the beginning for push
4. Delete elements from the beginning for pop
5. Display stack elements
6. Repeat until exit
7. Stop
Time Complexity
 Time Complexity for Push (Insertion): O(1)
 o Reason: You are simply creating a new node and making it the new top by
pointing it to the old top. No traversal is needed.
 Time Complexity for Pop (Deletion): O(1)
o Reason: You just move the top pointer to the next node and free the old top.
Again, no traversal is required.
 Time Complexity for Display: O(n)
o Reason: To print the whole stack, you must traverse the linked list from the top
node down to the end (NULL).
Space Complexity:
 Auxiliary Space Complexity: O(1) per operation.
o Reason: Pushing and popping only require a couple of temporary pointers,
regardless of how many elements are in the stack.
C Program
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
} *top = NULL;
void push(int val) {
struct Node* nn = (struct Node*)malloc(sizeof(struct Node));
nn->data = val;
nn->next = top;
top = nn;
}
void pop() {
if (top == NULL) {
printf("Stack Underflow!\n");
return;
}
struct Node* temp = top;
printf("Popped: %d\n", temp->data);
top = top->next;
free(temp);
}
void display() {
struct Node* t = top;
printf("Stack (Top to Bottom): ");
while (t != NULL) {
printf("%d -> ", t->data);
t = t->next;
}
printf("NULL\n");
}
int main() {
int choice, val;
while(1) {
printf("\[Link] [Link] [Link] [Link] | Choice: ");
scanf("%d", &choice);
if (choice == 1) {
printf("Enter value: ");
scanf("%d", &val);
push(val);
}
else if (choice == 2) pop();
else if (choice == 3) display();
else break;
}
return 0;
}
Output
 PROGRAM 16
Write a program to reverse a string using Stack
Algorithm
1. Start
2. Read the input string
3. Initialize an empty stack
4. Push each character of the string onto the stack
5. Pop characters from the stack and store them back into the string
6. Display the reversed string
7. Stop

Time Complexity
 Best Case Time Complexity: O(n)
 Average Case Time Complexity: O(n)
 Worst Case Time Complexity: O(n)
o Reason: The time complexity is exactly the same for all cases. You must
visit every character in the string once to push it onto the stack (n
operations) and visit the stack exactly n times to pop the characters back
out. Therefore, it will always take linear time based on the length of the
string (n).
Space Complexity:
 Auxiliary Space Complexity: O(n)
o Reason: You have to store every single character of the string inside the
stack at the same time. If your string has 100 characters, your stack
needs enough memory to hold 100 characters.

C Program
#include <stdio.h>
#include <string.h>

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

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

char pop() { return stack[top--]; }
int main() {
char str[100];
printf("Enter a string: ");
scanf("%s", str);
int len = strlen(str);
 for(int i = 0; i < len; i++)
push(str[i]);
for(int i = 0; i < len; i++)
str[i] = pop();
printf("Reversed string: %s\n", str);
return 0;
}
Output
 PROGRAM 17
Write a program to check whether an expression has Balanced Parenthesis
Algorithm
1. Start
2. Read the input expression
3. Initialize an empty stack
4. For each character in the expression:
• If opening bracket, push onto stack
• If closing bracket: – If stack is empty, expression is unbalanced – Pop and
check for matching pair
5. If stack is empty after scanning, expression is balanced
6. Else expression is unbalanced
7. Stop
Time Complexity
 Best Case Time Complexity: O(n)
 Average Case Time Complexity: O(n)
 Worst Case Time Complexity: O(n)
o Reason: You must scan the expression exactly once from left to right.
For each character, pushing to or popping from the stack takes O(1)
time. Therefore, the time taken is directly proportional to the length of the
string (n).
 Note on Early Exit: If you encounter a closing bracket when the stack is
empty, or a mismatched pair, the algorithm can stop early. However, in Big-O
notation, we still consider the worst-case scenario where it scans the whole
string, so it remains O(n).
Space Complexity:
 Auxiliary Space Complexity: O(n)
o Reason: In the worst-case scenario (an expression with all opening
brackets like {{{{{{{{), you will end up pushing every single character onto
the stack. Thus, the stack requires space proportional to the length of
the string.
C Program
#include <stdio.h>
#include <string.h>
char stack[100];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? '\0' : stack[top--]; }
int isMatch(char a, char b) {
return (a == '(' && b == ')') ||
(a == '{' && b == '}') ||
 (a == '[' && b == ']');
}
int main() {
char exp[100];
printf("Enter expression: ");
scanf("%s", exp);
for (int i = 0; i < strlen(exp); i++) {
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') {
push(exp[i]);
}
else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
if (top == -1 || !isMatch(pop(), exp[i])) {
printf("Result: Unbalanced\n");
return 0; // Exit early if unbalanced
}
}
}
if (top == -1)
printf("Result: Balanced\n");
else
printf("Result: Unbalanced\n");
return 0;
}
Output
 PROGRAM 18
Write a program to convert Infix expression to Prefix and Postfix
Algorithm
1. Start
2. Read the infix expression
3. Convert infix to postfix using stack
4. Reverse infix and convert to postfix for prefix conversion
5. Display postfix and prefix expressions
6. Stop
Time Complexity
 Best, Average, and Worst Case Time Complexity: O(n)
o Reason: Every character in the expression of length n is processed a constant
number of times. It is pushed to the stack at most once and popped at most
once. The reversing functions also take linear O(n) time. Therefore, the overall
time is directly proportional to the length of the string.
Space Complexity:
 Auxiliary Space Complexity: O(n)
o Reason: You need an extra stack to temporarily hold the operators (and
parentheses) as you scan the expression, which could potentially grow to size
n in the worst case. You also need space to store the resulting output strings.
C Program
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char stack[100];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }
int prec(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return 0;
}
void reverse(char* str) {
int l = 0, r = strlen(str) - 1;
while (l < r) {
char t = str[l]; str[l] = str[r]; str[r] = t;
l++; r--;
}
for (int i = 0; str[i]; i++) {
if (str[i] == '(') str[i] = ')';
else if (str[i] == ')') str[i] = '(';
 }
}
void inToPost(char* in, char* post) {
int i = 0, j = 0;
top = -1;
while (in[i]) {
if (isalnum(in[i])) post[j++] = in[i];
else if (in[i] == '(') push(in[i]);
else if (in[i] == ')') {
while (top != -1 && stack[top] != '(') post[j++] = pop();
pop(); // Remove '('
} else {
while (top != -1 && prec(stack[top]) >= prec(in[i])) post[j++] = pop();
push(in[i]);
}
i++;
}
while (top != -1) post[j++] = pop();
post[j] = '\0';
}

int main() {
char in[100], post[100], pre[100], temp[100];
printf("Enter Infix expression: ");
scanf("%s", in); inToPost(in, post);
printf("Postfix: %s\n", post);
strcpy(temp, in);
reverse(temp);
inToPost(temp, pre
reverse(pre);
printf("Prefix: %s\n", pre);
return 0;
}
Output
 PROGRAM 19
Write a program to implement Linear Queue using Array and Linked List
Linear Queue Using Array
Algorithm (Linear Queue Using Array)
1. Start
2. Initialize front = -1 and rear = -1
3. For enqueue operation:
• Increment rear and insert element
• If front is -1, set front = 0
4. For dequeue operation:
• Remove element at front and increment front
5. Display elements from front to rear
6. Repeat until exit
7. Stop
Time Complexity
 Time Complexity for Enqueue (Insertion): O(1)
o Reason: You only need to increment the rear index and place the element
there. No shifting is required.
 Time Complexity for Dequeue (Deletion): O(1)
o Reason: You simply increment the front index to "remove" the element from
the valid queue range.
 Time Complexity for Display: O(n)
o Reason: To print the queue, you must iterate from the front index to the rear
index.
Space Complexity:
 Auxiliary Space Complexity: O(1) per operation.
o Reason: The enqueue and dequeue operations themselves do not require any
extra memory beyond a few standard variables.
C Program
#include <stdio.h>
int queue[5], front = -1, rear = -1;
void enqueue(int val) {
if (rear == 4) printf("Queue Overflow!\n");
else {
if (front == -1) front = 0;
queue[++rear] = val;
}
}
void dequeue() {
if (front == -1 || front > rear) printf("Queue Underflow!\n");
else printf("Dequeued: %d\n", queue[front++]);
}
void display() {
 if (front == -1 || front > rear) {
printf("Queue is empty!\n");
return;
}
printf("Queue: ");
for (int i = front; i <= rear; i++) printf("%d ", queue[i]);
printf("\n");
}
int main() {
int choice, val;
while(1) {
printf("\[Link] [Link] [Link] [Link] | Choice: ");
scanf("%d", &choic;
if (choice == 1) {
printf("Enter value: ");
scanf("%d", &val);
enqueue(val);
}
else if (choice == 2) dequeue();
else if (choice == 3) display();
else break;
}
return 0;
}

Output
Linear Queue Using Linked List
Algorithm (Linear Queue Using Linked List)
1. Start
2. Initialize front and rear pointers as NULL
3. For enqueue operation: • Create a new node
• Add it at the rear
4. For dequeue operation: • Remove node from front 101
5. Display all nodes from front to rear
6. Repeat until exit
7. Stop
Time Complexity
 Time Complexity for Enqueue (Insertion): O(1)
o Reason: Because we maintain a rear pointer, adding a new node to the end of
the line happens instantly. We don't have to traverse the list to find the end.
 Time Complexity for Dequeue (Deletion): O(1)
o Reason: Because we maintain a front pointer, removing the first node
happens instantly. We just move the front pointer to the next node in line.
 Time Complexity for Display: O(n)
o Reason: To print the queue, you must visit every node starting from the front
until you reach the rear (which points to NULL).
Space Complexity:
 Auxiliary Space Complexity: O(1) per operation.
o Reason: Enqueuing and dequeuing only require adjusting a couple of
temporary pointers, regardless of how many elements are currently in the
queue.
C Program
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
} *front = NULL, *rear = NULL;
void enqueue(int val) {
struct Node* nn = (struct Node*)malloc(sizeof(struct Node));
nn->data = val;
nn->next = NULL;
if (rear == NULL) {
front = rear = nn;
} else {
rear->next = nn;
rear = nn;
}
}
void dequeue() {
if (front == NULL) {
printf("Queue Underflow!\n");
 return;
}
struct Node* temp = front;
printf("Dequeued: %d\n", temp->data);
front = front->next;
if (front == NULL) rear = NULL;
free(temp);
}
void display() {
struct Node* t = front;
printf("Queue: ");
while (t != NULL) {
printf("%d -> ", t->data);
t = t->next;
}
printf("NULL\n");
}
int main() {
int choice, val;
while(1) {
printf("\[Link] [Link] [Link] [Link] | Choice: ");
scanf("%d", &choice);
if (choice == 1) {
printf("Enter value: ");
scanf("%d", &val);
enqueue(val);
}
else if (choice == 2) dequeue();
else if (choice == 3) display();
else break;
}
return 0;
}
Output
 PROGRAM 20
Write a program to implement Circular Queue using Array and Linked List
Circular Queue Using Array
Algorithm (Circular Queue Using Array)
1. Start
2. Initialize front = -1 and rear = -1
3. For enqueue operation:
• If queue is full, display overflow
• Else update rear using modulo operation
• Insert element at rear
• If front is -1, set front = 0
4. For dequeue operation:
• If queue is empty, display underflow
• Else remove element at front
• Update front using modulo operation
5. Display elements from front to rear circularly
6. Repeat until exit
7. Stop
Time Complexity
 Time Complexity for Enqueue (Insertion): O(1)
o Reason: You only need to calculate the new rear index using the modulo
operator (%) and place the element there. No shifting is required, even
when wrapping around to the beginning of the array.
 Time Complexity for Dequeue (Deletion): O(1)
o Reason: You simply calculate the new front index using the modulo
operator to "remove" the element.
 Time Complexity for Display: O(n)
o Reason: To print the queue, you must iterate from the front index
circularly to the rear index, visiting each element once.
Space Complexity:
 Auxiliary Space Complexity: O(1) per operation.
o Reason: The enqueue and dequeue operations themselves do not
require any extra memory, just index calculations.
C Program
#include <stdio.h>
#define SIZE 5

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

void enqueue(int val) {

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

void dequeue() {
if (front == -1) {
printf("Queue Underflow!\n");
} else {
printf("Dequeued: %d\n", queue[front]);
if (front == rear) front = rear = -1; // Reset if queue becomes empty
else front = (front + 1) % SIZE;
}
}

void display() {
if (front == -1) {
printf("Queue is empty!\n");
return;
}
printf("Queue: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
}
printf("\n");
}

int main() {
int choice, val;
while(1) {
printf("\[Link] [Link] [Link] [Link] | Choice: ");
scanf("%d", &choice);

if (choice == 1) {
printf("Enter value: ");
scanf("%d", &val);
enqueue(val);
 }
else if (choice == 2) dequeue();
else if (choice == 3) display();
else break;
}
return 0;
}
Output
Circular Queue Using Linked List
Algorithm (Circular Queue Using Linked List)
1. Start
2. Initialize front and rear pointers as NULL
3. For enqueue operation:
• Create a new node
• Insert it at the rear
• Make rear-next point to front
4. For dequeue operation:
• Remove the node from the front
• Update front pointer
• Update rear-next
5. Display elements by traversing circularly
6. Repeat until exit
7. Stop
Time Complexity
 Time Complexity for Enqueue (Insertion): O(1)
o Reason: Because you maintain a rear pointer, you can instantly add a
new node to the end of the queue. The only extra step compared to a
linear queue is making the new rear's next pointer loop back to the front,
which also takes constant time.
 Time Complexity for Dequeue (Deletion): O(1)
o Reason: You instantly remove the node at the front pointer and move
front to the next node. You then just update the rear->next to point to this
new front.
 Time Complexity for Display: O(n)
o Reason: To print the queue, you must start at front and traverse the list
until your temporary pointer loops back around to front.
Space Complexity:
 Auxiliary Space Complexity: O(1) per operation.
o Reason: Operations only require moving a few pointers around,
regardless of the size of the queue.
C Program
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
} *front = NULL, *rear = NULL;

void enqueue(int val) {

 struct Node* nn = (struct Node*)malloc(sizeof(struct Node));
nn->data = val;
if (front == NULL) {
front = rear = nn;
rear->next = front; // Point back to itself
} else {
rear->next = nn;
rear = nn;
rear->next = front; // Maintain circular link
}
}
void dequeue() {
if (front == NULL) {
printf("Queue Underflow!\n");
return;
}
struct Node* temp = front;
printf("Dequeued: %d\n", temp->data);
if (front == rear) {
front = rear = NULL;
} else {
front = front->next;
rear->next = front; // Update rear to point to new front
}
free(temp);
}
void display() {
if (front == NULL) {
printf("Queue is empty!\n");
return;
}
struct Node* t = front;
printf("Queue: ");
do {
printf("%d -> ", t->data);
t = t->next;
} while (t != front);
printf("(FRONT)\n");
}
int main() {
int choice, val;
 while(1) {
printf("\[Link] [Link] [Link] [Link] | Choice: ");
scanf("%d", &choice);
if (choice == 1) {
printf("Enter value: ");
scanf("%d", &val);
enqueue(val);
}
else if (choice == 2) dequeue();
else if (choice == 3) display();
else break;
}
return 0;
}
Output
 PROGRAM 21
Write a program to implement Deque using Array and Linked List
Deque Using Array
Algorithm (Deque Using Array)
1. Start
2. Initialize front = -1 and rear = -1
3. For insertion at front or rear, adjust indices accordingly
4. For deletion, remove elements from front or rear
5. Display elements of deque
6. Repeat until exit
7. Stop
Time Complexity
 Time Complexity for Insertion:
o At Front: O(1)
o At Rear: O(1)
 Time Complexity for Deletion:
o At Front: O(1)
o At Rear: O(1)
 Time Complexity for Display: O(n)
Space Complexity:
 Auxiliary Space Complexity: O(1) per operation.
o Reason: Like the other array structures, it only requires basic index calculations.
C Program
#include <stdio.h>
#define SIZE 5
int deque[SIZE], front = -1, rear = -1;
void insertFront(int val) {
if ((front == 0 && rear == SIZE - 1) || front == rear + 1) {
printf("Deque Overflow!\n"); return;
}
if (front == -1) front = rear = 0;
else front = (front == 0) ? SIZE - 1 : front - 1;
deque[front] = val;
}
void insertRear(int val) {
if ((front == 0 && rear == SIZE - 1) || front == rear + 1) {
printf("Deque Overflow!\n"); return;
}
if (front == -1) front = rear = 0;
else rear = (rear == SIZE - 1) ? 0 : rear + 1;
deque[rear] = val;
}
void deleteFront() {
if (front == -1) { printf("Deque Underflow!\n"); return; }
printf("Deleted Front: %d\n", deque[front]);
if (front == rear) front = rear = -1;
 else front = (front == SIZE - 1) ? 0 : front + 1;
}
void deleteRear() {
if (front == -1) { printf("Deque Underflow!\n"); return; }
printf("Deleted Rear: %d\n", deque[rear]);
if (front == rear) front = rear = -1;
else rear = (rear == 0) ? SIZE - 1 : rear - 1;
}
void display() {
if (front == -1) { printf("Deque is empty!\n"); return; }
printf("Deque: ");
int i = front;
while (1) {
printf("%d ", deque[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
}
printf("\n");
}
int main() {
int choice, val;
while(1) {
printf("\[Link] [Link] [Link] [Link] [Link] [Link] | Choice: ");
scanf("%d", &choice);
if (choice == 1) { printf("Val: "); scanf("%d", &val); insertFront(val); }
else if (choice == 2) { printf("Val: "); scanf("%d", &val); insertRear(val); }
else if (choice == 3) deleteFront();
else if (choice == 4) deleteRear();
else if (choice == 5) display();
else break;
}
return 0;
}
Output