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.
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.
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 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.
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.
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!
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.
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
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.
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?
@@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); }
@@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.
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?
@@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...
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
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
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
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
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.
best thing about your videos is you don't feel bored
nice
This is a brilliant explanation. So clear!! And now I see a slinky.
you put lots of effort in your video's bro kudos to that...
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!
Wow, what a great explanation! It's very easy to understand and interesting to listen :)
Simple and superior as always.
thank you, you're really good at explaining concepts
thx
Your explanation is amazing! Thanks for this video!!!!
Brilliant explanation!!
thanks
best explanation
Thank you 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
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.
Amazing and Clear Explanations! Kudos!
thanks for watching
@@BackToBackSWE would love your videos on System Design if possible :)
Great explanation! Thanks for sharing, subscribed and liked the video.
thanks for the great channel ...you are my new hero! ✌️👍
We are all heroes
firstly I feared about dynamic programming but now it is a cakewalk after your watching videos and now queues and stacks also
great
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 :)
Awesome explanation. Thanks!
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
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)
Amazing article. Thank you very much.
sure
WHAT A GENIUS!
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
Loved it! Thank you for putting this great content out!
God bless you Benyam! Great content as always!
Thanks for uploading this...This is very helpfull to me.
Great explanation
كل الشكر التقدير لك من متابع عربي ❤❤
another wonderful video, Thank you so much
You make stuff damn simple. Thank you.
sure
how such a high quality video!🔥
great explaination. Really appreciate it
You are so helpful! Thank you for the excellent content!
You are awesome 👍❣️
Thanks Ben 😄😄
Love your video and appreciate your amazing work. and please keep doing this :).
ok
What's the music at the end credits?
I really liked it. Shazam didn't pick it up either.🤔
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
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
哈哈，谢谢大兄弟清晰的解释😀 爱你
haha, sure, no problem
@@BackToBackSWE Hahahahaha, you understand this?
very nice explanation
thanks
Awesome liked it!
thanks
icredible explanation..
thanks
when we add items to the list, are you using the insert method or append?
either?
Thank you so much!
Love your work 😍
thanks
Whoa. Where were you all this time 🙏
you are great thank you!
Great video and give goal🔥
thx
Brilliant !!
thanks
you explain much better , and you talk slower , i followed you better than last time
nice
please make a video on egg dropping problem
ok
@@BackToBackSWE thanks
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.
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?
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
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
14:09 we acknowledge you!
ye
Great...
hola mi amigo
Spoiler alert:
7:32 second stack
shocker
I'm digging that banana republic shirt
I'm digging your vibe
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
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
Should have included the peek Operation too
stack is also an abstract concept though :)
yeah, where did I misspeak?
1 queue-hater disliked this video
thas' tru
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 👍❣️