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

preview_player
Показать описание
📹 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)

Space: O( n )

We upper bound space to the maximum amount of items that we will ever store.

++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++

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<E> 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.

BackToBackSWE
Автор

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.

angelluisgarciaguzman
Автор

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.

levifoster-grundy
Автор

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!

cristina-gabrielagavrila
Автор

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.

tushar
Автор

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.

longuyen
Автор

best thing about your videos is you don't feel bored

shivamchauhan
Автор

I like how they nailed the staged rewind part. Good content bro. Keep it up.

abanerjee
Автор

you put lots of effort in your video's bro kudos to that...

arunkumar
Автор

This is a brilliant explanation. So clear!! And now I see a slinky.

AlekVila
Автор

thank you, you're really good at explaining concepts

jonathanharris
Автор

firstly I feared about dynamic programming but now it is a cakewalk after your watching videos and now queues and stacks also

rakeshreddyabbireddy
Автор

Your explanation is amazing! Thanks for this video!!!!

jussaraambrosio
Автор

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!

helenashatalova
Автор

thanks for the great channel ...you are my new hero! ✌️👍

b
Автор

Wow, what a great explanation! It's very easy to understand and interesting to listen :)

kraanas
Автор

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?

yanxichen
Автор

Great explanation! Thanks for sharing, subscribed and liked the video.

ricardopereira
Автор

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)

dinohunter
Автор

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.

pranavnyavanandi