Skip to content

Instantly share code, notes, and snippets.

@wylieconlon
Created February 11, 2012 05:32
Show Gist options
  • Save wylieconlon/1796725 to your computer and use it in GitHub Desktop.
Save wylieconlon/1796725 to your computer and use it in GitHub Desktop.
Queue with fixed maximum length
#!/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
#!/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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment