Multiple Stacks

 

📚 MULTIPLE STACKS (Using Arrays)

✨ What are Multiple Stacks?

  • Multiple stacks mean managing two or more stacks inside a single array.

  • Purpose: To save space and share memory better instead of using separate arrays for each stack.

✅ HOW TO IMPLEMENT MULTIPLE STACKS IN ARRAYS?

There are two ways:

TypeExplanation
1. Fixed DivisionDivide array into fixed parts for each stack. Each stack gets its own block. Simple but can waste memory.
2. Dynamic DivisionAllow stacks to grow toward each other. More efficient and avoids memory wastage.

1️⃣ Fixed Division (Simple Method)

Suppose array size = 10:

  • Stack 1 → indexes 0 to 4

  • Stack 2 → indexes 5 to 9

Each stack behaves independently within its section.

Limitations: One stack may overflow even if other has free space.

2️⃣ Dynamic Sharing (Best Method)

  • Stack 1 grows from left to right.

  • Stack 2 grows from right to left.

  • Overflow occurs only if top1 + 1 == top2.





C Program two stacks in an array

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

#define SIZE 10

int arr[SIZE];
int top1 = -1;
int top2 = SIZE;

// Function to push in Stack 1
void push1(int value) {
    if (top1 + 1 == top2) {
         printf("Stack 1 Overflow!\n");
        
    } else {
         top1++;
        arr[top1] = value;
    }
}

// Function to push in Stack 2
void push2(int value) {
    if (top1 + 1 == top2) {
        printf("Stack 2 Overflow!\n");
           } else {
         top2--;
        arr[top2] = value;
    }
}

// Function to pop from Stack 1
int pop1() {
    if (top1 ==-1) {
        printf("Stack 1 Underflow!\n");
        return -1;
       
    } else {
         int value = arr[top1];
        top1--;
        return value;
    }
}

// Function to pop from Stack 2
int pop2() {
    if (top2 == SIZE) {
        printf("Stack 2 Underflow!\n");
        return -1;
          } 
    else {
        int value = arr[top2];
        top2++;
        return value;
    }
}

