This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Complexity:
Complexity:
%%writefile queue_list.py
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
class Queue(object):
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, data):
node = Node(data)
# Empty list
if self.head is None and self.tail is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def dequeue(self):
# Empty list
if self.head is None and self.tail is None:
return None
data = self.head.data
# Remove only element from a one element list
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = self.head.next
return data
Overwriting queue_list.py
%run queue_list.py
%%writefile test_queue_list.py
import unittest
class TestQueue(unittest.TestCase):
# TODO: It would be better if we had unit tests for each
# method in addition to the following end-to-end test
def test_end_to_end(self):
print('Test: Dequeue an empty queue')
queue = Queue()
self.assertEqual(queue.dequeue(), None)
print('Test: Enqueue to an empty queue')
queue.enqueue(1)
print('Test: Dequeue a queue with one element')
self.assertEqual(queue.dequeue(), 1)
print('Test: Enqueue to a non-empty queue')
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
print('Test: Dequeue a queue with more than one element')
self.assertEqual(queue.dequeue(), 2)
self.assertEqual(queue.dequeue(), 3)
self.assertEqual(queue.dequeue(), 4)
print('Success: test_end_to_end')
def main():
test = TestQueue()
test.test_end_to_end()
if __name__ == '__main__':
main()
Overwriting test_queue_list.py
%run -i test_queue_list.py
Test: Dequeue an empty queue Test: Enqueue to an empty queue Test: Dequeue a queue with one element Test: Enqueue to a non-empty queue Test: Dequeue a queue with more than one element Success: test_end_to_end
Source: https://docs.python.org/2/tutorial/datastructures.html#using-lists-as-queues
It is possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one). To implement a queue, use collections.deque which was designed to have fast appends and pops from both ends. For example: >>> >>> from collections import deque >>> queue = deque(["Eric", "John", "Michael"]) >>> queue.append("Terry") # Terry arrives >>> queue.append("Graham") # Graham arrives >>> queue.popleft() # The first to arrive now leaves 'Eric' >>> queue.popleft() # The second to arrive now leaves 'John' >>> queue # Remaining queue in order of arrival deque(['Michael', 'Terry', 'Graham'])