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.

1. i=free;
2. We correspondingly update the value of free to next free space available with the help of next array. // free= next[I];
3. We store the value of element at the first free space in our array. arr[I]=element;
4. in our next array, we update the value of the element corresponding to the free space. next[I]=top[sn];
5. Finally, we store top[sn]=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)

1. We go to the top pointer array to find out where our top element of the stack is, we store this index as i. i = top[sn];
2. We update top[sn] with the next element from the next array, ie. -1. //top[sn]=next[top[sn]];
3. Now, since this is a free space, we need to update our free variable to 0. But we also simultaneously, have to link the previous free variable. We do so by updating our next array. //next[I]=free; //free=I;

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 :)