At a chai stall, customers stand in a line. The first person to arrive is served first. This is a queue.
But the stall only owns stacks. A stack is a pile where you can touch only the top. Use stacks to build the queue.
Write a class MyQueue with these methods:
push(x): the customer with number x joins the back of the line.pop(): serve the customer at the front, and return that number.peek(): return the number at the front, without serving that customer.empty(): return true if nobody is in the line, otherwise return false.
Use only the basic actions of a stack: put a number on top, look at or take off the top number, ask the size, and ask if it is empty.
Examples
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty", "pop", "empty"]
[[], [8], [1], [], [], [], [], []]
Output
[null, null, null, 8, 8, false, 1, true]
Explanation
push(8) // line: 8
push(1) // line: 8, 1 (8 is at the front)
peek() // returns 8
pop() // returns 8, line: 1
empty() // returns false
pop() // returns 1
empty() // returns true
Example 2:
Input
["MyQueue", "push", "push", "pop", "push", "peek", "pop", "pop", "empty"]
[[], [2], [5], [], [7], [], [], [], []]
Output
[null, null, null, 2, null, 5, 5, 7, true]
Explanation
After push(2) and push(5), pop() returns 2 because it came first.
push(7) joins the back. The line is now 5, 7.
peek() returns 5. The next pop() returns 5, and the one after returns 7.
The line is empty, so empty() returns true.