// Function to display Stack 1
void display1() {
    if (top1 >= 0) {
        printf("Stack 1 elements: ");
        for (int i = 0; i <= top1; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    } else {
        printf("Stack 1 is empty!\n");
    }
}

// Function to display Stack 2
void display2() {
    if (top2 < SIZE) {
        printf("Stack 2 elements: ");
        for (int i = top2; i < SIZE; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    } else {
        printf("Stack 2 is empty!\n");
    }
}

int main() {
    int choice, stackNumber, value;

    while (1) {
        printf("\n--- Menu ---\n");
        printf("1. Push into Stack 1\n");
        printf("2. Push into Stack 2\n");
        printf("3. Pop from Stack 1\n");
        printf("4. Pop from Stack 2\n");
        printf("5. Display Stack 1\n");
        printf("6. Display Stack 2\n");
        printf("7. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value to push into Stack 1: ");
                scanf("%d", &value);
                push1(value);
                break;
            case 2:
                printf("Enter value to push into Stack 2: ");
                scanf("%d", &value);
                push2(value);
                break;
            case 3:
                value = pop1();
                if (value != -1)
                    printf("Popped from Stack 1: %d\n", value);
                break;
            case 4:
                value = pop2();
                if (value != -1)
                    printf("Popped from Stack 2: %d\n", value);
                break;
            case 5:
                display1();
                break;
            case 6:
                display2();
                break;
            case 7:
                printf("Exiting program.\n");
                exit(0);
            default:
                printf("Invalid choice! Try again.\n");
        }
    }

    return 0;
}

📚 Implementing More than Two Stacks in an Array

You already know:
✅ 1 array + 2 stacks = can be managed by growing from opposite ends (left to right and right to left).
But if you want more than two stacks (say 3, 4, or k stacks), things become trickier.

✨ There are mainly TWO Ways

MethodIdeaDifficultyMemory Efficiency
1. Fixed PartitioningDivide array into fixed equal parts for each stack.EasyWastes space
2. Flexible (Dynamic) PartitioningUse extra arrays (next[], top[]) to link free spaces dynamically.HardVery Efficient

1️⃣ FIXED PARTITIONING (Simple Method)

  • Divide array into k equal parts.

  • Each stack is allocated a fixed region.

  • Manage each stack separately in its region.

Example:
If array size = 100 and 4 stacks:

  • Stack 1: 0-24

  • Stack 2: 25-49

  • Stack 3: 50-74

  • Stack 4: 75-99

Each stack has its own top pointer initialized to one less than its start index.

✅ Algorithm (Fixed Partition)

For each stack i:

  • start[i] → starting index of stack i

  • end[i] → ending index of stack i

  • top[i] → initially start[i] - 1

PUSH Operation:

  • Check if top[i] < end[i]

  • If yes, increment top[i] and insert element.

POP Operation:

  • Check if top[i] >= start[i]

  • If yes, pop element and decrement top[i].

📌 Drawbacks of Fixed Partitioning

  • Suppose Stack 1 fills up and Stack 2 is empty: Stack 1 can't use free space of Stack 2.

  • So not memory efficient if number of stacks is large or usage is uneven.

2️⃣ FLEXIBLE PARTITIONING (Advanced Method)

  • Dynamic allocation inside array.

  • Use 3 arrays:

    • arr[] → Actual data

    • top[] → Top index for each stack

    • next[] → Helps in linking free spaces

  • Also maintain a free pointer which points to the next free index.

This method is called k Stacks in a Single Array dynamically.

Advanced but very efficient.

🚀 HOW FLEXIBLE PARTITIONING WORKS?

Suppose you have:

  • arr[10]

  • top[k]

  • next[10]

  • free initially = 0

At every insertion:

  • Use free index

  • Update free using next[]

  • Adjust next[] to point to previous top of the stack

  • Update top[]

🎯 C Program: Multiple Stacks(3 Stacks) in One Array (Fixed Partitioning)

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

#define SIZE 30    // Total size of array
#define STACKS 3   // Number of stacks
#define PARTITION (SIZE / STACKS)  // Size of each stack partition

int arr[SIZE];
int top[STACKS];    // Array to store tops of stacks

// Initialize tops
void initializeTops() {
    for (int i = 0; i < STACKS; i++) {
        top[i] = i * PARTITION - 1;
    }
}

// Push into a particular stack
void push(int stackNum, int value) {
    if (stackNum < 0 || stackNum >= STACKS) {
        printf("Invalid Stack Number!\n");
        return;
    }

    // Check for overflow
    if (top[stackNum] >= ((stackNum + 1) * PARTITION) - 1) {
        printf("Stack %d Overflow!\n", stackNum + 1);
    } else {
        top[stackNum]++;
        arr[top[stackNum]] = value;
        printf("Pushed %d into Stack %d\n", value, stackNum + 1);
    }
}

// Pop from a particular stack
int pop(int stackNum) {
    if (stackNum < 0 || stackNum >= STACKS) {
        printf("Invalid Stack Number!\n");
        return -1;
    }

    int start = stackNum * PARTITION;

    // Check for underflow
    if (top[stackNum] < start) {
        printf("Stack %d Underflow!\n", stackNum + 1);
        return -1;
    } else {
        int value = arr[top[stackNum]];
        top[stackNum]--;
        return value;
    }
}

// Display a particular stack
void display(int stackNum) {
    if (stackNum < 0 || stackNum >= STACKS) {
        printf("Invalid Stack Number!\n");
        return;
    }

    int start = stackNum * PARTITION;

    if (top[stackNum] < start) {
        printf("Stack %d is empty!\n", stackNum + 1);
        return;
    }

    printf("Stack %d elements: ", stackNum + 1);
    for (int i = top[stackNum]; i >= start; i--) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int choice, stackNum, value;

    initializeTops();

    while (1) {
        printf("\n--- Menu ---\n");
        printf("1. Push\n");
        printf("2. Pop\n");
        printf("3. Display\n");
        printf("4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter stack number (1-%d): ", STACKS);
                scanf("%d", &stackNum);
                printf("Enter value to push: ");
                scanf("%d", &value);
                push(stackNum - 1, value); // Adjust index
                break;
            case 2:
                printf("Enter stack number (1-%d): ", STACKS);
                scanf("%d", &stackNum);
                value = pop(stackNum - 1);
                if (value != -1)
                    printf("Popped value: %d\n", value);
                break;
            case 3:
                printf("Enter stack number (1-%d): ", STACKS);
                scanf("%d", &stackNum);
                display(stackNum - 1);
                break;
            case 4:
                printf("Exiting program.\n");
                exit(0);
            default:
                printf("Invalid choice! Try again.\n");
        }
    }

    return 0;
}


Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and evaluation scheme  1.Basic Concepts of Data Structures     Data structures and data abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more