1 00:00:00,500 --> 00:00:05,689 So in order for us to come up with a solution to this problem, we need to think about the right approach 2 00:00:05,689 --> 00:00:09,680 of implementing statutes in such a way that we can achieve a. 3 00:00:09,680 --> 00:00:16,430 Q And the trick here is the fact that the question says Stax, plural, but we still need to think about 4 00:00:16,430 --> 00:00:18,920 how many Stax do we need to implement in order for this to work? 5 00:00:18,920 --> 00:00:25,490 And also, what is the configuration of the Stax and their methods that allow us to achieve the same 6 00:00:25,490 --> 00:00:27,080 behavior as a Q? 7 00:00:27,260 --> 00:00:33,020 So let's first think about the behavioral differences and similarities between Q's and Stax so that 8 00:00:33,020 --> 00:00:35,300 we can glean the correct insights. 9 00:00:35,600 --> 00:00:37,850 Let's talk about inserting values. 10 00:00:37,850 --> 00:00:46,310 If we were to insert the values one, two, three, four and five into a Q or into a stack, the order 11 00:00:46,310 --> 00:00:47,630 is the exact same. 12 00:00:47,630 --> 00:00:53,150 The Q would get one, two, three, four, five, and the stack would get one, two, three, four, 13 00:00:53,150 --> 00:00:53,780 five. 14 00:00:54,050 --> 00:00:58,490 So here we see insertion order does not change between a Q and a stack. 15 00:00:58,490 --> 00:00:59,600 That's the first thing. 16 00:01:00,020 --> 00:01:02,870 The next thing we've got to think about then is popping. 17 00:01:02,870 --> 00:01:04,610 What about removing values? 18 00:01:04,730 --> 00:01:08,390 When we remove a value from a Q, we remove it from the beginning. 19 00:01:08,390 --> 00:01:12,530 So here we would, let's say, call pop on our Q we'd pull out the one. 20 00:01:13,870 --> 00:01:17,530 If we were to call Pop again, we would pull out the two. 21 00:01:19,910 --> 00:01:25,220 Similarly, if we were to call the pop methods on our stack, we would first get the five. 22 00:01:26,390 --> 00:01:28,280 And then we would get the four. 23 00:01:29,780 --> 00:01:35,390 So here we see the differences between the stack and the queue is the order of the elements that get 24 00:01:35,390 --> 00:01:36,080 removed. 25 00:01:36,860 --> 00:01:43,100 What we notice, though, is that if we wanted the elements one and two out of the stack, we would 26 00:01:43,100 --> 00:01:45,440 need the values of the very beginning. 27 00:01:45,440 --> 00:01:51,710 And essentially the only way a stack that could achieve the same kind of value extraction from a Q if 28 00:01:51,710 --> 00:01:58,970 we're looking at the one and the two is such that if we had a different stack with the values in reverse 29 00:01:58,970 --> 00:02:06,890 order five, four, three, two, one here what we notice is that this when you call pop on a stack 30 00:02:06,890 --> 00:02:08,509 with this shape. 31 00:02:09,740 --> 00:02:16,760 You will end up retrieving the 1/1 and then you would end up retrieving the two after. 32 00:02:17,710 --> 00:02:20,760 Because we're removing from the end of this stack. 33 00:02:20,770 --> 00:02:26,980 So that's really the insight here, is that the only way we can achieve the same values from a Q as 34 00:02:26,980 --> 00:02:33,700 we would from a stack is if the values were in the reverse order that they were in the Q. 35 00:02:34,550 --> 00:02:36,530 That is one big insight. 36 00:02:37,310 --> 00:02:45,260 So what is the way that we need to do to get this stack that had the values one, two, three, four, 37 00:02:45,260 --> 00:02:52,100 five into this stack that had the values, five, four, three, two and one. 38 00:02:52,130 --> 00:02:54,560 Remember, we have to use stacks. 39 00:02:54,560 --> 00:03:00,350 So here I'm just going to say stack two is the stack that we are trying to achieve in order, at the 40 00:03:00,350 --> 00:03:03,680 very least, for us to pop values in the same way as the queue. 41 00:03:04,130 --> 00:03:07,370 How do we get this stack to become this stack? 42 00:03:08,140 --> 00:03:12,670 Well, let's imagine that we had some second stack. 43 00:03:12,670 --> 00:03:18,130 So here we're running two stacks and this stack two is the stack that we want to achieve. 44 00:03:18,160 --> 00:03:20,140 This here is also a stack. 45 00:03:21,090 --> 00:03:26,880 As we pop values from this first stack here, what is the order that they come out in? 46 00:03:27,240 --> 00:03:33,750 They come out as five, four, three, two and one because we're popping from the end. 47 00:03:33,750 --> 00:03:38,100 First the five, then the four, then the three, then the two, then the one. 48 00:03:38,340 --> 00:03:46,230 And here what we notice about this order is that it is the same order that we want elements to be inserted 49 00:03:46,230 --> 00:03:53,400 into Stack two, because if we pop the five and then insert the five, well here in the second stack, 50 00:03:53,790 --> 00:03:56,220 this five is now the first element. 51 00:03:56,220 --> 00:03:59,340 Then we pop the four and we insert the four. 52 00:03:59,580 --> 00:04:05,220 We see that this is achieving the order that we were looking for right here. 53 00:04:05,220 --> 00:04:06,090 Similarly, what? 54 00:04:06,090 --> 00:04:09,390 The three, the two and the one finally. 55 00:04:09,970 --> 00:04:17,769 So what we notice now is that this stack is in the correct shape that we need it to be in order for 56 00:04:17,769 --> 00:04:25,270 us to pop elements from this stack so that it achieves the same order of elements popped from our queue. 57 00:04:25,450 --> 00:04:30,610 So immediately here we know that we should probably average two stacks. 58 00:04:30,910 --> 00:04:32,530 But is this enough? 59 00:04:32,650 --> 00:04:39,820 What happens if we were to push values into our queue, and how does that reflect in these two stacks 60 00:04:39,820 --> 00:04:40,600 that we have? 61 00:04:40,690 --> 00:04:45,700 So here I'm just going to make this more clear because we've achieved what we wanted with this shape 62 00:04:45,700 --> 00:04:46,570 example. 63 00:04:46,720 --> 00:04:52,600 And I want to just explicitly call this second stack stack too, just so that we're aware that we need 64 00:04:52,600 --> 00:04:54,070 to be running two stacks. 65 00:04:54,980 --> 00:05:01,940 So once we pop these values from Stack one into Stack two, we've removed these values as well. 66 00:05:02,270 --> 00:05:07,880 So in order for us to achieve that shape, we see that we have an empty stack one and stack two is filled 67 00:05:07,880 --> 00:05:11,840 with the values that we popped out of Stack one and then inserted into Stack two. 68 00:05:12,830 --> 00:05:19,460 But let's say that after we popped two values from Stack two so that it matches the same as the Q that 69 00:05:19,460 --> 00:05:19,970 we have. 70 00:05:19,970 --> 00:05:23,240 So we popped out first the one, then we popped out the two. 71 00:05:23,240 --> 00:05:28,610 So here we notice that these two are now the same and these elements represent the same elements in 72 00:05:28,610 --> 00:05:31,280 the respective data structures. 73 00:05:31,700 --> 00:05:38,180 Let's say we were to insert values six and seven now into our Q and then into our stack. 74 00:05:38,510 --> 00:05:41,990 So if we inserted six and then we insert it seven. 75 00:05:42,830 --> 00:05:45,860 What happens when we call pop three more times? 76 00:05:46,340 --> 00:05:48,530 We are popping three, four or five. 77 00:05:49,540 --> 00:05:54,730 Because that's the order in which they appear inside of our queue. 78 00:05:55,610 --> 00:06:01,760 But here, let's think about what we need to do with our two stacks that we have achieved here. 79 00:06:01,790 --> 00:06:08,480 We want to try and manipulate this so that it works with the same order of operations as the queue. 80 00:06:09,230 --> 00:06:13,670 We have six and seven to insert into either of these two stacks. 81 00:06:14,090 --> 00:06:19,390 If we insert it six and seven into stack two, well, they would go in the same order. 82 00:06:19,400 --> 00:06:26,090 We figured that out during our first insight when we realized that the order of insertion is the same 83 00:06:26,090 --> 00:06:27,410 between a Q and a stack. 84 00:06:27,680 --> 00:06:32,210 So we can only insert it into either stack two or stack one and inserting it into stack two. 85 00:06:32,240 --> 00:06:33,140 What happens? 86 00:06:33,350 --> 00:06:39,410 Well, now, when we want to pop values three, four or five, we now can access these values because 87 00:06:39,410 --> 00:06:41,740 we have to pop from the end of stack 2/1. 88 00:06:41,750 --> 00:06:47,960 So what we see is that we would end up getting seven, six and then three, which is not correct. 89 00:06:48,860 --> 00:06:50,550 So let's try the other thing. 90 00:06:50,570 --> 00:06:54,920 What if we were to insert six and seven into stack one? 91 00:06:55,610 --> 00:07:01,190 Well here now whenever we were to pop from stack two, three, four, five, we would end up getting 92 00:07:01,190 --> 00:07:08,180 the values three, four or five from stack two, which is the exact same order that we want it to achieve. 93 00:07:08,880 --> 00:07:10,020 With our. 94 00:07:10,020 --> 00:07:17,970 Q So once we've popped these values out, what we'll notice is that we don't have any values in Stack 95 00:07:17,970 --> 00:07:18,720 two left. 96 00:07:18,720 --> 00:07:24,750 So let's say we were to keep popping values from both our Q and our two stack representation of our 97 00:07:24,750 --> 00:07:25,200 Q. 98 00:07:25,830 --> 00:07:28,380 Let's say we pop six and we pop seven. 99 00:07:30,160 --> 00:07:34,990 Well, at this point, we can't pop six and seven from stack two because we have no values in Stack 100 00:07:34,990 --> 00:07:35,490 two. 101 00:07:35,500 --> 00:07:38,530 And with Stack one, we see we have our original problem. 102 00:07:38,530 --> 00:07:42,910 It's not in the order that we want, but we already know what to do when we need to achieve the reverse 103 00:07:42,910 --> 00:07:43,360 order. 104 00:07:43,360 --> 00:07:48,220 We push these values by popping them out and then pushing them into stack two. 105 00:07:48,310 --> 00:07:54,070 So by popping it out first we pop out the seven and we insert it into stack two, then we pop the six 106 00:07:54,490 --> 00:07:59,560 and we put it into Stack two, and once again we now have achieved the order that we want. 107 00:07:59,560 --> 00:08:04,330 So now when I pop out from our stack two, we'll get six. 108 00:08:04,330 --> 00:08:07,060 And then when I pop again, we'll get seven. 109 00:08:08,000 --> 00:08:15,410 So here we see that we've achieved this on Q and DK method from our Q using two stacks. 110 00:08:16,350 --> 00:08:21,660 The big thing that we also want to infer is that when we think about it, as long as there are values 111 00:08:21,660 --> 00:08:30,780 inside of Stack and we call the pop or the DX Q method on this Q represented by two stacks, we want 112 00:08:30,780 --> 00:08:35,760 to pop values from stack two because it will be the order that we want it in. 113 00:08:35,970 --> 00:08:42,360 It's only when Stack two is empty that we want to do that whole reversal process of popping values from 114 00:08:42,360 --> 00:08:47,820 Stack one and then pushing them into Stack two before we continue popping those values off of Stack 115 00:08:47,820 --> 00:08:49,830 two to achieve that order. 116 00:08:49,860 --> 00:08:56,610 This makes sense because while we push and pull values out of our queue, we want to be able to achieve 117 00:08:56,610 --> 00:08:59,460 that same order with our two stack representation. 118 00:08:59,460 --> 00:09:00,850 So that's really the key. 119 00:09:00,870 --> 00:09:03,390 If you push values, you push them into stack one. 120 00:09:03,390 --> 00:09:08,520 If you pop values, you pop them out of stack two until this is empty, then you reverse stack one into 121 00:09:08,520 --> 00:09:11,250 stack two and you continue popping values out of stack two. 122 00:09:12,340 --> 00:09:22,270 The two remaining methods is empty and its peak peak is pretty much the exact same as DX Q or the pop 123 00:09:22,270 --> 00:09:22,870 method. 124 00:09:22,900 --> 00:09:27,550 The only difference is that instead of actually removing the value from stack two, we just want to 125 00:09:27,550 --> 00:09:31,690 return a reference to the last value that is inside of Stack two. 126 00:09:32,050 --> 00:09:37,330 So I will leave you to figure out the implementation of that as well as empty, because they're actually 127 00:09:37,330 --> 00:09:38,110 quite simple. 128 00:09:38,110 --> 00:09:43,360 And I want you to think about it a little bit so that you really understand how these two stacks work 129 00:09:43,420 --> 00:09:46,000 inside of this implementation of a queue. 130 00:09:46,790 --> 00:09:51,580 And if you're familiar with implementing classes in your native language as well as in JavaScript, 131 00:09:51,590 --> 00:09:53,540 definitely try and code it out yourself. 132 00:09:53,540 --> 00:09:59,570 If you're unfamiliar with classes, I'm going to link a resource in your resources folder that will 133 00:09:59,570 --> 00:10:06,140 teach you all about classes and JavaScript so that you can still take a crack at implementing it yourself. 134 00:10:06,900 --> 00:10:12,090 After that, I'm going to show you in the next video how to do it yourself, but definitely take a strike 135 00:10:12,090 --> 00:10:18,210 at trying to solve these four methods inside of our Q with stacks class implementation yourself.