1
00:00:00,630 --> 00:00:03,150
Hi everyone, let's do this question.

2
00:00:03,150 --> 00:00:06,990
Implement a first in first out queue using only two stacks.

3
00:00:07,200 --> 00:00:12,750
The implemented queue should support all the functions of a normal queue push, peak, pop and empty.

4
00:00:12,750 --> 00:00:17,910
So we have to write a Fifo data structure which is a queue using only two stacks.

5
00:00:17,910 --> 00:00:23,700
And over here the methods that should be supported by the My Queue class are mentioned, which is push,

6
00:00:23,700 --> 00:00:25,140
pop, peak and empty.

7
00:00:25,170 --> 00:00:28,410
Now push while pushes element val to the back of the queue.

8
00:00:28,410 --> 00:00:32,160
Pop removes the element from the front of the queue and returns it.

9
00:00:32,160 --> 00:00:33,690
So that's because it's Fifo, right?

10
00:00:33,690 --> 00:00:36,180
It should return the element which was first inserted.

11
00:00:36,180 --> 00:00:41,280
Now peak returns the element at the front of the queue, so this is not going to remove it, but it

12
00:00:41,280 --> 00:00:47,520
will just return the element and empty returns true if the queue is empty and false otherwise.

13
00:00:47,520 --> 00:00:48,750
So this is the question.

14
00:00:48,750 --> 00:00:50,370
Now over here we have a few notes.

15
00:00:50,370 --> 00:00:57,210
So it says you must only use standard operations of a stack, which means only push to top peak pop

16
00:00:57,210 --> 00:00:59,340
from top size and is empty.

17
00:00:59,340 --> 00:01:03,870
Operations are valid, so we can only use LIFO data structure which is stack for this.

18
00:01:03,870 --> 00:01:04,470
All right.

19
00:01:04,470 --> 00:01:08,370
And then it says depending on your language the stack may not be supported natively.

20
00:01:08,370 --> 00:01:14,490
You may simulate a stack using a list or a queue double ended queue as long as you only use the stack

21
00:01:14,490 --> 00:01:15,630
standard operations.

22
00:01:15,630 --> 00:01:21,180
Over here we're going to use an array implementation for the stack, and then you have a follow up note

23
00:01:21,180 --> 00:01:21,780
over here.

24
00:01:21,780 --> 00:01:27,240
Implement the queue such that each operation is amortized over one time complexity.

25
00:01:27,240 --> 00:01:34,140
In other words, performing N operations will take over all O of N time even if one of those operations

26
00:01:34,140 --> 00:01:35,550
may take longer.

27
00:01:35,550 --> 00:01:36,360
So that's the question.

28
00:01:36,360 --> 00:01:40,890
So in the notes it's mentioned, we should use only the operations which are allowed for a stack which

29
00:01:40,890 --> 00:01:41,610
is lafoe.

30
00:01:41,610 --> 00:01:45,480
So the stack is a leaf or last in first out data structure.

31
00:01:45,480 --> 00:01:51,690
And then it says over here that the operations should be amortized O of one or constant time complexity.

32
00:01:51,690 --> 00:01:57,900
And again amortized O of one time complexity just means that the average time complexity has to be O

33
00:01:57,900 --> 00:01:58,380
of one.

34
00:01:58,380 --> 00:02:04,230
Or in other words, it's mentioned over here performing N operations will take over all O of n time,

35
00:02:04,230 --> 00:02:06,990
even if one of these operations may take longer.

36
00:02:06,990 --> 00:02:11,100
So we're doing N operations and that's taking O of N time.

37
00:02:11,100 --> 00:02:11,370
All right.

38
00:02:11,370 --> 00:02:13,560
So it's not one operation it's n operations.

39
00:02:13,560 --> 00:02:16,920
So this O of n can be written as n into o of one.

40
00:02:17,650 --> 00:02:22,480
So that's why we can say that on an average, one operation is going to take O of one time.

41
00:02:22,480 --> 00:02:28,750
So among the N operations, some operation may take more time, but on average one operation is going

42
00:02:28,750 --> 00:02:30,130
to take O of one time.

43
00:02:30,130 --> 00:02:31,660
So that's what is mentioned over here.

44
00:02:31,660 --> 00:02:32,110
All right.

45
00:02:32,110 --> 00:02:33,400
So we have understood the question.

46
00:02:33,400 --> 00:02:38,530
So we need to implement a Fifo data structure which is a queue using only two stacks.

47
00:02:38,530 --> 00:02:44,080
And then these are the instance methods that we have to write for the MC class which is push pop, peek

48
00:02:44,080 --> 00:02:44,770
and empty.

49
00:02:44,800 --> 00:02:48,940
In the next video let's try to discuss how we can implement this.