From 60d7ea5b91c8f6bc8005af82be623fc0a3e0144d Mon Sep 17 00:00:00 2001 From: William Carroll Date: Sat, 21 Nov 2020 16:15:43 +0000 Subject: 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) | +------------+----------------------------+------+ --- scratch/facebook/interview-cake/queue-two-stacks.py | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) create mode 100644 scratch/facebook/interview-cake/queue-two-stacks.py 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") -- cgit 1.4.1