Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Learn Queue data structures in 10 minutes đïž
Das Wichtigste aus dem Video
Transkriptautomatisch erstellt · 78 Zeilen
- hey what's going on everybody it's you bro hope you're doing well in this video i'm going to explain cues in computer science
- so sit back relax and enjoy the show if you find this video helpful please remember to like
- comment and subscribe your support will help keep this channel running whoa hey we're talking about cues today so cues
- are a fifo data structure not to be confused with fifa fifo as in first in first out an example would be a line of people it's first
- come first serve whoever's there first gets helped first so this is a collection designed for holding elements prior to processing
- it's a linear data structure here's an example imagine that we're a cashier and we're selling tickets to a concert we will help
- whoever approaches our register first it's first come first serve in other words it's fifo first in
- first out unfortunately a wild karen appears and she would like to talk to the manager now karen is going to waste everybody's
- time so it's going to be a while in the meantime chad enters the line he will enter in at the back and wait his turn
- followed by steve and then harold so karen is at the head of our queue our line and harold is all the way at the back our tail
- as you can see harold is very anxious right now once karen has been defeated chad will move to the head of our queue so
- chad will now be helped next and harold will still be at the tail until somebody else enters the line once chad has been helped he will move
- out of our queue and steve is at the head now and the tail will move as well and then once steve has been held harold
- is the only one currently waiting in line for his tickets he will be at both the head and the tail of our queue so that's kind of
- how a queue works it's first come first serve fifo first in first out if you were here first then you will be helped first
- now the concepts of adding and removing objects from a queue are known as both enqueuing and dequeueing enqueuing is the concept of adding an object
- to the end of our cue our tail and dequeueing is when we remove an object from the head of our queue
- now what methods do you need to enqueue and dq from a queue well it really depends on the programming language that you're working
- with a lot of you voted for data structures and algorithms using java so i'll probably stick with java then
- here's an example now to enqueue and dq we need well a queue so let's create one q then we need to list the data type of
- the objects that we're going to add to this queue let's work with strings because strings are objects and they're fairly simple
- and i will name this queue q equals new now check this out i will attempt to create a queue object and instantiate it and the data type is string and i will
- add a constructor now we cannot instantiate the type q here's the reason why so if we take a look at the queue class
- right here q is actually an interface and not a class and based on our lesson on interfaces we cannot create an instance of an interface
- an interface is meant to be more of like a template that we can apply to another class so to utilize q technology we need a
- class that implements q now taking a look at our java collections hierarchy there are two classes that implement
- cues one of which is the linked list and the other is the priority queue now priority queues they will rearrange their elements based on a certain
- priority so they wouldn't be a good example so to utilize the features of a queue we are going to create a linked list
- because we cannot instantiate a queue itself because it's an interface with that being said let's change equals new q
- to equals new linked list we won't be focusing on any of the features of linked lists we'll save that for another video maybe the next one i
- haven't decided yet so we will only cover the features that linked lists will utilize via the q interface now with the q interface
- there are three methods that we inherit from the collections parent class add remove and element these will do approximately the same thing
- as enqueuing dequeuing and peaking at the topmost element however they throw exceptions and according to the documentation
- it's actually better to use this column of methods instead these will return a special value we have offer
- which will enqueue or add an element to the tail of our queue poll will dequeue it will remove the head of our current
- queue and then there is also peak it will not remove the head but it will examine it and return it so those are the three
- dedicated methods that we implement via the queue interface there are some additional methods too which we'll cover later
- which we inherit from the collections class so let's begin by offering a bunch of people to our queue this is how we enqueue or add
- elements to our queue so first in our line we have karen so to add her to the queue we would type the name of our queue
- q dot offer and we will offer karen to the front of our queue and she would like to complain to the manager
- next we have chad q dot offer chad then we have steve
- and lastly harold okay now if we were to display our cue we'll place it within a print line
- statement we will pass in q as an argument and this should display our q in order first we have karen at the head then
- chad steve then harold at the tail one method that we implement from the q interface is the peak method
- we can use the peak method to examine and take a look at the object at the head of our queue we're not actually going to remove
- the object at the head of the cube but take a look at it so within a print line statement i will use q dot peak method and after peaking over
- our cash register unfortunately karen is at the front of the line now to dq we can use the pull method
- so type q dot poll and this will dequeue your q so karen is no longer at the head of our queue so let's pull a couple more times
- for practice so after polling twice karen and chad are now gone using pull a third time will remove
- steve and lastly now the nice thing about the poll method is that it will not cause an exception according to the java documentation you
- can use element to peak but it will throw an exception so if i was to use element at the end this would cause an
- exception then so usually it's preferable to use this column of methods even though they're similar
- these will not throw exceptions offer pull and peek now with cues there are some additional methods that you might be interested in
- the q class will extend the collection class so the q class inherits everything that the collection class has
- and there's some pretty useful methods within here i'll show you a few so the first is that we can check to see if our queue is empty
- so within a print line statement i will type q dot is empty and if our queue is empty this will return true
- so if i move this line of code after we offer a bunch of strings a bunch of people to our queue if we check to see if our queue is empty
- that will be false there are people currently within our line so that is the is md method we can also check to see
- the size of our queue how long is our line system.out.printline q dot size and the size of our line our q is four four objects we have four
- people waiting in line to be helped so that is the size method and another is the contains method we can check to see if our queue has a
- certain object that we're looking for so within a print line statement i will type q dot contains and then pass in an
- object let's check to see if harold is at the back of the line he's been waiting here patiently
- q dot contains herald and according to the contains method herald is in fact within our line that is true
- however this method does not give the index the position in which herald is in imagine that we yell out hey harold are you there and he yells back
- yeah or true that's kind of how the contains method works so these are three useful methods that cues
- inherit from the collection class now where could cues be useful they're actually used in quite a number of things but here's a few examples that
- came to mind so one that can be used in keyboard buffers have you ever typed so fast that the computer couldn't render all the
- characters onto the screen and all of those characters were added to a buffer they were all displayed in sequence and they were waiting for their
- turn to be displayed so with a keyboard buffer letters should appear on the screen in the order that they're pressed right
- first in first out they're also used in printer cues print jobs should be completed in order so we would start with page one
- then page two and just follow that pattern and as we discussed before they're used in linked lists priority queues as well as
- breadth first search algorithms well everybody in conclusion a queue is a fifo data structure first
- in first out it's a collection designed for holding elements prior to some sort of processing it's a
- linear data structure imagine a bunch of people waiting in line to enqueue that means to add an element to the tail
- of our queue to the end we can use the offer method in java to dequeue we would use the poll method in java
- that will remove the element at the head of our queue so that is the q data structure in the comments down below
- let me know what you would tell karen if she asked to speak with your manager and that ladies and gentlemen is the q data structure in the field of computer
- science