## Introduction

In this blog, we will look at the approach to store the elements of two stacks in an array, i.e. both the stacks will be using the same array for storing elements.

### Problem Statement

**Given:** Two stacks with elements

**Problem: **Store the value of the two stacks in an array such that both stacks use the same array for storing elements.

### Sample Example

Let us look at an example to understand the given problem.

The given stacks are:

```
Stack 1 - 1 2 3 4 5
Stack 2 - 6 7 8 9
```

Total elements are 9 and they will be stored in such a manner that stack 1 will occupy the indices from 0 to 4(n/2) and stack 2 will occupy the indices from 5 (n/2) to 8 (n-1).

In this way the array of 9 elements will be used to store the elements of both the stacks.

## Brute Force Approach

In this approach, we will divide the array into two sub-arrays and then store the elements. The array will be divided into two equal subarrays if the number of elements are even, and if the number of elements are odd then the left subarray will have n/2 elements and the right subarray will have n/2+1 elements.

Read more, __Data Structure__

### Pseudocode

The pseudocode to implement two stacks in an array is as follows:

- Store the elements in the two stacks and initialize an array with the total number of elements in both the stacks.
- Run a loop to divide the array into two halves, from ar[0] to a[n/2] for stack1 and from ar[n/2 + 1] to ar[n-1] for stack2.
- Iterate over the loops and perform push and pop operations for stack throughout the loop for every element and store it in the array.
- When all the elements are stored in either of the stack, then store the remaining elements from another stack.

### Implementation in C++

```
// Program to implement two stacks in an array/list
#include <iostream>
#include <stdlib.h>
using namespace std;
class twoStacks {
int* ar;
int size;
int top1, top2;
public:
twoStacks(int n)
{
size = n;
ar = new int[n];
top1 = n / 2 + 1;
top2 = n / 2;
}
void push1(int x)
{
if (top1 > 0) {
top1--;
ar[top1] = x;
}
else {
cout << "Stack Overflow"
<< " By element :" << x << endl;
return;
}
}
void push2(int x)
{
if (top2 < size - 1) {
top2++;
ar[top2] = x;
}
else {
cout << "Stack Overflow"
<< " By element :" << x << endl;
return;
}
}
int pop1()
{
if (top1 <= size / 2) {
int x = ar[top1];
top1++;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
int pop2()
{
if (top2 >= size / 2 + 1) {
int x = ar[top2];
top2--;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
};
int main()
{
twoStacks ts(5);
ts.push1(5);
ts.push2(10);
ts.push2(16);
ts.push1(13);
ts.push2(6);
cout << "Popped element from stack1 is "
<< " : " << ts.pop1()
<< endl;
ts.push2(12);
cout << "\nPopped element from stack2 is "
<< ": " << ts.pop2()
<< endl;
return 0;
}
```

### Implementation in Python

```
# Program to implement two stacks in an array/list
import math
class twoStacks:
def __init__(self, n):
self.size = n
self.ar = [None] * n
self.top1 = math.floor(n/2) + 1
self.top2 = math.floor(n/2)
def push1(self, x):
if self.top1 > 0:
self.top1 = self.top1 - 1
self.ar[self.top1] = x
else:
print("Stack Overflow by element : ", x)
def push2(self, x):
if self.top2 < self.size - 1:
self.top2 = self.top2 + 1
self.ar[self.top2] = x
else :
print("Stack Overflow by element : ", x)
def pop1(self):
if self.top1 <= self.size/2:
x = self.ar[self.top1]
self.top1 = self.top1 +1
return x
else:
print("Stack Underflow ")
exit(1)
def pop2(self):
if self.top2 >= math.floor(self.size/2) + 1:
x = self.ar[self.top2]
self.top2 = self.top2 - 1
return x
else:
print("Stack Underflow ")
exit(1)
# Main program
ts = twoStacks(5)
ts.push1(5)
ts.push2(10)
ts.push2(16)
ts.push1(13)
ts.push2(6)
print("Popped element from stack1 is : " + str(ts.pop1()))
ts.push2(12)
print("Popped element from stack2 is : " + str(ts.pop2()))
```

**Output: **

```
Stack Overflow By element :6
Popped element from stack1 is : 13
Stack Overflow By element :12
Popped element from stack2 is : 16
```

### Complexity Analysis

**Time Complexity** - We have traversed over n elements and therefore, the time complexity is O(n).

**Space Complexity** - The auxiliary space is used for n elements and therefore, the space complexity is O(n).