An easy First-In-First-Out queue class based on Python's List data structure.
1 2 3 4 5 6 7 8 9 10 11 12 13
class Queue: """A sample implementation of a First-In-First-Out data structure.""" def __init__(self): self.in_stack =  self.out_stack =  def push(self, obj): self.in_stack.append(obj) def pop(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop()
We had a discussion on Python-Tutor a while back about implementing a first-in-first out data structure in Python. For reference, here's links to the discussion:
http://aspn.activestate.com/ASPN/Mail/Message/python-Tutor/1677154 http://aspn.activestate.com/ASPN/Mail/Message/python-Tutor/1677909 http://aspn.activestate.com/ASPN/Mail/Message/python-Tutor/1679139 http://aspn.activestate.com/ASPN/Mail/Message/python-Tutor/1679248
The naive approach to make a queue is to use a single list, and use append() and pop(0) to grow or shrink the queue. The problem with this approach is that it performs poorly as the queue grows large, since pop(0) forces the remaining elements of a list to shift.
The approach above is based on the idea that two stacks can efficiently implement a queue. Knuth makes a brief mention of it in The Art Of Computer Programming (Exercise 14, Section 2.2.1.).