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
Tipp auf eine Zeit â das Video springt genau dorthin.
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
Zum Nachlesen
Warteschlange (Datenstruktur)In der Informatik bezeichnet eine Warteschlange (englisch queue [kju]) eine hĂ€ufig eingesetzte Datenstruktur. Sie dient als Puffer zur Zwischenspeicherung âŠ
DatenstrukturIn der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine âŠ
VorrangwarteschlangeDen Elementen, die in die Warteschlange gelegt werden, wird ein SchlĂŒssel mitgegeben, der die Reihenfolge der Abarbeitung der Elemente bestimmt.
DequeHierbei handelt es sich um eine Datenstruktur Ă€hnlich der Warteschlange oder des Stapelspeichers. Es kombiniert die Eigenschaften beider Datentypen. Der âŠ