Implement A Queue Using Stacks - The Queue ADT ("Implement Queue Using Stacks" on LeetCode)
HTML-код
- Опубликовано: 13 окт 2024
- 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.
Table of Contents:
The Problem Introduction 0:00 - 0:17
The Queue ADT 0:17 - 1:27
What Problems Does A Stack Give Us? 1:27 - 1:45
Walkthrough With 1 Underlying Stack 1:45 - 6:44
We Missed Something...Go Back 6:44 - 7:39
Walkthrough Using A 2nd Stack 7:39 - 11:19
What You See Is A Queue (Abstraction) 11:19 - 11:52
Space Complexity 11:52 - 12:08
Time Complexity 12:08 - 12:20
Amortized Analysis: What Is It? 12:20 - 13:34
Amortized Analysis: Use For ArrayList In Java 13:34 - 14:05
Wrap Up 14:05 - 14:40
The code for this problem is in the description. Fully commented for teaching purposes.
Encapsulation is a means to achieve abstraction
The best part of this is that no code is presented, making it easy to gasp and possible to apply to all known languages without much complication, really appreciate that everything in the vid focused on the key concept of a queue and not jump straight to code.
sure
I just discovered your videos and I find them so helpful in my learning process! I deeply appreciate the amount of work you put in each of your videos and hope you pursue your dreams concerning this channel!
thanks
Thanks a lot. You are the only instructor I have found yet who explains the thinking behind the solution rather than just parroting the solution, like a lot of other instructors do. It is the difference between learning from a person and a book. Thanks for that. I hope that more teachers around the world start to do this.
thx
Oh my god you are the only person who made this simple. I been stressing for weeks on how to do it for college. Thank you so much.
sure
Have been watching your videos for 3 years doing my Comp Sci degree. Thank you so much from your help. You're so much better than most of my lecturers, unfortunately.
I've only been doing this since December 2018 haha so I guess 1.5? and nice
I like how they nailed the staged rewind part. Good content bro. Keep it up.
Thank you so much for your simple and clear explanation! I can't thank you enough for the work you've done and energy&time you put into making these videos!
Means a lot!
best thing about your videos is you don't feel bored
nice
Great work as always. One question: how rarely does the operation need to happen for the amortized time to go down from the worst case to constant time?
To be honest, I am not sure. I'm in Algorithms right now so I'm still learning.
We would have to look at a concrete analysis (like I did with Bubble Sort and Selection Sort) and see the exact worst case operations that are done across many operations.
We get the concrete analysis and then bound it based on what we find.
For amortized analysis we wouldn't bound to a specific operation's worst case, we would bound against a large amount of operations' worst cases throughout the algorithm.
Again, I'm not qualified to teach this in depth yet so I found a great resource here: www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
@@BackToBackSWE Thanks so much!
@@yanxichen4236 sure
You can look at this specific problem in this way - for every pop which takes O(N) time there will be N pops in O(1) time. This makes pop O(2N/(N+1))~O(2)~O(1) operation.
That is a great question
Your explanation is amazing! Thanks for this video!!!!
thank you, you're really good at explaining concepts
thx
you put lots of effort in your video's bro kudos to that...
firstly I feared about dynamic programming but now it is a cakewalk after your watching videos and now queues and stacks also
great
This is a brilliant explanation. So clear!! And now I see a slinky.
Great explanation! Thanks for sharing, subscribed and liked the video.
thanks for the great channel ...you are my new hero! ✌️👍
We are all heroes
Thanks, I love the idea from 7:39. I struggled with tge first approach and it did not made sense how can work O(1)
Simple and superior as always.
Awesome explanation. Thanks!
Brilliant explanation!!
thanks
Amazing and Clear Explanations! Kudos!
thanks for watching
@@BackToBackSWE would love your videos on System Design if possible :)
best explanation
Thank you 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
Wow, what a great explanation! It's very easy to understand and interesting to listen :)
Good video man, got to know about what an ADT is - similar to the idea of a java interface, what amortized analysis is, and the solution to the problem.
Thank you very much!! The solution from leetcode was a little confusing and I couldn't really understand it, but this video definitely helped me :)
Thanks for uploading this...This is very helpfull to me.
amazing explanation, thank you! keep up the great work!
Glad to hear that! Subscribe to our DSA course with a flat 30% discount for some amazing content b2bswe.co/3HhvIlV
another wonderful video, Thank you so much
Loved it! Thank you for putting this great content out!
WHAT A GENIUS!
Great explanation
can you please make a video that goes deeper into Amortized analysis. Like also explaining the different methods to calculate the amortized time
yeah - but I'd have to read a paper on it, I only know the basics
great explaination. Really appreciate it
You make stuff damn simple. Thank you.
sure
Amazing article. Thank you very much.
sure
كل الشكر التقدير لك من متابع عربي ❤❤
God bless you Benyam! Great content as always!
This is a neat approach. Also could we not just check the length of the stack and just either pop from the nth -1 on dequeue and add to the 0th item on enqueue?
I would like to answer this but I'm not fully sure what you mean
@@BackToBackSWE ** if we override the Stack implementation by extending the Stack..**
public synchronized E pop() {
int len = size();
if (len == 0)
throw new EmptyStackException();
removeElementAt(0);
return elementAt(0);
}
Small test program:
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack mystack = new MyStack();
mystack.add(1); //First In
mystack.add(5);
mystack.add(3);
mystack.add(7); //Last in
System.out.println(mystack);
mystack.pop(); // Removes 1
System.out.println(mystack);
mystack.push(7);
System.out.println(mystack);
mystack.pop();
System.out.println(mystack);
}
Sorry when I replied earlier I wasn't being clear on overriding the Stack. My apologies.
Very cool, thank you 👍!! Will implement that today for practice 😁!
nice
You are so helpful! Thank you for the excellent content!
how such a high quality video!🔥
Thanks Ben 😄😄
icredible explanation..
thanks
Whoa. Where were you all this time 🙏
Thank you so much!
Love your video and appreciate your amazing work. and please keep doing this :).
ok
You are awesome 👍❣️
Awesome liked it!
thanks
What's the music at the end credits?
I really liked it. Shazam didn't pick it up either.🤔
Some people argue that space is constant time as we create only stack pointer and we are moving the nodes
Not sure what you mean, but no matter what, our structure underneath will hold n items if n items are given to us.
Right? Do you agree?
But queue itself has n items .Is it counted as O(n)??They are counting extra space excluded of n items
@@vishnuvardhan623 If you don't include the items in the actual queue (which is really 2 stacks underneath) then yeah, space will be O(1) since we aren't creating any auxiliary space past the actual items.
when we add items to the list, are you using the insert method or append?
either?
you are great thank you!
very nice explanation
thanks
哈哈,谢谢大兄弟清晰的解释😀 爱你
haha, sure, no problem
@@BackToBackSWE Hahahahaha, you understand this?
please make a video on egg dropping problem
ok
@@BackToBackSWE thanks
This video explains everything very well but I just have 1 questions, since the enqueue and dequeue methods take a fair ammount of code, should I put them into functions so I dont have to write it out each time?
Love your work 😍
thanks
Since u r soo good at explaining please I want u to explain step by step python code for it ...with black theme and mobile user friendly font size
Great video and give goal🔥
thx
Fuck man.. u are awesome...Probably the best explaination i ever had listened on algorithm....
wassup
@@BackToBackSWE Hey Ben, I just want to know do these tech companies owner really know ds and algos... Do guys like Jack Dorsey really knew ds and algos prior to creating twitter...
@@shivrajnag12 No
Brilliant !!
thanks
14:09 we acknowledge you!
ye
you explain much better , and you talk slower , i followed you better than last time
nice
I'm digging that banana republic shirt
I'm digging your vibe
Awesome!
hey
you are legendary
the legend isn't complete. give me a few more years.
@@BackToBackSWE you are on the right track! you got this man
The expected output for empty queue is 1 on Leetcode...
The code sample passes all test cases: github.com/bephrem1/backtobackswe/blob/master/Stacks%20%26%20Queues/queueWith2Stacks.java
Where did I misspeak?
Your code is correct, sry
@@wl7497 haha it is ok, I'm just making sure
Great...
hola mi amigo
Should have included the peek Operation too
Spoiler alert:
7:32 second stack
shocker
1 queue-hater disliked this video
thas' tru
stack is also an abstract concept though :)
yeah, where did I misspeak?
It's am-or-tized, not amor-tized.
ok
man this sucks (not the video!) i’ve been programming for a while and i understand this intuitively but i don’t understand any of the terminology like “linear in runtime” does that just mean it happens step by step i have no idea
Watch my asymptotic complexity video, it'll click. It is an asymptotic statement. When n is huge, what does the graph of operations look like? A line? A curve? But in a more thorough sense it is all about functions.
Back To Back SWE jeez dude this is a blessing you seem to care a lot and i appreciate that. anyway i’ll check that out wanna say your teaching style of the most “clickable” i’ve learned from on youtube
hhhhhhh u are so cute
wut
You are awesome 👍❣️