Day 365

[vaskoz]

Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

A quack is a data structure combining properties of both stacks and queues. It can be viewed as a list of elements written left to right such that three operations are possible:

• push(x): add a new item x to the left end of the list
• pop(): remove and return the item on the left end of the list
• pull(): remove the item on the right end of the list.
  Implement a quack using three stacks and O(1) additional memory, so that the amortized time for any push, pop, or pull operation is O(1).

[vaskoz]

NOTE: The solution provided by dailycodingproblem.com for the last day problem has a small bug in it. My solution doesn't contain that typo/bug.