Get this book > Problems on Array: For Interviews and Competitive Programming
In this article, we have present two approaches to design K stacks in one array. The challenge is to efficiently store the elements to use all available space in the array and maintain the time complexity of stack operations.
Table of contents:
 Simple method
 Efficient method
Let us get started with Implement K stacks in one array.
Simple method
In this method we will create array of some size and divide that array into k parts for storing elements of k stacks
for implementing this first we will create two array arr
of size n for storing values
top
of size k for storing top positions of stacks
we will initialize all elements of arr with 1 index with 1 in it is considered to be and empty index
and initialize elements of top with starting elements of their stack
Ex:
let arr
be array of size 9(n=9)
which will store values of elements
top
be array of size 3(k=3)
which will store top position of stack
range of stack will be [(stack_no1)*n/k, stack_no*n/k1]
then,
top[3]={0, 3, 6}
range of stack 1 = [0, 2]
range of stack 2 = [3, 5]
range of stack 1 = [6, 8]
value in top if ith index will denote top element of corresponding stack and the value of will get stored at arr[i]
ex: let n = 4 and k=2
arr={1, 1, 1, 1}
top = {0, 2}
if we enter 1 in stack 1 and 2 in stack 2 then
arr = {1, 1, 2, 1}
top = {0, 2}
top[0] = 0 = top of 1st stack
top[1] = 2 = top of 2nd stack
now of we add 3 in 1st stack and 4 in 2nd stack
then,
arr = {1, 3, 2, 4}
top = {1, 3}
top[0] = 1 = top of 1st stack
top[1] = 3 = top of 2nd stack
insert in stack
 for inserting we will use
push
function  for inserting element in stack first we will check if stack is full or not if yes then we will simply print stack is full
 if not then add value at top of the stack
Removing value from stack
 for removing values from stack we will use
pop
function  for removing element from stack first we will check if stack is empty or not if yes then we will simply print stack is empty
 else we will remove value from stack
push(int value, int stack_no)

if top[stack_no](stack_no*n)/k and arr[top[stack_no]]1 then stack is empty [top of stack is equal to first index of stack and value in same index at arr is 1] so we can add insert element in stack

if top[stack_no]+1<((stack_no+1)*n)/k then the index next to the top element is empty and we can add value there. so first we will increase top[stack_no] by 1 nad then we will insert value at arr[top[stack_no]]

if top[stack_no]>=((stack_no+1)*n)/k then we will print stack is full as ((stack_no+1)*n)/k is first element of stack who is next to current stack
pop(int stack_no)
 if top[stack_no](stack_no*n)/k and arr[top[stack_no]]1 means top of stack is equal to first index of stack and value in same index at arr is 1, hence stack is empty so we will just print stack is empty as there is no element present in stack
 if top[stack_no]==(stack_no*n)/k and arr[top[stack_no]]!=1 means top of stack is first index of stack and there is some value present in starting index of current stack therefore we will return value at top of stack and store 1 in arr at starting index of current stack
 if index in top[stack_no] is greater than first index then we will return value in arr at index top[stack_no], store 1 in place of arr[index] and decrease side of stack by 1
Code
#include<iostream>
using namespace std;
class kstack{
int n, k;
int *arr, *top;
public:
kstack(int n, int k){
this>n = n; this>k = k;
arr = new int[n];
top = new int[k];
for(int i=0; i<n; i++) arr[i]=1;
for(int i=0; i<k; i++) top[i] = (i*n)/k;
}
void push(int value, int stack_no){
stack_no;
if(top[stack_no]==(stack_no*n)/k and arr[top[stack_no]]==1) arr[top[stack_no]]=value;
else if(top[stack_no]+1<((stack_no+1)*n)/k and arr[top[stack_no]+1]==1) top[stack_no]++, arr[top[stack_no]]=value;
else cout<<"Stack no "<<stack_no+1<<" is Full, can't enter "<<value<<endl;
}
int pop(int stack_no){
int temp=1;
stack_no;
if(top[stack_no]==(stack_no*n)/k and arr[top[stack_no]]==1) cout<<"Stack no "<<stack_no+1<<" is Empty"<<endl;
else if(top[stack_no]==(stack_no*n)/k and arr[top[stack_no]]!=1) temp=arr[top[stack_no]], arr[top[stack_no]]=1;
else temp=arr[top[stack_no]], arr[top[stack_no]]=1, top[stack_no];
return temp;
}
~kstack(){
delete [] arr;
delete [] top;
}
};
void solve(){
// Stack with k=2 and n=4
kstack k1(4, 2);
// Adding elements to stack 1
k1.push(1, 1);
k1.push(2, 1);
k1.push(3, 1);
// Adding elements to stack 2
k1.push(4, 2);
k1.push(5, 2);
k1.push(6, 2);
// Removing elements from Stack 1
cout<<k1.pop(1)<<endl;
cout<<k1.pop(1)<<endl;
cout<<k1.pop(1)<<endl;
// Removing elements from Stack 2
cout<<k1.pop(2)<<endl;
cout<<k1.pop(2)<<endl;
cout<<k1.pop(2)<<endl;
}
int main(){
solve();
return 0;
}
Output
Stack no 1 is Full, can't enter 3
Stack no 2 is Full, can't enter 6
2
1
Stack no 1 is Empty
1
5
4
Stack no 2 is Empty
1
Time Complexity
O(1)
[all the operation (pop and push) are performed in O(1) time]
Space Complexity
O(N)
[as we are using two arrays one of size n and other of size k(k<=n) therefore, O(N)]
Efficient method
In this method we will create three arrays:
 array
