c-program-multi-stack-in-datastructure
admin
#c-program-multi-stack-in-datastructure
Are you searching for an efficient solution to implement multiple stacks within a single array? This article will guide you through the implementation of multi-stack using C, a technique widely used in data structures to optimize memory utilization.
When you try to manage multiple stacks using a single array, you can avoid the limitations of fixed-size arrays. This is especially beneficial for scenarios where dynamic memory allocation isn't feasible or preferred. Below, we’ll explore the concept of multi-stacks, their advantages, and how to implement them effectively in C.
A multi-stack refers to the implementation of multiple stacks in one array. For example:
Method 1: Basic Multi-Stack Implementation
Using a single array, this method demonstrates the implementation of two stacks, Stack A and Stack B, within the same array. Stack A grows from left to right, while Stack B grows from right to left. Below is the code for Method 1:
#include<stdio.h>
#define MAX 10
int stack[MAX], topA = -1, topB = MAX;
void pushA(int val) {
if (topA + 1 == topB) {
printf("\noverflow in StackA");
return;
}
stack[++topA] = val;
}
int popA() {
if (topA == -1) {
printf("\nunderflow in StackA");
return -999;
}
return stack[topA--];
}
void showA() {
if (topA == -1) {
printf("\nstackA is empty");
return;
}
for (int i = topA; i >= 0; i--)
printf(" %d", stack[i]);
}
void pushB(int val) {
if (topB - 1 == topA) {
printf("\noverflow in StackB");
return;
}
stack[--topB] = val;
}
int popB() {
if (topB == MAX) {
printf("\nunderflow in StackB");
return -999;
}
return stack[topB++];
}
void showB() {
if (topB == MAX) {
printf("\nstackB is empty");
return;
}
for (int i = topB; i < MAX; i++)
printf(" %d", stack[i]);
}
void main() {
int no, ch;
do {
printf("\n 1 pushA");
printf("\n 2 popA");
printf("\n 3 showA");
printf("\n 4 pushB");
printf("\n 5 popB");
printf("\n 6 showB");
printf("\n 0 exit");
printf("\n enter your Choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("\n Enter no : ");
scanf("%d", &no);
pushA(no);
break;
case 2:
no = popA();
if (no != -999)
printf("\n % d popped ", no);
break;
case 3:
showA();
break;
case 4:
printf("\n Enter no : ");
scanf("%d", &no);
pushB(no);
break;
case 5:
no = popB();
if (no != -999)
printf("\n % d popped ", no);
break;
case 6:
showB();
break;
case 0:
break;
default:
printf("\n invalid choice");
}
} while (ch != 0);
}
This method provides a scalable way to manage multiple stacks within a single array. The total size of the array is divided equally among the stacks, and each stack's operations (push, pop, and display) are managed separately. Here is the implementation:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Total size of the array
#define STACK_COUNT 3 // Number of stacks
int stack[MAX];
int top[STACK_COUNT];
int stackStart[STACK_COUNT];
int stackEnd[STACK_COUNT];
// Function to initialize stacks
void initializeStacks(int stackSize) {
for (int i = 0; i < STACK_COUNT; i++) {
stackStart[i] = i * stackSize;
stackEnd[i] = (i + 1) * stackSize - 1;
top[i] = stackStart[i] - 1; // Initialize top for each stack
}
}
// Push operation
void push(int stackNumber, int value) {
if (stackNumber < 0 || stackNumber >= STACK_COUNT) {
printf("Invalid stack number!\n");
return;
}
if (top[stackNumber] == stackEnd[stackNumber]) {
printf("Stack %d is full (Overflow)!\n", stackNumber);
return;
}
top[stackNumber]++;
stack[top[stackNumber]] = value;
printf("Pushed %d to stack %d\n", value, stackNumber);
}
// Pop operation
int pop(int stackNumber) {
if (stackNumber < 0 || stackNumber >= STACK_COUNT) {
printf("Invalid stack number!\n");
return -9999;
}
if (top[stackNumber] < stackStart[stackNumber]) {
printf("Stack %d is empty (Underflow)!\n", stackNumber);
return -9999;
}
int value = stack[top[stackNumber]];
top[stackNumber]--;
return value;
}
// Display operation for a specific stack
void display(int stackNumber) {
if (stackNumber < 0 || stackNumber >= STACK_COUNT) {
printf("Invalid stack number!\n");
return;
}
if (top[stackNumber] < stackStart[stackNumber]) {
printf("Stack %d is empty!\n", stackNumber);
return;
}
printf("Stack %d: ", stackNumber);
for (int i = stackStart[stackNumber]; i <= top[stackNumber]; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}
int main() {
int stackSize = MAX / STACK_COUNT;
initializeStacks(stackSize);
int choice, stackNumber, value;
while (1) {
printf("\nMulti-Stack Operations:\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter stack number (0 to %d): ", STACK_COUNT - 1);
scanf("%d", &stackNumber);
printf("Enter value to push: ");
scanf("%d", &value);
push(stackNumber, value);
break;
case 2:
printf("Enter stack number (0 to %d): ", STACK_COUNT - 1);
scanf("%d", &stackNumber);
value = pop(stackNumber);
if (value != -9999)
printf("Popped value: %d from stack %d\n", value, stackNumber);
break;
case 3:
printf("Enter stack number (0 to %d): ", STACK_COUNT - 1);
scanf("%d", &stackNumber);
display(stackNumber);
break;
case 4:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}
By using arrays for multi-stack implementation, we can efficiently utilize memory and handle multiple stacks within a single structure. Method 1 demonstrates a simple two-stack implementation, while Method 2 expands the concept to multiple stacks with dynamic allocation within a single array.
This approach is highly useful in applications where multiple stacks are required, such as expression evaluation, memory management, and more.