Stacks & Queues | Data Structures in JavaScript

hello and welcome to part one of a little video series I am doing on data structures today we will be covering stacks and queues we will learn what they are why they are useful and how to implement them in JavaScript so what are stacks and queues stacks and queues our collections they are linear data structures with essentially the same meaning that they do in everyday life so when you visualize a stack you can think of a stack of plates and when you visualize a queue you can think of a line of people at anciently theater when you have a stack you can only add or remove things from the top of the stack you wouldn't normally pull a plate from the middle of the stack or take from the bottom of the stack it just makes sense to take from the top if you've got your stack of plates the last place you go in the stock is the first plate to go out so stacks are last in first out the only operations we are concerned about with a stack are to push or add to the stack pops or remove from the stack and pink which is to just look at the last item in the stack without adding or removing it one application of the stack in the real world is a text editor or graphics editors undo redo feature every time you do something your actions will get added to an undo stack and when you hit undo those actions get plucked from the stack and also pushed into a reduce neck a queue is very similar to a stack but the primary difference between them is that stocks are last in first out while queues are first in first out considering our line of people at the movie theater you can always add more and more people to that queue but person at that front of the cube will always be the first person to leave after which point the following people in line shuffle on forward the first person in the queue is always the first person out so first in first out the operations that queues work with our NQ or addict to the queue and DQ which is removing from the cube one application of hue in the real world is a printer queue so you can queue up multiple jobs for printing and the printer will process and print each of those jobs in the order it was given we can actually implement stacks and queues with Java scripts Bilgin array methods so let's initialize our stock as an empty array and remember the methods we want on our stack are push top and peak so conveniently push and pop are exactly the same as the JavaScript array prototype methods so we can stock dot push dog and a bear and if you take a look at her staff it's now got three animals in it when we pop them the stock it'll return the last item in the stock and remove that item so staff dot pop we expect to return bear and if you look at our stock it should only have two items in it dog and cat now if we peek at our stock it'll just show us the last item in the stock so we would expect our peak method to return cat peek however is not actually a JavaScript array prototype method so to look at the last item in the stash we would simply access the stack at its last index so that would be stacked length minus 1 and that should show us our cast so now let's implement the stock using javascript classes so let's make a class stuck with a constructor and our constructor will have two properties this storage is set to an empty object and this size set to 0 and then we'll have our pushpop and peek methods our push method will take an element and when we push into our staff we will increase the size by one so let's increment this size and then we'll store that element in this storage as a key value pair with the key being the size and the value being the element itself now when we popped from the stack we want to return the last item in the stack and also remove it in the stuff so let's do a temporary variable that will store that removed items so we'll let removed equal is not storage just dot size and then we'll return remove now we should delete that actual item so delete this top storage list dot size and then we'll decrement the size finally the peek method is simply returning this storage this dot size so now let's test our stack by creating a new one and then let's put some things into the stack now let's take a look at our stack we've got a stack object with the property of storage holding all of our elements and we've also got these size property here now if we pop them are stuck we're going to expect it to return there and if we look at our stack it's only got dog and cat in it bear has been removed and now finally if we peek at our stock we should just see the last element inside it which would just be cat now let's look at how to implement a queue in JavaScript it's very very similar once again let's just use the JavaScript array methods so will constitute equal empty array and then remember the methods that we're concerned with fur QR NQ on Q and Q and EQ just a sidebar there is another data structure called a deck spelled like that so don't confuse that with DQ so recall that queues are first in first out so the equivalent JavaScript array methods for NQ & DQ respectively would be push and shift because push will add to the end of the array probably point like this push will add to the end of your array and then shift will remove from the beginning of your array so if we queued up push let's do like an aquatic theme this time seahorse so now we've added three sea animals to our queue and now we want its DQ and when we shift we expect this to return the item that's at the front of our array so that would be our seahorse now when we look at our queue again all that's left are the dolphin and whale shark and if we shift one more time we expect this to return dolphin the animal at the front of our queue and then if we look at our queue again only the whale shark is left now let's look at implementing the queue with JavaScript classes so let's make a class Q instructor and this time we're going to keep track of this dot storage this dot head and this dot tail of course we've got our NQ and GQ methods when we NQ still don't know if it's produced in Hue or on cue earlier today I was building an app with my team and we didn't know whether it was pronounced favicon or favicon it's just one of those things like you just try to not speak out loud with NQ we've got an element once again so we're going to add elements to our cues storage through the tail so we would have this storage at this tail equal the element and then we'll increment the tail once again with DQ much like the stack pop method we want to return the removed elements so we'll do let me let remove equal this dot storage this dot head this time because we're removing from the front of our storage object we're adding from the back removing from the and then we're going to return removed let's delete this storage this stuff pad and then increment ahead so it moves forward one position finally let's test our queue once again with cost Q equal let's on Q some sea animals and if we look at our queue we've got a queue object with three sea animals instorage ahead a zero and a tail at three now if we D Q we expect this to return the animal at the front of our queue so we expect to see a seahorse let's look at our queue once more the seahorse has been deleted and we now have storage with dolphin and whale shark and the head moved to position one let's DQ one more time we expect to return dolphin and if we look at the queue once more we have one si animal left in the queue in summary we learned that stacks and queues are both linear data structures there are just collections of items with a very similar meaning to their real-life counterparts the primary difference between the stack and the queue is that stacks are last in first out while queues are first in first out we learn some common applications of steps and queues in the real world and finally we looked at implementation of stacks and queues in JavaScript using the built in array prototype methods and JavaScript classes it is also certainly possible for stacks and queues to show up in technical interviews so you should consider how these data structures might actually be useful in solving certain types of problems there's just one interview problem where you're given an input of a string of parentheses and you have to determine if they're valid so if you're given a string of parenthesis curly braces and it's brackets you could actually use a stack to determine whether all of those parentheses close each other in a valid way as for queues I think I have seen some problems where you implement a queue using two steps or you can use a queue in a stack to determine if where it is a palindrome so it's certainly possible for these data structures to show up in toy problems so it's really good to brush up on them and that concludes today's video on stacks and queues this is part of a little video series I'm doing on data structures so please subscribe so you don't miss the next one and do leave a like if you thought this was helpful thank you for watching and I'll see you in the next video [Music]

Channel: beiatrix

Views: 10,575

Rating: 4.9931741 out of 5

Keywords: javascript, programming language, software, data structures, stacks, queues, object oriented programming, methods, computer science, software engineering, software development, software developer, software engineer, screencast, tutorial, education, array, arrays, class

Id: 1AJ4ldcH2t4

Length: 12min 49sec (769 seconds)

Published: Fri Jan 25 2019