K stacks in a single array | GeeksforGeeks

This video is contributed by Bharathi.

Please Like, Comment and Share the Video among your friends.

Install our Android App:

If you wish, translate into local language and help us reach millions of other geeks:

Follow us on Facebook:

And Twitter:

Also, Subscribe if you haven't already! :)

[prasad]

Understood after listening for 10 times approximately for two days

[viditsharma]

i wish was smart enough to grab the concept in one go. thanks btw good explanation

[nehamalvia]

I could not understand it looking at the code, it became easier to understand with the example. thanks!

[ramchandran]

You made the difficult logic look so simple. Thank u so much ..

[MemesYTpage]

after watching this in knowledge kaze its clear, , , mashaallah its good

[sagaralwani]

A few minutes ago
I was searching for it...
Thank u

[nero]

I feel like I sort of understand the first method but besides memorizing it, Idk if I'd be able to explain it on an interview

[verma_jay]

Thanks a lot Bharathi ma'am for this wonderful explanation.

[theuntrainedsinger]

first time i was not able to understand a video on gfg. next thought was youtube. and you have made a good video

[amerdelic]

I understood this, but I couldn't get over how simple solution was so I had to make sure. The way I did this was just to create an array with k stack objects in it. I couldn't see beyond this solution honestly. IMO, anything beyond this is needlessly complicated.

kStacks = [new Stack(), new Stack(), new Stack()];

And there you go lol.

[TusharRaghav]

➡ Setup: in this method the elements of a given stack would be sitting at any available space unlike being next to each other like other implementations that we have seen so far. To know the top element of a stack we will maintain a top array of size k which will tell us the location of the top element of the stacks. Also we will use a next array of size n that will serve 2 purpose, if ith cell is filled in our stack array then ith cell in this next array will tell us the location of the element that is below it in the stack i.e that was pushed before it. For cells that are empty it will tell us the next empty cell in case we are filling this one. Apart from these we will have variable named free that will tell us left most free cell in the array. Initially we initialize the top array with value -1 since all stacks are initially empty. The next array is initialized with value i+1 where i is th index of the cell, because if we are filling ith cell then initially (i+1)th cell will be empty and logically we must go there. Our free variable will have initial value as 0.

➡ Working Of Push: Now when we want to push a value in jth stack (say) then we will have to insert it in the place that free is pointing to. Now since this is the new top of the jth stack we need to update the top array as top[j] = free. Now the free cell is getting filled so we need to also change the free variable to next free cell that is given to us by the next array. Also we need to to update the next array since now it is filled now and need to tell us the previous element in the stack which is current top.

➡ Working Of Pop: to pop an item from the jth stack we need to use top[j] to get the index of the top most element of the jth stack since this is now the new empty cell we have to bring free here also current value of free must go in the next array as when this cell gets filled again later then next will give us next free cell which is current free cell (i.e before pop), current value of next will give us the new top of the jth stack.

[pranavsingh]

though the animations help and are quite clear but video is too short. I had to watch it multiple times to gain clarity. would have been better if you did 3-4 push and 2-3 pops and explained.

[koyavasudhalakshmi]

Mam is there any solution possible without using constructors for method2 provided in the geeksforgeeks link mentioned

[koyavasudhalakshmi]

Mam what is the time complexity for best case and worst case?

[swatigupta]

Canyou explain for multiple queue also please

[chetan]

I watched lots of videos but didn't understand until I found this vido

[ShivamSingh-kmxo]

At least you should have taken stack no.2 also for push and pop, just wrapped up the video in only stack no.1 . Then it would have been more clearer.
Not nicely explained.
Going to look another time!!

[prasad]

We may not get an idea to implement it directly without knowing it before.

[sarahabraham]

"Implementing multiple queues with single array. " please explain this concept.

[abhinavagrawal]

Why GFG videos are so monotonous? Please don't explain problems like a computer