Photo by Alexander Grey on Unsplash

# Saving Memory Space: How to Handle Multiple Stacks with a Single Array

To store multiple stack in an array, the first approach that comes to your mind would be that you have an array of n elements and there are k stacks to be stored, and the first thing you will be doing is to make space for stacks that is you will divide the array into n/k stacks.

To perform push operation we will use push(x,m), where x is the value to be inserted and m is the stack number. Say if you have to push 5 in stack 2 that is S2, the push operation will be push(5,2) and to pop we will use pop(m).

But, there is a drawback in this approach, it is not space optimised. So, we will be looking at another approach.

Now, let us look at our second approach

Suppose that we have an array of 6 elements and we want to store 3 stacks in it. We will need two additional things, the first one is top[], which is an array that will store the position of the top elements of the stacks, its size will be the same as that of the number of stacks. And the other one is next[], it will point to the next element after stack top when stack is filled and it point to the next free space when stack is empty.

Now let us look at the algorithm to push an element:

push(10,1) -> this translates to push 10 in stack 1

Find index

int index = freeSpot

update freeSpot

freeSpot = next[index]

freeSpot becomes 1 from 0

insert the element in array

arr[index] = x

update next

next[index] = top[m-1]

update top

top[m-1] = index

The algorithm for pop operation is the reverse of the push.

```
// n stacks in an single array
#include <iostream>
using namespace std;
class Nstack
{
int *arr;
int *top;
int *next;
int n, s;
int freeSpot;
public:
Nstack(int N, int S)
{
n = N;
s = S;
arr = new int[s];
top = new int[n];
next = new int[s];
// top initialise
for (int i = 0; i < n; i++)
{
top[i] = -1;
}
// next initialise
for (int i = 0; i < s; i++)
{
next[i] = i + 1;
}
// update last index value to -1
next[s - 1] = -1;
// initialise freeSpot
freeSpot = 0;
}
// Pushes 'x' into the Mth stack. Returns true if get pushed
bool push(int x, int m)
{
// Check for overflow
if (freeSpot == -1)
{
return false;
}
// find index
int index = freeSpot;
// update freeSpot
freeSpot = next[index];
// insert element into array
arr[index] = x;
// update next
next[index] = top[m - 1];
// update top
top[m - 1] = index;
return true;
}
// Pops top element from Mth stack. Returns -1 if the stack is empty
int pop(int m)
{
// check underflow
if (top[m - 1] == -1)
{
return -1;
}
int index = top[m - 1];
top[m - 1] = next[index];
next[index] = freeSpot;
freeSpot = index;
return arr[index];
}
};
int main()
{
int numberOfStacks = 3;
int SizeOfArray = 10;
Nstack nStacks(numberOfStacks, SizeOfArray);
// Push some elements into the first stack
for (int i = 1; i <= 5; i++)
{
if (nStacks.push(i, 1))
{
cout << "Pushed " << i << " to Stack 1" << endl;
}
else
{
cout << "Stack 1 is full. Cannot push " << i << endl;
}
}
// Push some elements into the second stack
for (int i = 6; i <= 10; i++)
{
if (nStacks.push(i, 2))
{
cout << "Pushed " << i << " to Stack 2" << endl;
}
else
{
cout << "Stack 2 is full. Cannot push " << i << endl;
}
}
// Push some elements into the third stack
for (int i = 11; i <= 15; i++)
{
if (nStacks.push(i, 3))
{
cout << "Pushed " << i << " to Stack 3" << endl;
}
else
{
cout << "Stack 3 is full. Cannot push " << i << endl;
}
}
// Pop elements from the first stack
for (int i = 1; i <= 5; i++)
{
int value = nStacks.pop(1);
if (value != -1)
{
cout << "Popped " << value << " from Stack 1" << endl;
}
else
{
cout << "Stack 1 is empty. Cannot pop." << endl;
}
}
// Pop elements from the second stack
for (int i = 1; i <= 5; i++)
{
int value = nStacks.pop(2);
if (value != -1)
{
cout << "Popped " << value << " from Stack 2" << endl;
}
else
{
cout << "Stack 2 is empty. Cannot pop." << endl;
}
}
// Pop elements from the third stack
for (int i = 1; i <= 5; i++)
{
int value = nStacks.pop(3);
if (value != -1)
{
cout << "Popped " << value << " from Stack 3" << endl;
}
else
{
cout << "Stack 3 is empty. Cannot pop." << endl;
}
}
return 0;
}
output:
Pushed 1 to Stack 1
Pushed 2 to Stack 1
Pushed 3 to Stack 1
Pushed 4 to Stack 1
Pushed 5 to Stack 1
Pushed 6 to Stack 2
Pushed 7 to Stack 2
Pushed 8 to Stack 2
Pushed 9 to Stack 2
Pushed 11 to Stack 3
Stack 3 is full. Cannot push 12
```