Implement A Queue Using Stacks - The Queue ADT ("Implement Queue Using Stacks" on LeetCode) 

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Implement a queue (a FIFO structure...first-in-first-out) only using stacks internally as efficiently as possible.
This problem is classic and well known but as always, I want to walk you through the thought process and not just present the solution.
Complexities
n is the total items between the 2 stacks (in the overarching queue)
Time: O( 1 ) - amortized (for enqueue and dequeue operations)
Amortized time is the way to express the time complexity when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time ( / amortized-time-in-the-... .
The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic. (en.wikipedia.o....
Space: O( n )
We upper bound space to the maximum amount of items that we will ever store.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 19.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.