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.
Table of Contents
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
- 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.
- Create a variable free to store the starting index of the free list.
- Traverse and set all values of top[ ] as -1 and values of next[ ] as index + 1.
- 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.
- 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.
- 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.
- 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.