arr
for storing stack elements  array
top
for storing top index of stacks next
for storing pointers to next free spaces and also for storing the index of element below the top element of that stack
Ex: let arr is of size n
then for an index 0 <= i < n
If arr[i] will store value of the element and next[i] will store index of element thich is below to that element in stack
but if arr[i] will be empty or not alloted to any of the stack then next[i] will store next free space after index i in arr
we will create one variable named as free
to store free slot with minimum index
we will implement this inside class and divide complete operations in functions
we will create array of size n
top of size k and initialize all elements with 1
next of size n and initialize each element with index if next element and initialize last element with 1
initialize free with 0
ex:
n=4, k=2
then
free = 0
top[2]={1, 1}
next[4]={1, 2, 3, 1};
isEmpty(int stack_no):

this function will check if the stack is empty of not

if top of stack is 1 then stack is empty as we have declared all elements as 1
isFull(int stack_no)
 this function will check whether stack is full or not
 if free is 1 then stack is full as free is the free index with minimum index if free is 1 means free is storing last element of next array
push(int value, int stack_no)
this function will be used to insert elements in stack
 first check if stack is full or not of full then print stack is full
 else
 store value of free in temp variable and in index temp of arr we will store our value
 store next free location in free using free = next[temp]
 storing temp which is index of current element which is also top element in stack in top array
pop(int stack_no)
this function will be used to remove element from a particular stack
 first we will check whether the stack is empty or not of yes then we will just print stack is empty
 else
 store top element index in temp
 updating top with second top element index using next[temp]
 updating next temp with next free location using free variable
 updating free with temp as index temp just got free
 returning value in index temp from arr
Code
#include<iostream>
using namespace std;
class kstack{
int n, k, free;
int *arr, *top, *next;
public:
kstack(int n, int k){
this>n = n;
this>k = k;
this>arr = new int[n];
this>top = new int[k];
for(int i=0; i<k; i++) top[i]=1;
this>next = new int[n];
for(int i=0; i<n1; i++) next[i]=i+1;
next[n1]=1;
this>free = 0;
}
bool isFull(){
if(free==1) return true;
else return false;
}
bool isEmpty(int stack_no){
if(top[stack_no]==1) return true;
else return false;
}
void push(int value, int stack_no){
stack_no=1;
if(isFull()){
cout<<"Stack no "<<stack_no+1<<" is Full, can't enter "<<value<<endl;
return;
}
int temp = free;
free = next[temp];
next[temp] = top[stack_no];
top[stack_no] = temp;
arr[temp] = value;
}
int pop(int stack_no){
stack_no=1;
if(isEmpty(stack_no)){
cout<<"Stack no "<<stack_no+1<<" is Empty"<<endl;
return 1;
}
int temp = top[stack_no];
top[stack_no] = next[temp];
next[temp] = free;
free = temp;
return arr[temp];
}
~kstack(){
delete [] arr;
delete [] top;
}
};
void solve(){
// Stack with k=2 and n=4
kstack k1(4, 2);
// Adding elements to stack 1
k1.push(1, 1);
k1.push(2, 1);
k1.push(3, 1);
// Adding elements to stack 2
k1.push(4, 2);
k1.push(5, 2);
k1.push(6, 2);
// Removing elements from Stack 1
cout<<k1.pop(1)<<endl;
cout<<k1.pop(1)<<endl;
cout<<k1.pop(1)<<endl;
// Removing elements from Stack 2
cout<<k1.pop(2)<<endl;
cout<<k1.pop(2)<<endl;
cout<<k1.pop(2)<<endl;
}
int main(){
solve();
return 0;
}
Output
Stack no 2 is Full, can't enter 5
Stack no 2 is Full, can't enter 6
3
2
1
4
Stack no 2 is Empty
1
Stack no 2 is Empty
1
Time Complexity
O(1)
[all the operation (pop and push) are performed in O(1) time]
Space Complexity
O(N)
[as we are using three arrays, 2 of size n and 1 of size k (k<=n) ] therefore, O(N)]
With this article at OpenGenus, you must have the complete idea of how to design and implement K stacks in one array.