Implement two stacks in an array

Here, we will create two stacks, and we will implement these two stacks using only one array, i.e., both the stacks would be using the same array for storing elements.

There are two approaches to implement two stacks using one array:

First Approach

First, we will divide the array into two sub-arrays. The array will be divided into two equal parts. First, the sub-array would be considered stack1 and another sub array would be considered stack2.

For example, if we have an array of n equal to 8 elements. The array would be divided into two equal parts, i.e., 4 size each shown as below:

The first subarray would be stack 1 named as st1, and the second subarray would be stack 2 named as st2. On st1, we would perform push1() and pop1() operations, while in st2, we would perform push2() and pop2() operations. The stack1 would be from 0 to n/2, and stack2 would be from n/2 to n-1.

If the size of the array is odd. For example, the size of an array is 9 then the left subarray would be of 4 size, and the right subarray would be of 5 size shown as below:

Disadvantage of using this approach

Stack overflow condition occurs even if there is a space in the array. In the above example, if we are performing push1() operation on the stack1. Once the element is inserted at the 3^rd index and if we try to insert more elements, then it leads to the overflow error even there is a space left in the array.

Second Approach

In this approach, we are having a single array named as 'a'. In this case, stack1 starts from 0 while stack2 starts from n-1. Both the stacks start from the extreme corners, i.e., Stack1 starts from the leftmost corner (at index 0), and Stack2 starts from the rightmost corner (at index n-1). Stack1 extends in the right direction, and stack2 extends in the left direction, shown as below:

If we push 'a' into stack1 and 'q' into stack2 shown as below:

Therefore, we can say that this approach overcomes the problem of the first approach. In this case, the stack overflow condition occurs only when top1 + 1 = top2. This approach provides a space-efficient implementation means that when the array is full, then only it will show the overflow error. In contrast, the first approach shows the overflow error even if the array is not full.

Implementation in C

// C Program to Implement two Stacks using a Single Array & Check for Overflow & Underflow

Output