We have discussed space efficient implementation of 2 stacks in a single array. In this post, a general solution for k stacks is discussed. Following is the detailed problem statement.
Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing elements. Following functions must be supported by kStacks.
push(int x, int sn) –> pushes x to stack number ‘sn’ where sn is from 0 to k-1
pop(int sn) –> pops an element from stack number ‘sn’ where sn is from 0 to k-1
Method 1 (Divide the array in slots of size n/k)
A simple way to implement k stacks is to divide the array in k slots of size n/k each, and fix the slots for different stacks, i.e., use arr[0] to arr[n/k-1] for first stack, and arr[n/k] to arr[2n/k-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.
The problem with this method is inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[]. For example, say the k is 2 and array size (n) is 6 and we push 3 elements to first and do not push anything to second second stack. When we push 4th element to first, there will be overflow even if we have space for 3 more elements in array.
[ad type=”banner”]Method 2 (A space efficient implementation)
The idea is to use two extra arrays for efficient implementation of k stacks in an array. This may not make much sense for integer stacks, but stack items can be large for example stacks of employees, students, etc where every item is of hundreds of bytes. For such large stacks, the extra space used is comparatively very less as we use two integer arrays as extra space.
Following are the two extra arrays are used:
1) top[]: This is of size k and stores indexes of top elements in all stacks.
2) next[]: This is of size n and stores indexes of next item for the items in array arr[]. Here arr[] is actual array that stores k stacks.
Together with k stacks, a stack of free slots in arr[] is also maintained. The top of this stack is stored in a variable ‘free’.
All entries in top[] are initialized as -1 to indicate that all stacks are empty. All entries next[i] are initialized as i+1 because all slots are free initially and pointing to next slot. Top of free stack, ‘free’ is initialized as 0.
[ad type=”banner”]Following is C++ implementation of the above idea.
C++ Programming:
[pastacode lang=”cpp” manual=”%2F%2F%20A%20C%2B%2B%20program%20to%20demonstrate%20implementation%20of%20k%20stacks%20in%20a%20single%20%0A%2F%2F%20array%20in%20time%20and%20space%20efficient%20way%0A%23include%3Ciostream%3E%0A%23include%3Cclimits%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20C%2B%2B%20class%20to%20represent%20k%20stacks%20in%20a%20single%20array%20of%20size%20n%0Aclass%20kStacks%0A%7B%0A%20%20%20%20int%20*arr%3B%20%20%20%2F%2F%20Array%20of%20size%20n%20to%20store%20actual%20content%20to%20be%20stored%20in%20stacks%0A%20%20%20%20int%20*top%3B%20%20%20%2F%2F%20Array%20of%20size%20k%20to%20store%20indexes%20of%20top%20elements%20of%20stacks%0A%20%20%20%20int%20*next%3B%20%20%2F%2F%20Array%20of%20size%20n%20to%20store%20next%20entry%20in%20all%20stacks%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20and%20free%20list%0A%20%20%20%20int%20n%2C%20k%3B%0A%20%20%20%20int%20free%3B%20%2F%2F%20To%20store%20beginning%20index%20of%20free%20list%0Apublic%3A%0A%20%20%20%20%2F%2Fconstructor%20to%20create%20k%20stacks%20in%20an%20array%20of%20size%20n%0A%20%20%20%20kStacks(int%20k%2C%20int%20n)%3B%0A%20%0A%20%20%20%20%2F%2F%20A%20utility%20function%20to%20check%20if%20there%20is%20space%20available%0A%20%20%20%20bool%20isFull()%20%20%20%7B%20%20return%20(free%20%3D%3D%20-1)%3B%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20To%20push%20an%20item%20in%20stack%20number%20’sn’%20where%20sn%20is%20from%200%20to%20k-1%0A%20%20%20%20void%20push(int%20item%2C%20int%20sn)%3B%0A%20%0A%20%20%20%20%2F%2F%20To%20pop%20an%20from%20stack%20number%20’sn’%20where%20sn%20is%20from%200%20to%20k-1%0A%20%20%20%20int%20pop(int%20sn)%3B%0A%20%0A%20%20%20%20%2F%2F%20To%20check%20whether%20stack%20number%20’sn’%20is%20empty%20or%20not%0A%20%20%20%20bool%20isEmpty(int%20sn)%20%20%7B%20%20return%20(top%5Bsn%5D%20%3D%3D%20-1)%3B%20%7D%0A%7D%3B%0A%20%0A%2F%2Fconstructor%20to%20create%20k%20stacks%20in%20an%20array%20of%20size%20n%0AkStacks%3A%3AkStacks(int%20k1%2C%20int%20n1)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20n%20and%20k%2C%20and%20allocate%20memory%20for%20all%20arrays%0A%20%20%20%20k%20%3D%20k1%2C%20n%20%3D%20n1%3B%0A%20%20%20%20arr%20%3D%20new%20int%5Bn%5D%3B%0A%20%20%20%20top%20%3D%20new%20int%5Bk%5D%3B%0A%20%20%20%20next%20%3D%20new%20int%5Bn%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20all%20stacks%20as%20empty%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20k%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20top%5Bi%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20all%20spaces%20as%20free%0A%20%20%20%20free%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn-1%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20next%5Bi%5D%20%3D%20i%2B1%3B%0A%20%20%20%20next%5Bn-1%5D%20%3D%20-1%3B%20%20%2F%2F%20-1%20is%20used%20to%20indicate%20end%20of%20free%20list%0A%7D%0A%20%0A%2F%2F%20To%20push%20an%20item%20in%20stack%20number%20’sn’%20where%20sn%20is%20from%200%20to%20k-1%0Avoid%20kStacks%3A%3Apush(int%20item%2C%20int%20sn)%0A%7B%0A%20%20%20%20%2F%2F%20Overflow%20check%0A%20%20%20%20if%20(isFull())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22%5CnStack%20Overflow%5Cn%22%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20int%20i%20%3D%20free%3B%20%20%20%20%20%20%2F%2F%20Store%20index%20of%20first%20free%20slot%0A%20%0A%20%20%20%20%2F%2F%20Update%20index%20of%20free%20slot%20to%20index%20of%20next%20slot%20in%20free%20list%0A%20%20%20%20free%20%3D%20next%5Bi%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Update%20next%20of%20top%20and%20then%20top%20for%20stack%20number%20’sn’%0A%20%20%20%20next%5Bi%5D%20%3D%20top%5Bsn%5D%3B%0A%20%20%20%20top%5Bsn%5D%20%3D%20i%3B%0A%20%0A%20%20%20%20%2F%2F%20Put%20the%20item%20in%20array%0A%20%20%20%20arr%5Bi%5D%20%3D%20item%3B%0A%7D%0A%20%0A%2F%2F%20To%20pop%20an%20from%20stack%20number%20’sn’%20where%20sn%20is%20from%200%20to%20k-1%0Aint%20kStacks%3A%3Apop(int%20sn)%0A%7B%0A%20%20%20%20%2F%2F%20Underflow%20check%0A%20%20%20%20if%20(isEmpty(sn))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22%5CnStack%20Underflow%5Cn%22%3B%0A%20%20%20%20%20%20%20%20%20return%20INT_MAX%3B%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%2F%2F%20Find%20index%20of%20top%20item%20in%20stack%20number%20’sn’%0A%20%20%20%20int%20i%20%3D%20top%5Bsn%5D%3B%0A%20%0A%20%20%20%20top%5Bsn%5D%20%3D%20next%5Bi%5D%3B%20%20%2F%2F%20Change%20top%20to%20store%20next%20of%20previous%20top%0A%20%0A%20%20%20%20%2F%2F%20Attach%20the%20previous%20top%20to%20the%20beginning%20of%20free%20list%0A%20%20%20%20next%5Bi%5D%20%3D%20free%3B%0A%20%20%20%20free%20%3D%20i%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20previous%20top%20item%0A%20%20%20%20return%20arr%5Bi%5D%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20twStacks%20class%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20create%203%20stacks%20in%20an%20array%20of%20size%2010%0A%20%20%20%20int%20k%20%3D%203%2C%20n%20%3D%2010%3B%0A%20%20%20%20kStacks%20ks(k%2C%20n)%3B%0A%20%0A%20%20%20%20%2F%2F%20Let%20us%20put%20some%20items%20in%20stack%20number%202%0A%20%20%20%20ks.push(15%2C%202)%3B%0A%20%20%20%20ks.push(45%2C%202)%3B%0A%20%0A%20%20%20%20%2F%2F%20Let%20us%20put%20some%20items%20in%20stack%20number%201%0A%20%20%20%20ks.push(17%2C%201)%3B%0A%20%20%20%20ks.push(49%2C%201)%3B%0A%20%20%20%20ks.push(39%2C%201)%3B%0A%20%0A%20%20%20%20%2F%2F%20Let%20us%20put%20some%20items%20in%20stack%20number%200%0A%20%20%20%20ks.push(11%2C%200)%3B%0A%20%20%20%20ks.push(9%2C%200)%3B%0A%20%20%20%20ks.push(7%2C%200)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Popped%20element%20from%20stack%202%20is%20%22%20%3C%3C%20ks.pop(2)%20%3C%3C%20endl%3B%0A%20%20%20%20cout%20%3C%3C%20%22Popped%20element%20from%20stack%201%20is%20%22%20%3C%3C%20ks.pop(1)%20%3C%3C%20endl%3B%0A%20%20%20%20cout%20%3C%3C%20%22Popped%20element%20from%20stack%200%20is%20%22%20%3C%3C%20ks.pop(0)%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]Output:
Popped element from stack 2 is 45 Popped element from stack 1 is 39 Popped element from stack 0 is 7
Time complexities of operations push() and pop() is O(1).
The best part of above implementation is, if there is a slot available in stack, then an item can be pushed in any of the stacks, i.e., no wastage of space.
[ad type=”banner”]