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:

1. Simple method
2. Efficient method

Prerequisite: Stack, Array

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_no-1)*n/k, stack_no*n/k-1]

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<n-1; i++) next[i]=i+1;
        next[n-1]=-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.