c-program-multi-stack-in-datastructure

admin

1/25/2025

#c-program-multi-stack-in-datastructure

Go Back

Implementation of Multi-Stack Using C in Data Structure

Introduction

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.


What is a Multi-Stack in Data Structures?

A multi-stack refers to the implementation of multiple stacks in one array. For example:

  • Instead of using multiple arrays to represent each stack, you divide a single array into separate regions for different stacks.
  • This technique ensures optimal use of available memory and allows dynamic allocation of elements within each stack.

Benefits of Multi-Stack Implementation:

  1. Efficient Memory Usage: No need to allocate multiple arrays, reducing memory waste.
  2. Scalable Design: The number of stacks and their sizes can be adjusted dynamically.
  3. Optimized for Space: Prevents memory overflow caused by fixed array sizes.

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);
}

Method 2: Advanced Multi-Stack Implementation

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;
}

Multi-Stack Operations

  1. Push: Adds a value to the selected stack.
  2. Pop: Removes the top value from the selected stack.
  3. Display: Shows all elements in the selected stack.
  4. Exit: Exits the program.

Conclusion

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.

#c-program-multi-stack-in-datastructure