Hi everyone, let's do this question.
Implement a first in first out queue using only two stacks.
The implemented queue should support all the functions of a normal queue push, peak, pop and empty.
So we have to write a Fifo data structure which is a queue using only two stacks.
And over here the methods that should be supported by the My Queue class are mentioned, which is push,
pop, peak and empty.
Now push while pushes element val to the back of the queue.
Pop removes the element from the front of the queue and returns it.
So that's because it's Fifo, right?
It should return the element which was first inserted.
Now peak returns the element at the front of the queue, so this is not going to remove it, but it
will just return the element and empty returns true if the queue is empty and false otherwise.
So this is the question.
Now over here we have a few notes.
So it says you must only use standard operations of a stack, which means only push to top peak pop
from top size and is empty.
Operations are valid, so we can only use LIFO data structure which is stack for this.
All right.
And then it says depending on your language the stack may not be supported natively.
You may simulate a stack using a list or a queue double ended queue as long as you only use the stack
standard operations.
Over here we're going to use an array implementation for the stack, and then you have a follow up note
over here.
Implement the queue such that each operation is amortized over one time complexity.
In other words, performing N operations will take over all O of N time even if one of those operations
may take longer.
So that's the question.
So in the notes it's mentioned, we should use only the operations which are allowed for a stack which
is lafoe.
So the stack is a leaf or last in first out data structure.
And then it says over here that the operations should be amortized O of one or constant time complexity.
And again amortized O of one time complexity just means that the average time complexity has to be O
of one.
Or in other words, it's mentioned over here performing N operations will take over all O of n time,
even if one of these operations may take longer.
So we're doing N operations and that's taking O of N time.
All right.
So it's not one operation it's n operations.
So this O of n can be written as n into o of one.
So that's why we can say that on an average, one operation is going to take O of one time.
So among the N operations, some operation may take more time, but on average one operation is going
to take O of one time.
So that's what is mentioned over here.
All right.
So we have understood the question.
So we need to implement a Fifo data structure which is a queue using only two stacks.
And then these are the instance methods that we have to write for the MC class which is push pop, peek
and empty.
In the next video let's try to discuss how we can implement this.