# How to Efficiently Implement k Stacks in a Single Array?

Difficulty Level Medium
Array StackViews 1671

Design and implement a new data structure that Implement k Stacks in a Single Array. The new data structure must support these two operations –

• push (element, stack_number): that pushes the element in a given number of the stack.
• pop (stack_number): that pop out the top element from a given number of the stack. ## Example

Input

push(15, 2)
push(45, 2)
push(17, 1)
push(49, 1)
push(39, 1)
push(11, 0)
push(9, 0)
push(7, 0)
pop(2)
pop(1)
pop(0)

Output

Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

Input

push(100, 1)
push(200, 0)
push(300, 0)
pop(1)
pop(0)

Output

Popped element from stack 1 : 100
Popped element from stack 0 : 300

## Algorithm to efficiently implement k stacks in a single array

1. Create array arr[ ] to store the elements of the stacks, top[ ] to store the index of top elements of all the stacks, and next[ ] to keep the update of the next element of all stacks.
2. Create a variable free to store the starting index of the free list.
3. Traverse and set all values of top[ ] as -1 and values of next[ ] as index + 1.
4. Create function push() that accepts element and stack number as a parameter and check if a stack of the given number is full print “Stack Overflow” and return.
5. Else Initialise a variable say i and update it as free. Update free as next(i), next(i) as the top of the stack of given number, top of the stack of a given number as i and at last push the element in the array at index i.
6. Create function pop() that accepts stack number as a parameter and check if the stack of a given number is empty print “Stack Underflow” and return.
7. Else Initialise a variable say i and update it as the top of the stack of a given number. Update top of the stack of a given number as next(i), next(i) as free, free as I, and at last return the element in the array at index I.

## C++ Program to efficiently implement k stacks in a single array

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

class newStack{
int *arr;
int *top;
int *next;

int n, k;
int free;
public:

newStack(int k, int n);

bool isFull(){
return(free == -1);
}

void push(int item, int sn);

int pop(int sn);

bool isEmpty(int sn){
return (top[sn] == -1);
}
};

newStack::newStack(int k1, int n1){

k = k1, n = n1;
arr = new int[n];
top = new int[k];
next = new int[n];

for(int i = 0; i < k; i++)
top[i] = -1;

free = 0;
for(int i=0; i<n-1; i++)
next[i] = i+1;
next[n-1] = -1;
}

void newStack::push(int item, int sn){

if(isFull()){
cout << "\nStack Overflow\n";
return;
}

int i = free;

free = next[i];

next[i] = top[sn];
top[sn] = i;

arr[i] = item;
}

int newStack::pop(int sn){

if(isEmpty(sn)){
cout<<"\nStack Underflow\n";
return INT_MAX;
}

int i = top[sn];

top[sn] = next[i];

next[i] = free;
free = i;

return arr[i];
}

int main(){

int k = 3, n = 10;
newStack ks(k, n);

ks.push(15, 2);
ks.push(45, 2);

ks.push(17, 1);
ks.push(49, 1);
ks.push(39, 1);

ks.push(11, 0);
ks.push(9, 0);
ks.push(7, 0);

cout << "Popped element from stack 2 : " << ks.pop(2) << endl;
cout << "Popped element from stack 1 : " << ks.pop(1) << endl;
cout << "Popped element from stack 0 : " << ks.pop(0) << endl;

return 0;
}```
```Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7```

## Java Program to efficiently implement k stacks in a single array

```class kstack{

static class newStack{
int arr[];
int top[];
int next[];

int n, k;
int free;

newStack(int k1, int n1){

k = k1;
n = n1;
arr = new int[n];
top = new int[k];
next = new int[n];

for(int i = 0; i < k; i++)
top[i] = -1;

free = 0;
for(int i = 0; i < n - 1; i++)
next[i] = i + 1;
next[n - 1] = -1;
}

boolean isFull(){
return (free == -1);
}

void push(int item, int sn){

if(isFull()){
System.out.println("Stack Overflow");
return;
}

int i = free;

free = next[i];

next[i] = top[sn];
top[sn] = i;

arr[i] = item;
}

int pop(int sn){

if(isEmpty(sn)){
System.out.println("Stack Underflow");
return Integer.MAX_VALUE;
}

int i = top[sn];

top[sn] = next[i];

next[i] = free;
free = i;

return arr[i];
}

boolean isEmpty(int sn){
return (top[sn] == -1);
}

}

public static void main(String[] args){

int k = 3, n = 10;

newStack ks = new newStack(k, n);

ks.push(15, 2);
ks.push(45, 2);

ks.push(17, 1);
ks.push(49, 1);
ks.push(39, 1);

ks.push(11, 0);
ks.push(9, 0);
ks.push(7, 0);

System.out.println("Popped element from stack 2 : " + ks.pop(2));
System.out.println("Popped element from stack 1 : " + ks.pop(1));
System.out.println("Popped element from stack 0 : " + ks.pop(0));
}
}```
```Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7```

## Complexity Analysis

Time Complexity: push() and pop() uses constant time i.e. O(1). Maintaining top and next will require O(k) and O(n) time respectively.

Space Complexity: O(n) where n is elements are stored.

References

Translate »