Data Structures: Queue With Two Stacks

Learn how to build a queue with two stacks. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

[planbprodigy]

to really demonstrate the benefits of having two queues, it is important to get the oldest and newest values. in a normal stack or queue, getting the highest priority ( newest for stack, oldest for queue) is an O(1) operation. getting the lowest priority (oldest for stack, newest for queue) is O(n). Having a double queue allows us to get highest and lowest priority in O(1), with added spatial complexity.

[mrkinetic]

I think a good way to explain this is when the oldestOnTop stack becomes empty, we grab the newestOnTop stack, flip it upside down, and it becomes the new oldestOnTop stack.

[RemixkingDystansy]

How are you running these methods in your main class. What are the parameters being pushed?

[andrewbass]

Would runtimes of these operations be considered amortized O(1)? It seems like it is similar to an ArrayList where in most cases it is O(1) but occasionally everything must be copied over.

[sahilsah]

Awesome !! Can I know which Java compiler you are using?

[pb-jk]

Now if we have stack newest on top, I mean stack oldest on top
and now we want to peek, I mean dequeue
we don't have to move anything into the new array, I mean the new stack

Why would a company want to ask this question? It's obviously too confusing to coherently explain even if you've written books about it.

[meghasyam]

i have understood the concept ...but iam getting lot of syntax errors while im trying to run it...can someone please provide the source code for this

[raushansingh]

Well Explained, Could you please explain that "what is the benefits of creating queue using two stack?"

[zl]

You have several videos about data structures, better wrap them up as a playlist

[aivancarlostuquero]

Can someone tell me what is the meaning of <T> when creating an object?

[cristian-adrianfrasineanu]

Can also be done with only one stack, but the space complexity and time complexity will always be O(n)

[ssshah]

I thought peek shows the top element in the stack or the "newest" in your example?

[ianokay]

"We need to pop everything off the top", well no, you can just call .shift() in any standard language, but interesting video to explain why this problem would even be conceived.

[kittysplode]

w....why would you not use a linked list for this. this is literally why a linked list exists. the time complexity of getting the first or last item from a linked list is O(0).

[SidsVlog]

You wont understand the logic until you put pen to paper and draw out everything as you go.