Program to Implement Two Stacks in an Array

• Write a program to implement two stacks using a single array supporting push and pop operations for both stacks.

Given an integer array of size N. We have to implement two stacks in given array. Both stacks must support push and pop operations. We should be able to push an element in any stack until there is a empty slot in given array.

Algorithm to implement two stacks in a array

• We will start two stacks from two extreme end of input array. Both these stacks will grow towards each other.
• Left stack will start index 0 and grow towards right end of array.
• Right array will start from index N-1 and grow towards left end of array.
• We will use stack number to differentiate between these two arrays. 0 and 1 will be used for left and right array respectively.
• When both stacks meet each other then we won't be able to push any element in any stack.

Here is the prototype of push and pop operations.
PUSH

• void push(int stack, int num);
• It will take stack number and integer to be pushed in stack as input.

POP

• int pop(int stack)
• It takes stack number as input. It removes the top element from stack corresponding to passed stack number.

NOTE : Here we are using same push and pop method for both stacks. We will select appropriate stacks based on stack number.

---

C program to implement two stacks in using one array

#include <stdio.h>
#include <limits.h>

#define ARRAY_SIZE 100
#define LEFT_STACK 0
#define RIGHT_STACK 1

struct st {
    int array[ARRAY_SIZE];
    int top1, top2;
} st;

void initialize() {
    st.top1 = -1;
    st.top2 = ARRAY_SIZE;
}
 
void push(int stack, int num) {
    if(stack == LEFT_STACK) {
        if (st.top1 < st.top2-1) {
            st.top1++;
            st.array[st.top1] = num;
        } else {
            printf("Left Stack Full");
            return;
        }
    } else if(stack == RIGHT_STACK) {
       if (st.top1 < st.top2-1) {
           st.top2--;
           st.array[st.top2] = num;
       } else {
           printf("Right Stack Full");
           return;
       }
    }
}
 
int pop(int stack) {
    if(stack == LEFT_STACK) {
        if(st.top1 >= 0){
            return st.array[st.top1--];
 } else {
            printf("Left Stack is Empty");
            return INT_MIN;
 }
    } else if(stack == RIGHT_STACK) {
     if(st.top2 <= ARRAY_SIZE-1){
         return st.array[st.top2++];
 } else {
            printf("Right Stack is Empty");
            return INT_MIN;
 }
    }
}
 
int main() {
    initialize();
    /* Push element in left stack */
    push(LEFT_STACK, 2);
    push(LEFT_STACK, 4);
    push(LEFT_STACK, 6);
    /* Push element in right stack */
    push(RIGHT_STACK, 1);
    push(RIGHT_STACK, 3);
    push(RIGHT_STACK, 5);
    /*Pop Elements from left stack */
    printf("Pop from left stack %d\n", pop(LEFT_STACK));
    /*Pop Elements from right stack */
    printf("Pop from right stack %d\n", pop(RIGHT_STACK));
    return 0;
}

Output

Pop from left stack 6
Pop from right stack 5

---

By dividing array into two equal parts.

• We will divide the input array into two equal sub arrays. Left stack from index 0 to N/2-1 and right stack from index N/2 to N-1.
• Left stack will start from index 0 and can grow till index N/2-1 whereas right start will start from index N/2 and can grow till index N-1.
• Any stack cannot hold more than N/2 elements.