- 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.

**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.

*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.