In a mess canteen, clean plates are piled one on top of another. You always take the plate that was put on last. This is a stack.
But the canteen only owns queues. A queue is a line where you add at the back and take from the front. Use queues to build the stack.
Write a class MyStack with these methods:
push(x): put the number x on top of the stack.pop(): take off the top number, and return it.top(): return the top number, without taking it off.empty(): return true if the stack has no numbers, otherwise return false.
Use only the basic actions of a queue: add at the back, look at or take off the front number, ask the size, and ask if it is empty.
Examples
Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty", "pop", "empty"]
[[], [3], [9], [], [], [], [], []]
Output
[null, null, null, 9, 9, false, 3, true]
Explanation
push(3) // stack: 3
push(9) // stack: 3, 9 (9 is on top)
top() // returns 9
pop() // returns 9, stack: 3
empty() // returns false
pop() // returns 3
empty() // returns true
Example 2:
Input
["MyStack", "push", "push", "pop", "push", "top", "pop", "pop", "empty"]
[[], [4], [6], [], [8], [], [], [], []]
Output
[null, null, null, 6, null, 8, 8, 4, true]
Explanation
After push(4) and push(6), pop() returns 6 because it was put on last.
push(8) goes on top, so top() returns 8, and the next pop() returns 8.
The last pop() returns 4. Then the stack is empty, so empty() returns true.