1 00:00:00,650 --> 00:00:01,550 Hi everyone. 2 00:00:01,550 --> 00:00:04,460 In this question we are going to design a queue. 3 00:00:04,490 --> 00:00:05,480 Now let's read it. 4 00:00:05,480 --> 00:00:12,410 Implement a queue first using an array and in the second part with the queue class using a linked list. 5 00:00:12,410 --> 00:00:14,870 Now we can implement a queue in multiple ways. 6 00:00:14,870 --> 00:00:20,510 In this question, we are going to see how we can implement or design a queue first using an array and 7 00:00:20,510 --> 00:00:21,590 then using a linked list. 8 00:00:21,590 --> 00:00:27,170 One should be able to add to the queue and remove from the queue following the Fifo property which is 9 00:00:27,170 --> 00:00:28,640 first in first out. 10 00:00:28,670 --> 00:00:34,760 Now a queue is a Fifo data structure, as we have seen previously, and Fifo stands for first in, first 11 00:00:34,760 --> 00:00:35,060 out. 12 00:00:35,060 --> 00:00:38,300 So that is what we also see in real life, right? 13 00:00:38,300 --> 00:00:41,450 You may be standing in a queue for buying a ticket. 14 00:00:41,450 --> 00:00:46,310 So the first person who came into the queue is the first one who comes out of the queue. 15 00:00:46,310 --> 00:00:49,910 Now in JavaScript there is no inbuilt queue data structure. 16 00:00:49,910 --> 00:00:55,340 So that's why in the ideal case, we will be implementing a queue with the linked list to get the optimum 17 00:00:55,340 --> 00:00:56,000 performance. 18 00:00:56,000 --> 00:00:59,240 Let's see why that is the case in the future part in this video. 19 00:00:59,240 --> 00:01:03,980 Now let's first try to understand how we can implement a queue with a simple array. 20 00:01:03,980 --> 00:01:05,420 Now let's say we have an array. 21 00:01:05,420 --> 00:01:07,850 So we can say const r is equal to new array. 22 00:01:07,850 --> 00:01:09,020 So this is our array. 23 00:01:09,050 --> 00:01:14,570 Now we need to be able to add to the array and remove from the array following the Fifo property first 24 00:01:14,570 --> 00:01:15,290 in first out. 25 00:01:15,290 --> 00:01:19,460 Now for this we are going to use the push and shift methods of the array. 26 00:01:19,490 --> 00:01:20,810 These are inbuilt methods. 27 00:01:20,810 --> 00:01:25,640 Now again remember shift is the method used to remove from the beginning of an array. 28 00:01:25,700 --> 00:01:27,590 Now let's look at an example. 29 00:01:27,590 --> 00:01:29,600 So let's say this is our empty array. 30 00:01:29,600 --> 00:01:32,210 And let's push in a few values into the array. 31 00:01:32,210 --> 00:01:34,310 So we push in one over here. 32 00:01:34,310 --> 00:01:37,550 And we are going to push in two and three as well. 33 00:01:37,550 --> 00:01:40,700 So first one was pushed in then two and then three. 34 00:01:40,700 --> 00:01:41,150 All right. 35 00:01:41,150 --> 00:01:44,390 Now again remember pushing adds to the end of the array. 36 00:01:44,450 --> 00:01:49,310 Now when we are going to shift we will be taking the first element out again. 37 00:01:49,310 --> 00:01:51,080 Shifting is removing from the beginning. 38 00:01:51,080 --> 00:01:53,330 So we will get back this one over here. 39 00:01:53,330 --> 00:01:55,790 And that's what entered the array first. 40 00:01:55,790 --> 00:01:58,340 So that's why this follows the Fifo property. 41 00:01:58,340 --> 00:02:03,170 Now push over here in the case of an array is a constant time operation. 42 00:02:03,170 --> 00:02:04,130 So that's efficient. 43 00:02:04,130 --> 00:02:09,890 But shifting from an array which is removing from the beginning is a o of n operation. 44 00:02:09,890 --> 00:02:11,540 The time complexity is O of n. 45 00:02:11,540 --> 00:02:15,500 That's because we have to reindex the remaining elements in the array. 46 00:02:15,500 --> 00:02:17,150 So this is not efficient. 47 00:02:17,150 --> 00:02:21,590 So that's why let's see how we can implement a queue with a linked list. 48 00:02:21,590 --> 00:02:25,370 Now we can either use a singly linked list or a doubly linked list. 49 00:02:25,370 --> 00:02:27,890 In this video we are going to use a singly linked list. 50 00:02:27,890 --> 00:02:31,310 Now you can implement it with a doubly linked list also if you want. 51 00:02:31,340 --> 00:02:35,540 And it's just going to be minor changes from what we are going to see over here. 52 00:02:35,540 --> 00:02:36,860 Now let's continue. 53 00:02:36,860 --> 00:02:40,010 Now we are going to have a node class and a queue class. 54 00:02:40,010 --> 00:02:43,280 Now we will use the node class to create our nodes. 55 00:02:43,280 --> 00:02:47,660 Now this is a this is just like what you've seen in the case of a singly linked list. 56 00:02:47,660 --> 00:02:52,730 So every value that we are going to insert into the queue will be made a node and added as a node. 57 00:02:52,730 --> 00:02:53,030 All right. 58 00:02:53,030 --> 00:02:57,800 Now in the case of a queue adding an element is called n queue. 59 00:02:57,800 --> 00:02:59,390 So that's just the nomenclature. 60 00:02:59,390 --> 00:03:02,750 And removing from a queue is called d queuing. 61 00:03:02,750 --> 00:03:03,050 All right. 62 00:03:03,050 --> 00:03:04,820 So we will be using these words. 63 00:03:04,820 --> 00:03:06,230 So enqueue and dequeue. 64 00:03:06,230 --> 00:03:09,380 And over here we have our queue class. 65 00:03:09,380 --> 00:03:10,760 And then we have our constructor. 66 00:03:10,760 --> 00:03:12,380 And we are tracking first and last. 67 00:03:12,380 --> 00:03:13,940 And both are initialized to null. 68 00:03:13,940 --> 00:03:16,700 When we first create an object for this class. 69 00:03:16,700 --> 00:03:18,620 And the size is equal to zero. 70 00:03:18,620 --> 00:03:22,100 Now we need to implement this as a Fifo data structure. 71 00:03:22,100 --> 00:03:23,120 First in first out. 72 00:03:23,120 --> 00:03:27,830 For this, we will be adding at the end of the queue or of the linked list. 73 00:03:27,830 --> 00:03:28,130 All right. 74 00:03:28,130 --> 00:03:32,120 So this is again a linked list and removing from the beginning of the linked list. 75 00:03:32,120 --> 00:03:37,190 So this is how we are going to implement our queue using a linked list and adding at the end in a linked 76 00:03:37,190 --> 00:03:43,040 list and removing from the beginning in a linked list in a singly linked list is a constant time operation. 77 00:03:43,040 --> 00:03:49,160 So that's why implementing our queue with a linked list is efficient compared to using an array. 78 00:03:49,160 --> 00:03:49,760 All right. 79 00:03:49,790 --> 00:03:52,820 Now let's go ahead and see how we are going to implement this. 80 00:03:52,820 --> 00:03:55,820 Now again first we are going to have a node. 81 00:03:55,820 --> 00:03:57,140 Let's say this is our first node. 82 00:03:57,140 --> 00:04:00,620 So this is inserted into our queue or our singly linked list. 83 00:04:00,620 --> 00:04:03,050 And then we add the second node at the end. 84 00:04:03,050 --> 00:04:04,820 So let's say two is the second node. 85 00:04:04,820 --> 00:04:07,100 So this is going to be added at the end. 86 00:04:07,100 --> 00:04:09,950 Now let's add one more element to this singly linked list. 87 00:04:09,950 --> 00:04:11,810 Again it's added at the end. 88 00:04:11,840 --> 00:04:15,950 Now when we are removing from the beginning we will get back this node over here. 89 00:04:15,950 --> 00:04:21,320 And you can see that by removing from the beginning we are getting back what was first added in. 90 00:04:21,320 --> 00:04:27,050 So that's why adding at the end and removing from the beginning in the case of a linked list gives us 91 00:04:27,050 --> 00:04:31,100 a queue data structure because it follows the Fifo property. 92 00:04:31,100 --> 00:04:31,580 All right. 93 00:04:31,580 --> 00:04:36,410 And again it's it's it's operating both both of these are constant time operations. 94 00:04:36,410 --> 00:04:38,390 So we are getting an efficient queue. 95 00:04:38,390 --> 00:04:42,290 Now let's go ahead and see how we will be implementing this in code. 96 00:04:42,290 --> 00:04:48,500 Now this is going to be pretty much similar to how we wrote our instance methods for the singly linked 97 00:04:48,500 --> 00:04:49,910 list design question. 98 00:04:49,910 --> 00:04:52,400 So let's say this is our singly linked list. 99 00:04:52,400 --> 00:04:54,320 Now we need to add at the end. 100 00:04:54,320 --> 00:04:56,330 So let's say a value is given. 101 00:04:56,330 --> 00:04:59,420 So we make a node out of that with that particular value. 102 00:04:59,420 --> 00:05:00,290 So this node. 103 00:05:00,530 --> 00:05:04,400 Over here will be pointing to null and the value of this node will be passed to it. 104 00:05:04,400 --> 00:05:10,340 And then we will take the previous last node, and we will make it point to the new node which we just 105 00:05:10,340 --> 00:05:11,180 now created. 106 00:05:11,180 --> 00:05:14,330 And then we will reassign last from here to here. 107 00:05:14,330 --> 00:05:16,190 Previously this was the last node. 108 00:05:16,190 --> 00:05:19,760 And that is going to be reassigned to the node that we have now created. 109 00:05:20,780 --> 00:05:24,530 So this is how we will add at the end in the singly linked list. 110 00:05:24,530 --> 00:05:28,370 And to remove from the beginning all we need to do is first. 111 00:05:28,370 --> 00:05:29,660 Previously is over here. 112 00:05:29,660 --> 00:05:32,180 This is going to be shifted to the next node. 113 00:05:32,180 --> 00:05:34,520 So that is how we will remove from the beginning. 114 00:05:34,520 --> 00:05:38,030 And the node which is removed will just be returned. 115 00:05:38,030 --> 00:05:41,240 So this is how we will implement our queue with the linked list. 116 00:05:41,270 --> 00:05:46,940 Now again remember adding at the end in the case of a singly linked list is a constant time operation 117 00:05:46,940 --> 00:05:53,450 and constant space operation and removing from the beginning also with respect to complexity is constant 118 00:05:53,450 --> 00:05:55,310 time and constant space.