Welcome, guest | Sign In | My Account | Store | Cart

Quick and easy FIFO queue class (Python recipe) by Danny Yoo
ActiveState Code (http://code.activestate.com/recipes/210459/)

An easy First-In-First-Out queue class based on Python's List data structure.

Python, 13 lines
Download
 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.).

Tags: algorithms

2 comments

Josiah Carlson 20 years, 8 months ago  # | flag

A couple variants for better speed. The below modification to yours keeps the pop and append calls to a minimum, increasing speed slightly.

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:
            self.in_stack.reverse()
            self.out_stack = self.in_stack
            self.in_stack = []
        return self.out_stack.pop()

If one isn't worried about using too much memory, the below is another variant that reduces the list reconstruction significantly, and still only uses one list. Even faster than the above, though as you can see, nothing is actually removed, it is merely 'hidden'.

class UndyingQueue:
    def __init__(self, lst=[]):
        self.q = []
        self.out = 0
    def push(self, seq):
        self.q.append(seq)
    def pop(self):
        k = self.q[self.out]
        self.out += 1
        return k
Jeremy Fincher 20 years, 3 months ago  # | flag

There's also significant discussion at http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436

Created by Danny Yoo on Tue, 15 Jul 2003 (PSF)
◄ Python recipes (4591) ►
◄ Danny Yoo's recipes (9) ►

Required Modules

  • (none specified)

Other Information and Tasks