This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• If there is one item in the list, do you expect the head and tail pointers to both point to it?
• Yes
• If there are no items on the list, do you expect the head and tail pointers to be None?
• Yes
• If you dequeue on an empty queue, does that return None?
• Yes
• Can we assume this fits memory?
• Yes

## Test Cases¶

### Enqueue¶

• Enqueue to an empty queue
• Enqueue to a non-empty queue

### Dequeue¶

• Dequeue an empty queue -> None
• Dequeue a queue with one element
• Dequeue a queue with more than one element

## Algorithm¶

### Enqueue¶

• If the list is empty, set head and tail to node
• Else, set tail to node

Complexity:

• Time: O(1)
• Space: O(1)

### Dequeue¶

• If the list is empty, return None
• If the list has one node
• Save the head node's value
• Set head and tail to None
• Return the saved value
• Else
• Save the head node's value
• Set head to its next node
• Return the saved value

Complexity:

• Time: O(1)
• Space: O(1)

## Code¶

In [1]:
%%writefile queue_list.py
class Node(object):

def __init__(self, data):
self.data = data
self.next = None

class Queue(object):

def __init__(self):
self.tail = None

def enqueue(self, data):
node = Node(data)
# Empty list
if self.head is None and self.tail is None:
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
# Remove only element from a one element list
self.tail = None
else:
return data

Overwriting queue_list.py

In [2]:
%run queue_list.py


## Unit Test¶

In [3]:
%%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

In [4]:
%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


## Pythonic-Code¶

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'])