Breaking down N/k stack implementation in a single array

There is an interesting question in which you have to implement N/k stacks in a single array.

It is an extension of the problem where you have to implement 2 stacks in a single array. For this, we can easily think of breaking the array or partitioning the array into two equal halves, i.e if the size of the array is n, then size of each stack is n/2. The top pointers of respective stacks are initially at 0 and n/2. But this approach leads to inefficient space utilisation. Even if there is space in the array and we need to insert in second stack, we cannot borrow space from the first stack, hence inefficient approach.

Approach 2: Place your top pointer of stack 1 at -1, and your top pointer of stack 2 at array.size(). Since both the pointers are at extreme ends, entire space can be utilised in the array. Although, we need to be careful to check if stack1 or stack2 is full. That should not cross each other, ie. top1!> top2.

Now, coming back to the question of N/k stacks, we can have similar approaches.

Approach 1: Divide the array into N/k Stacks. Interval of stacks will be

[0, N/k -1] , [N/k, 2(N/k) -1] and so on. (Inefficient space utilisation)

Approach 2: Here, I shall break down a unique approach to the question. Let us take 3 different arrays for the purpose of solving the question.

Input array: size n where n is the number of elements.

Top pointers array: Size is number of stacks ie k

Next array: This will store the next element of the corresponding element i at Input array.

Initialisation of the array

For initialisation purpose, we will take -1 for the top pointer array. The free variable will contain the free space in the input array to insert the element. Initially, free space will be equal to 0. Next array will initially contain array[I]=I+1, because for every element in next array, there is free space in the adjacent input array initially. Last element of next is however, to be initialised as -1, to indicate that the our entire input array is full.

We have to understand that, since input array will be filled in contiguous locations, irrespective of the stack number, we will maintain stack number’s top pointers with the help of top pointer array and next array.

Code for initialisation: int top= new int[k]; int next = new int[n]; int free=0;

for(int i =0;i<k;i++) { top[i]=-1}; // initialisation of the top array

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

Coming over to performing push and pop operations.

Push() operation:

Push(stack number, element): Suppose we push 20 in stack number 2. For this, we would need to push it in the first free space. Let us save first free space as temp.

push(2,20) : push element 20 in stack number 2.

Now, how did we reach here and make these changes? Let us go step by step.

We store our free variable as i.

Now, let us talk about pop operation: Currently, the array looks like this and we decide to pop the element from the stack number2.

pop(stack number)

pop() operation

20 will be overwritten in the next operation as free variable is now 0. Thus, we complete the operations of N/k stacks in a single array. Happy reading :)



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store