Created
February 26, 2014 21:09
-
-
Save kylestev/9238617 to your computer and use it in GitHub Desktop.
queue derived from two stacks
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Stack(object): | |
def __init__(self): | |
self.arr = [] | |
def __len__(self): | |
return len(self.arr) | |
def push(self, obj): | |
self.arr.append(obj) | |
def pop(self): | |
if len(self.arr) == 0: | |
raise Exception('Cannot pop when there are no elements!') | |
v = self.arr[-1] | |
del self.arr[-1] | |
return v | |
class Queue(object): | |
def __init__(self): | |
self.stacks = [Stack(), Stack()] | |
def enqueue(self, obj): | |
self.stacks[0].push(obj) | |
def dequeue(self): | |
if len(self.stacks[0]) == 0: | |
raise Exception('Nothing left to dequeue!') | |
# swap stack 1 to stack 2 except last element | |
for _ in xrange(len(self.stacks[0]) - 1): | |
self.stacks[1].push(self.stacks[0].pop()) | |
# pop from stack 2 => val | |
val = self.stacks[0].pop() | |
# swap back to stack 1 | |
for _ in range(len(self.stacks[1])): | |
self.stacks[0].push(self.stacks[1].pop()) | |
# ret val | |
return val | |
def main(): | |
q = Queue() | |
for i in xrange(1, 3): | |
q.enqueue(i) | |
print q.dequeue() | |
q.enqueue(5) | |
print q.dequeue() | |
print q.dequeue() | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment