Implement K stacks in a single Array

Problem Statement:  Design a data structure to implement ‘N’ stacks using a single array of size ‘S’. It should support the following operations:

  • push(X, M): Pushes an element X into the Mth stack. Returns true if the element is pushed into the stack, otherwise false.
  • pop(M): Pops the top element from Mth Stack. Returns -1 if the stack is empty, otherwise, returns the popped element.

Examples:

Input: K , N ( K denotes the no. of stacks , N is the size of the array)
There are two types of queries denote these operations :
Type 1: for push(X, M) operation.
Type 2: for pop(M) operation.

Input: push(11,0) 
Output: Pushes element 11 into stack 0

Input: push(13,1) 
Output: Pushes element 13 into stack 1

Input: pop(1) 
Output: Pops the top element from stack 1.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Brute Force

Since we are given one array(size n) and k stacks , the basic approach can be to divide this array into k parts . Where length of each part will be k/n  and each part will have its own top to implement the stack.

Code:

C++ Code

#include<bits/stdc++.h> 
using namespace std;

int pop(int stno,vector<int> &arr,int &t1,int &t2,int &t3){
	if(stno==0){
	if(t1!=0){

	return arr[t1--];
		}
	}
	else if(stno==1){
	if(t2!=0){
	return arr[t2--];
		}
	}	
	if(t3!=0){
		return arr[t1--];
	}
return INT_MAX;
}
void push(int ele,int stno,int &t1,int &t2,int &t3,int &b1,int &b2,int &b3,
vector<int>&arr){
	cout<<"Element pushed in the stack"<<endl;
	if(stno == 0){
		if(t1==b1){
			cout<<"overflow";
			return;
		}
		else arr[++t1]=ele;
		
		
	}
	else if(stno == 1){
		if(t2==b2){
			cout<<"overflow";
			return;
		}
		else arr[++t2]=ele;
		
	}
	else{
			
		if(t3==b3){
			cout<<"overflow";
			return;
		}
		else arr[++t3]=ele;
		
	
	}
	return ;
}
int main(){
	int n = 9;
	int k = 3;
	vector<int>arr(n);
	int t1 = -1 ,t2=2,t3=5;
	int b1=t1+3,b2=t2+3,b3=t3+3;
	//Suppose we are pushing element 11 in stack 0
	push(11,0,t1,t2,t3,b1,b2,b3,arr);
	push(13,0,t1,t2,t3,b1,b2,b3,arr);
	cout<<"Element popoed from the stack "<<pop(0,arr,t1,t2,t3);
	return 0;
}

Output:

Element pushed in the stack
Element pushed in the stack
Element popoed from the stack 13

Solution 2: Optimal Approach

Here , we will take 3 array , arr to keep the elements , top array to store the top of each stack and next array , to store the next free space as well as the previous element in the stack. We also use a variable free, to keep track of the next free space.

Initially the array, arr is empty. The top is initialized to -1 as there are no elements in the stack . The next array keeps track of the next free element , so it will be initialized as , index 0 will have 1 , index 1 will have 2 and so on , because the next free space to index 0 at initially is the just next block . 

next[n-1] will be -1 because there are no more blocks after that.

CASE 1: Push (11,0) push element 11 in stack 0 

We will first check free , here we get the index i of the next free space  ,we update free to the next[i]. Now next[i] will keep track of the previous element to which we are about to add, so next[i]=top[0] // top of stack ,  we then update top of stack in stack array, top[0] = 0 ,because 0 is the index where we are going to store the element. Now we add the element at arr[i] = 11. 

CASE 2: Push (13,0) push element 13 in stack 0 

We again will first check free  which is 1, here we get the index i of the next free space so i=1 now  ,we update free to the next[i] , free becomes 2. Now next[i] will keep track of the previous element to which we are about to add, so next[i]=top[0] ,i.e, next[i] = 0 // top of stack ,  we then update top of stack in stack array, top[0] = i,because 1 is the index where we are going to store the element. Now we add the element at arr[i] = 13.  

CASE 3: Push (15,1) push element 15 in stack 1 

We again will first check free  which is 2, here we get the index i of the next free space so i=2 now, we update free to the next[i], free becomes 3. Now next[i] will keep track of the previous element to which we are about to add, so next[i]=top[1], i.e, next[i] = -1 // top of stack,  we then update top of stack in stack array, top[1] = i,because 3 is the index where we are going to store the element. Now we add the element at arr[i] = 15.  

Case 4: pop element from stack 0

To pop an element from a stack,  we know we have to remove from the top. We got to top[st no] and check the top element. This also gives us the index I at which in the next array, the previous element to current top is stored. We go to next [1] which is 0, so now new top will be 0 . And as we are going to delete this entry next[i] will get free, so we update next[i]=free, because as we had decided it will keep track of next free cell and free= I, as current cell is now going to be empty. We can now return arr[i] as that is the top element in the stack.

To check if stack is empty, we can simply check is top[st no] = -1 

For overflow we can stop when we get free=-1

Code:

C++ Code

#include<bits/stdc++.h> 
using namespace std;

int pop(int stno,vector<int> &arr,vector<int>&top,vector<int>&next,int &free){
	int i;
	if(top[stno]==-1){
		cout<<"Underflow";     // can't pop if stack is empty
		return 1e9;	     // just because we have to return something in 
                                    //case of underflow
	}
	
		i=top[stno];		//find top of stack
		top[stno] = next[i];   // change top to updated top
		next[i]=free;		// because this cell is now clear
		free=i;
		return arr[i];
	
}
void push(int ele,int stno,vector<int> &arr,vector<int>&top,vector<int>&next,
int &free ){
	cout<<"Element is pushed in the stack"<<endl;
	int i;
	if(free == -1){			//overflow condition
		cout<<"stack overflow"<<endl;
		return ; 
	}
	else{
		i= free;        // i=  space where we can add element
		free=next[i];	// free is next[i], next avilable space
		next[i]=top[stno]; // keeps track of previous top
		top[stno]=i;	   // changes top to new top
		arr[i]=ele;	   //stores the element
	}
	return ;
}
int main(){
	int n = 9,i,free;
	int k=3;
	vector<int>arr(n);
	vector<int>top(k,-1);
	vector<int>next(n);
	for(int i=0;i<n-1;i++){
		next[i]=i+1;   //Initialize next array to keep tarack of free spaces
	}
	next[n-1]=-1;
	free=0;
	
	push(11,0,arr,top,next,free);
	push(13,0,arr,top,next,free);
	push(15,1,arr,top,next,free);
	cout<<"Element is popped from the stack "<<pop(0,arr,top,next,free);
	cout<<endl;
	cout<<"Element is popped from the stack "<<pop(0,arr,top,next,free);
	
	return 0;
}

Output:

Element is pushed in the stack
Element is pushed in the stack
Element is pushed in the stack
Element is popped from the stack 13
Element is popped from the stack 11

Special thanks to RIshika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article