Part 3 - How to implement a Queue in Java - Dequeue Operation
Part 3 - How to implement a Queue in Java - Dequeue Operation
► ►Personal queries? - Follow me on LinkedIn - https://www.linkedin.com/in/dinesh-va…
► ►This video is part of my Complete Data Structures and Algorithms Course playlist: • Data Structures and Algorithms in Jav…
►Source Code - https://github.com/dinesh-varyani/ds-…
►Click here to subscribe - https://www.youtube.com/user/hubbersp…
Watch all my playlist here:
►Data Structures and Algorithms Course playlist: • Data Structures and Algorithms in Jav…
►Mastering JUnit 5 - https://www.youtube.com/playlist?list…
►Mastering Mockito 3 - • Mockito 3 Tutorials
►Analysis of Algorithms - • Analysis of Algorithms
►Linked List Data Structures - • Linked List Data Structures
►Array Data Structures - • เพลย์ลิสต์
►Stack Data Structure - • Stack Data Structure
►Queue Data Structure - • Queue Data Structure
►Binary Tree Data Structure - • Binary Tree Data Structure
►Graph Data Structure - • Graph Data Structure
►Binary Heap Data Structure - • Binary Heap Data Structure
►Trie Data Structure - • Trie Data Structure
►Dynamic Programming Algorithms - • Dynamic Programming Algorithms
►Hashing Data Structures - • Hashing Data Structures
►Sorting and Searching - • Sorting and Searching
►String Algorithms - • String Algorithms
►Java Programming Tutorial - • Java Programming Tutorial
►Design Patterns in Java - • Design Patterns in Java
Follow Me On Social Media
►Website - http://www.hubberspot.com
►Facebook - https://www.facebook.com/dinesh.varyani/
►Instagram - https://www.instagram.com/dinu.varyani/ Get complete free course on Data Structures and Algorithms at - • Data Structures and Algorithms in Jav… .
Subscribe to the channel for all free courses at - https://www.youtube.com/user/hubbersp…
🙏 Thank you for your continuous love and support. I humbly request you to help this channel grow more, for that please Like, Share and Subscribe to my channel. Your support will motivate me to add more valuable content.
|| LIKE || SHARE || SUBSCRIBE ||
For free complete course download our android app on Visualizing Data Structures and Algorithms -
https://play.google.com/store/apps/de…
CLICK TO DOWNLOAD COMPLETE SOURCE CODE -
https://github.com/dinesh-varyani/ds-…
Visit my blog for more such free videos -
http://www.hubberspot.com
Content
1.65 -> Hello friends, welcome to my new data
structures and algorithm in Java tutorial
5.88 -> series video.
7.95 -> Friends. In this tutorial we will continue
with the implementation of the queue.
13.86 -> In our previous tutorial, we discussed how to
add an element in a queue in Java. So in this
19.41 -> tutorial we'll discuss how we can remove an
element from a queue in Java.
25.14 -> So, friends in my previous tutorial, I added
three elements into the queue by date as 1015
31.29 -> and 20. So, in this tutorial, we will discuss
how we can remove an element from a queue
37.17 -> which is nothing but a dq operation.
40.35 -> So, here I will take the same example. And
you can see that q has three elements the
45.69 -> front is pointing to the first node and rear
is pointing to the last node and length is
50.76 -> three.
53.4 -> So, here you can see this is the algorithm
for a dq operation. Now, let's see the
57.6 -> demonstration of this algorithm step by step.
63.36 -> Now, in the first step, we will check their
whether queue is empty or not. So, currently,
68.13 -> if you see length is three, and we know that
the queue contains three nodes. Therefore,
73.32 -> queue is not empty. So, the condition in a
block comes out to be false.
80.97 -> Now friend as we want to remove an element
from a queue, so, here you can see the return
85.47 -> type of dq method is an integer type, we are
actually removing an element from the queue
90.21 -> and we are sending back the data part of it.
93.72 -> So, in order to store the data, somewhere, we
are creating an integer variable by name
98.76 -> result, and we are storing front out data
into it.
103.53 -> So friends, in my previous tutorial, we
discussed that Q is a list with fewer
108.63 -> restrictions, where the elements are inserted
at one end, which is the rear end and
113.97 -> elements are removed at one end which is the
front end. So friends, the restriction which
118.98 -> we impose on a list makes it a queue and
therefore the queue is called as FIFA list
124.17 -> which is first in first out. So here you can
see by first in first out we mean the limit
130.23 -> inserted first would be the first one to be
removed.
134.07 -> So, in my previous tutorial, we discussed
when we inserted the elements into the queue,
138.63 -> we inserted first and then we inserted 15 and
then we inserted 20 is using the rear end.
145.56 -> Now in order to remove an element we know
that 10 was inserted first so now 10 would be
151.17 -> removed first. So this is nothing but a FIFA
property first in first out.
157.41 -> So let's see how we can use the front end to
remove the notes which are inserted first.
162.96 -> So, here after this line gets executed
166.17 -> results holds a value of 10 because the note
10 was the node first inserted into the cube
172.23 -> therefore this node will be removed first
175.95 -> moving it
178.77 -> now friends in order to remove this north
from the queue, we know that it is being
182.97 -> referred by this front node and if you break
the link from front to this node, then this
189.36 -> node can be removed easily.
192.3 -> So in order to do that, what we are doing we
are simply assigning the value of friend dot
196.86 -> next to front. So here we are simply
assigning front next value to front. So that
203.25 -> once this node is remote 15 becomes our new
front. So therefore we are simply assigning
208.71 -> the value of front dot next to front. So it
would look something like this.
216.66 -> Moving ahead
219.84 -> then we are checking whether the front is
equal to null or not. So currently, you can
224.46 -> see front is pointing to a second node
therefore it's not null. So the condition in
229.89 -> a block comes out to be false.
232.44 -> Moving ahead.
235.44 -> So friends as we have removed the reference
of friend from this note, therefore, this
240.66 -> node will be garbage collected. And you can
see once this node is remote, we will
246.03 -> decrement the length by one. So currently the
length is three and after the removal of this
250.89 -> node length becomes two.
253.98 -> So we simply decrement the length by one
moving at
259.38 -> and in the final step will simply return the
value stored in the result.
266.7 -> So friends when the dq method is executed,
the queue has two elements and length is two.
273.24 -> Now friend, let's suppose we call dq method
once again.
279.9 -> So here first we check whether the queue is
empty or not. So currently, q has two notes,
284.97 -> therefore it's not empty.
288.42 -> And then we will simply store front or data
into the result. So it would look something
293.79 -> like this, that we are storing the data into
the list node which has been pointed by the
298.26 -> front so now
300 -> Result contains the value is 15.
302.82 -> Moving ahead
305.79 -> now, in order to remove this node from a
queue, we have to break this link, because a
311.1 -> friend is referring to this node, then this
node would not be removed. So, in order to
316.14 -> break this link, we are simply assigning a
friend or next value to front.
321.42 -> So, it would look something like this
327.84 -> moving ahead
330.27 -> then we are checking with the front is equal
to null or not. So, front is pointing to this
335.07 -> third node, therefore, it's not equal. So,
the condition in a block comes out to be
338.7 -> false.
341.49 -> And here as we removed the link upfront to
this node, so, now this node has no reference
346.5 -> to it, therefore, it will be removed easily.
349.8 -> We know that now, q has only one element
therefore, we will decrement the length of
353.82 -> one
356.91 -> moving at
358.83 -> and in the final step will simply return the
value stored in the result which is 15.
369.84 -> So, friends, when the dq method is executed,
373.98 -> he was only one element where front and rear
both point to that particular element,
378.96 -> because this is the only element left.
382.05 -> Now, I suppose called dq again.
387.09 -> So, first we'll check whether Q is empty or
not. So, currently q has lent one debt means
392.73 -> it has one node, therefore, it's not empty.
So, the condition in a block comes out to be
397.62 -> false
400.2 -> then we will simply store the value of front
or data into result because we want to return
405.96 -> this value.
408.45 -> So, now resolve will hold the value of 20.
Moving ahead
414.3 -> now friends, we need to take an especial care
when we removed the last element from a queue
419.28 -> because of the queue contents only one
element and if you want to remove that
423.03 -> particular element, then we need to break two
links, one is up front and others have rear
429.57 -> because if any of the link is referring to
this node, then this node would not be
433.35 -> removed.
435.03 -> So therefore here just simply assigning the
value of friend or next to front, so it would
440.16 -> look something like this.
444.09 -> So now front is assigned with its next value
which is null.
448.26 -> Moving at
450.84 -> now we'll check whether front is pointing to
null or not. So currently, the front is
455.22 -> pointing to null. Therefore, the condition in
a block comes out to be true.
461.67 -> And as we discussed that, we need to break
both the links in order to free this node. So
466.98 -> therefore, we'll simply assign the value of
null to rear. So now this link will be
471.66 -> removed. So it would look something like
this.
477.42 -> So now front and rear both are pointing to
null.
482.61 -> So friends as this node is having no
reference therefore, this node will be freed
487.11 -> easily.
488.7 -> So once this node is removed, will decrement
the length by one because we know there are
492.93 -> no elements left. So we'll simply decrement
the value of length by one.
497.82 -> So, now land becomes zero because we have
removed all the nodes.
504.03 -> So, in the final step will simply return the
value 20.
511.23 -> So, friends, once this method is executed,
this node gets freed up.
518.04 -> And as we know that now front and rear both
pointing to null therefore, the list is empty
524.28 -> and length is zero. So, friends, if we again
call dq method
531.84 -> then the first I will check with a queue is
empty or not. So, here you can see front is
537.15 -> pointing to null responding to null and we
also know the length is zero therefore Q is
542.43 -> empty. So there are no elements left to be
removed.
547.02 -> So, the condition in a flow comes out to be
true and will simply throw in no such element
552.15 -> exception because there are no elements left
to be rebuilt.
559.5 -> So friends in this slide we discussed the
demonstration of the dq method. Now let's go
564.66 -> to eclipse and see the working code.
569.67 -> So friends in my previous tutorial, I created
on class by name queue, we created few
575.25 -> instance variable of type list node, one of
which was front and other was rear. We also
581.16 -> created an integer variable which actually
store the length of the queue. And then we
586.53 -> have created few methods. One was length is
empty and in queue.
594.21 -> So basically we created in queue method which
could insert the elements into the queue.
600 -> In here, if you see, and we also saw that we
are added three elements. And when we printed
605.88 -> that you it printed something like
610.889 -> 10 1520. So, so I will take the same list,
and we'll perform dq operation on it. So
618.779 -> first let's write the dq method.
621.9 -> So public,
624.9 -> we know that the return type of it would be
integer, so int dq.
634.53 -> Now, the first step we do is we check
639.24 -> whether the queue is empty or not so is
empty.
645.63 -> Now, if that queue is empty, we know that
there are no more elements left to be
649.86 -> removed. Therefore, we throw an exception
655.02 -> as no such
659.04 -> element exception
664.14 -> and we pass a string s, Q is already
670.92 -> empty.
674.52 -> Moving ahead,
676.59 -> now we know that when we remove an element
from a queue, we are returning the data part
681.33 -> of it. So therefore, we'll create
684.6 -> an integer variable by name result, and we'll
store front data to it moving at Isaiah got
693.39 -> the data of the front node will simply
traverse front towards next value by
699.78 -> assigning front next to front.
703.74 -> And then we simply check
708.12 -> where the front is equal to null or not. So,
if Rand is equal to null, we know that we
715.08 -> have to make the rear also null
717.81 -> which you saw in the slide.
721.23 -> Moving
722.94 -> now, as you remove the node from a queue, we
have to decrement the length by one
729.96 -> and finally, we are returning the result.
734.34 -> So friends, this is the port for dq method
whose demonstration we saw in the slide. Now,
739.47 -> let's test the working of this method.
742.65 -> So, initially, we are inserted three nodes.
747 -> Now, let's say I declare one node
752.1 -> and then I print the queue again.
758.94 -> So, if I run the code,
764.58 -> so, you can see, when we inserted three
nodes, first 10 was inserted, then 15 got
769.71 -> inserted, then 20 got inserted. So the
insertion was at the rear end. Now, when we
775.26 -> are doing a dq 10 was removed, because we are
removing a node from the other end, which is
780.27 -> the front end. So that's us a fee for list,
where we insert the node at one end, which is
786.09 -> the rear end and where we remove the node
from the other end, which is the front end.
790.47 -> So, now as you can see, 10 was the first
element of inserted therefore, it got removed
795.66 -> first. Now, if I call dq again.
805.59 -> So, you can see 15 also got remote and if I
call you once again.
817.98 -> So, here you can see nothing got printed,
because we have removed all the elements from
822.12 -> the queue. And when we printed the list,
826.92 -> we can see when the list is empty, we are
simply returning from the print method. So
831.96 -> therefore, nothing got printed.
835.35 -> And now a list is empty. If I call dq one
more time, and if I run the code,
842.91 -> we get an exception, saying no such element
exception, Su is already empty.
850.02 -> So friend, this was the working of dq method
sovereigns. Apart from this in queue and dq
856.11 -> method, q also has two more methods by name
first and last. So when we call the first
862.8 -> method,
864.36 -> we get the value stored at the node which has
been referred by front and when we call the
869.22 -> last method, we get the value stored in the
list node which is being referred by the
874.23 -> rear.
876.03 -> So here we simply create public int first.
884.19 -> So your first we simply check that whether
queue is empty, because if queue is empty,
891.36 -> then we know that front and rear both points
to null.
897.24 -> Therefore we check whether queue is empty or
not.
900 -> After this check, we simply return value
stored in the front.
906.12 -> So we simply return front door data.
910.83 -> And you also write one more method, say last
916.199 -> which is very similar, we'll first check
whether the queue is empty or not. And if the
921.149 -> queue is not empty, then we will simply
return
924.9 -> Ria dot data.
929.67 -> So friends, let's test the working of first
and last method. So, here I will just remove
934.53 -> this thing. So we inserted three notes by
values 1015 and 20. So far on the code,
945.03 -> so you can see front is pointing to a node
event data is 10 and rear is pointing to a
951.63 -> node heaven data is 20 as system
956.31 -> so if I simply print q dot
960.96 -> first
966.45 -> and Q dot last.
972.39 -> And if I run the code
975.84 -> so you see it printed 10 and 20, because 10
is being referred by front and 20 is being
982.98 -> referred by a rear.
985.08 -> So friends in this tutorial, we discussed
about the dq operation. We discuss about a
990.12 -> few of the methods like first and last. So
this was basically all about the
995.37 -> implementation of Q. I hope you liked this
video. Please like comment, share, and
1000.8 -> subscribe my YouTube channel. Thanks Have a
nice day.
Source: https://www.youtube.com/watch?v=27yOGyZow6U