Implement a queue using two stacks

The space cost is O(n). The runtime cost of enqueue is O(1); the runtime cost of
dequeue is O(n). Using the "accounting method", the cost of an item in the
system is O(1). Here's why:

+------------+----------------------------+------+
| enqueue    | push onto lhs              | O(1) |
+------------+----------------------------+------+
| lhs -> rhs | pop off lhs; push onto rhs | O(1) |
+------------+----------------------------+------+
| dequeue    | pop off rhs                | O(1) |
+------------+----------------------------+------+

1 files changed, 17 insertions, 0 deletions

diff --git a/scratch/facebook/interview-cake/queue-two-stacks.py b/scratch/facebook/interview-cake/queue-two-stacks.py
new file mode 100644
index 000000000000..bfa465f98d7f
--- /dev/null
+++ b/scratch/facebook/interview-cake/queue-two-stacks.py
@@ -0,0 +1,17 @@
+class Queue(object):
+    def __init__(self):
+        self.lhs = []
+        self.rhs = []
+
+    def enqueue(self, x):
+        self.lhs.append(x)
+
+    def dequeue(self):
+        if self.rhs:
+            return self.rhs.pop()
+        while self.lhs:
+            self.rhs.append(self.lhs.pop())
+        if self.rhs:
+            return self.rhs.pop()
+        else:
+            raise Exception("Attempting to remove an item from an empty queue")