Queue with fixed maximum length

boundedqueue.py

#!/usr/bin/env python

# This bounded queue is implemented as a doubly-linked list with an additional size
# parameter. This enables O(1) time efficiency for the enqueue and dequeue
# operations, as these operations only operate on the first and last nodes.
# 
# This may not have optimal space efficiency because of the double pointers in
# each node, but it is a tradeoff for maximum time and throughput. The queue
# never examines nodes in the middle of the list, so it uses a minimal amount
# of memory throughput.

class BoundedQueue:
    size = 0
    maxSize = 0
    firstNode = None # end delimiter
    lastNode = None
    
    # constructor
    #
    # usage:
    # queue = BoundedQueue(maxSize)
    # 
    def __init__(self, maxSize):
        self.maxSize = maxSize
    
    # enqueue
    # 
    # usage:
    # queue.enqueue(num)
    # 
    # check that the size is within the maxSize
    # if it is, add a new node at the beginning of the list
    # otherwise, ignore the command
    #
    def enqueue(self, n):
        if self.size < self.maxSize:
            self.size += 1
            
            if self.firstNode is None:
                # empty list, so create a new node referencing end delimiters
                self.firstNode = DoublyLinkedNode(n, None, None)
                
                # first node and last node are the same for now
                self.lastNode = self.firstNode
            else:
                # non-empty list, so start by creating a node that references
                # the current first node
                newNode = DoublyLinkedNode(n, self.firstNode.prev, self.firstNode)
                
                # make the current first node point to the new first node
                self.firstNode.prev = newNode
                
                # make the first node our new node
                self.firstNode = newNode
    
    # dequeue
    # 
    # usage:
    # queue.dequeue()
    # 
    # if the queue is not empty, remove the last node from the list
    # otherwise, ignore the command
    # 
    def dequeue(self):
        if self.lastNode is not None:
            self.size -= 1
            
            # set the second-to-last node to be the last
            self.lastNode = self.lastNode.prev
            
            if self.lastNode is None:
                # list is empty, but firstNode still references a node
                self.firstNode = None
            else:
                # list is not empty, but lastNode has to link to None
                self.lastNode.next = None;
    
    # equalsList
    #
    # a comparison function for testing purposes. compares this queue to a list
    # 
    def equalsList(self, list):
        # check size first. guarantees that loop is best way to check
        #
        if self.size != len(list):
            return False
        else:
            # simultaneously loop over the values in the queue and in the list
            # to make sure they match
            #
            # start at last node because the oldest nodes get pushed to the end,
            # and this is a FIFO data structure
            
            node = self.lastNode
            index = 0
            
            while node is not None:
                if node.val != list[index]:
                    return False
                node = node.prev
                index += 1
            
            return True

class DoublyLinkedNode:
    def __init__(self, val, prev, next):
        self.val = val
        self.prev = prev
        self.next = next

tests.py

#!/usr/bin/env python

from boundedqueue import BoundedQueue

numTests = 0
numPassed = 0

def assertTrue(name, value):
    global numTests, numPassed
    
    print "Testing: %s..." % name,
    
    numTests += 1
    if value:
        print "PASS"
        numPassed += 1
    else:
        print "***FAIL***"
    print

def assertEqual(name, queue, list):
    assertTrue(name, queue.equalsList(list))

bq0 = BoundedQueue(0)
assertEqual("Empty queue is empty", bq0, [])
assertTrue("Empty queue size 0", bq0.size is 0)
assertTrue("Empty queue maxSize 0", bq0.maxSize is 0)

bq1 = BoundedQueue(5)
bq1.dequeue()
assertEqual("Dequeue of empty queue doesn't change state", bq1, [])

bq1.enqueue(1)
assertEqual("Enqueue a single element", bq1, [1])

bq1.dequeue()
assertEqual("Dequeue a single element", bq1, [])

bq2 = BoundedQueue(5)
bq2.enqueue(1)
bq2.enqueue(2)
bq2.enqueue(3)
bq2.enqueue(4)
bq2.enqueue(5)
bq2.enqueue(6)
assertEqual("Enqueue respects bounds of queue", bq2, [1, 2, 3, 4, 5])

bq2.dequeue()
assertEqual("Dequeue on multi-element queue", bq2, [2, 3, 4, 5])

bq2.enqueue(7)
bq2.enqueue(8)
assertEqual("Enqueue after dequeue", bq2, [2, 3, 4, 5, 7])

bq2.dequeue()
bq2.dequeue()
bq2.dequeue()
assertEqual("Dequeue on multi-element queue", bq2, [5, 7])

bq2.dequeue()
bq2.dequeue()
assertEqual("Dequeue", bq2, [])

print
print "Results: %d of %d tests passed" % (numPassed, numTests)