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.

Multi-Stack Time and space complexity 

Time Complexity:

    pushA = O(1)
    popA = O(1)
    showA = O(MAX)
    pushB = O(1)
    popB = O(1)
    showB = O(MAX)
Space Complexity: O(MAX), as we are using a single array of size MAX to hold elements for both stacks.

This approach is efficient with respect to time complexity for individual operations (push, pop), and the space complexity is linear with respect to the size of the array used.

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.