Learn Queue data structures in 10 minutes 🎟️
Bro Code
https://www.youtube.com/watch?v=nqXaPZi99JI

Transkript (automatisch erstellt)

0:00 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
0:06 so sit back relax and enjoy the show if you find this video helpful please remember to like
0:14 comment and subscribe your support will help keep this channel running whoa hey we're talking about cues today so cues
0:21 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
0:30 come first serve whoever's there first gets helped first so this is a collection designed for holding elements prior to processing
0:37 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
0:44 whoever approaches our register first it's first come first serve in other words it's fifo first in
0:50 first out unfortunately a wild karen appears and she would like to talk to the manager now karen is going to waste everybody's
0:57 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
1:03 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
1:11 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
1:18 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
1:26 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
1:34 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
1:41 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
1:48 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
1:57 to the end of our cue our tail and dequeueing is when we remove an object from the head of our queue
2:04 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
2:11 with a lot of you voted for data structures and algorithms using java so i'll probably stick with java then
2:16 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
2:25 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
2:31 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
2:40 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
2:49 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
2:58 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
3:05 class that implements q now taking a look at our java collections hierarchy there are two classes that implement
3:13 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
3:21 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
3:28 because we cannot instantiate a queue itself because it's an interface with that being said let's change equals new q
3:36 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
3:45 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
3:55 there are three methods that we inherit from the collections parent class add remove and element these will do approximately the same thing
4:04 as enqueuing dequeuing and peaking at the topmost element however they throw exceptions and according to the documentation
4:12 it's actually better to use this column of methods instead these will return a special value we have offer
4:19 which will enqueue or add an element to the tail of our queue poll will dequeue it will remove the head of our current
4:28 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
4:35 dedicated methods that we implement via the queue interface there are some additional methods too which we'll cover later
4:42 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
4:50 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
4:58 q dot offer and we will offer karen to the front of our queue and she would like to complain to the manager
5:06 next we have chad q dot offer chad then we have steve
5:17 and lastly harold okay now if we were to display our cue we'll place it within a print line
5:27 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
5:35 chad steve then harold at the tail one method that we implement from the q interface is the peak method
5:42 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
5:50 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
6:00 our cash register unfortunately karen is at the front of the line now to dq we can use the pull method
6:08 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
6:20 for practice so after polling twice karen and chad are now gone using pull a third time will remove
6:29 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
6:40 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
6:48 exception then so usually it's preferable to use this column of methods even though they're similar
6:54 these will not throw exceptions offer pull and peek now with cues there are some additional methods that you might be interested in
7:01 the q class will extend the collection class so the q class inherits everything that the collection class has
7:08 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
7:15 so within a print line statement i will type q dot is empty and if our queue is empty this will return true
7:24 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
7:33 that will be false there are people currently within our line so that is the is md method we can also check to see
7:40 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
7:52 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
8:00 certain object that we're looking for so within a print line statement i will type q dot contains and then pass in an
8:09 object let's check to see if harold is at the back of the line he's been waiting here patiently
8:14 q dot contains herald and according to the contains method herald is in fact within our line that is true
8:21 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
8:30 yeah or true that's kind of how the contains method works so these are three useful methods that cues
8:37 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
8:44 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
8:51 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
8:58 turn to be displayed so with a keyboard buffer letters should appear on the screen in the order that they're pressed right
9:05 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
9:12 then page two and just follow that pattern and as we discussed before they're used in linked lists priority queues as well as
9:20 breadth first search algorithms well everybody in conclusion a queue is a fifo data structure first
9:27 in first out it's a collection designed for holding elements prior to some sort of processing it's a
9:34 linear data structure imagine a bunch of people waiting in line to enqueue that means to add an element to the tail
9:42 of our queue to the end we can use the offer method in java to dequeue we would use the poll method in java
9:50 that will remove the element at the head of our queue so that is the q data structure in the comments down below
9:57 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
10:05 science