%%writefile queue_list.py
class Node(object):

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


class Queue(object):

    def __init__(self):
        self.first = None
        self.last = None

    def enqueue(self, data):
        node = Node(data)
        if self.first is None and self.last is None:
            self.first = node
            self.last = node
        else:
            self.last.next = node
            self.last = node

    def dequeue(self):
        # Empty list
        if self.first is None and self.last is None:
            return None

        # Remove only element from a one element list
        elif self.first == self.last:
            data = self.first.data
            self.first = None
            self.last = None
            return data
        else:
            data = self.first.data
            self.first = self.first.next
            return data

%run queue_list.py

"""
Explanation: <small><i>This notebook was prepared by Donne Martin. Source and license info is on GitHub.</i></small>
Solution Notebook
Problem: Implement a queue with enqueue and dequeue methods using a linked list.

Constraints
Test Cases
Algorithm
Code
Unit Test
Pythonic-Code

Constraints

If there is one item in the list, do you expect the first and last pointers to both point to it?
Yes


If there are no items on the list, do you expect the first and last pointers to be None?
Yes


If you dequeue on an empty queue, does that return None?
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 first and last to node
Else, set last 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 first node's value
Set first and last to None
Return the saved value


Else
Save the first node's value
Set first to its next node
Return the saved value



Complexity:
* Time: O(1)
* Space: O(1)
Code
End of explanation
"""


%%writefile test_queue_list.py
from nose.tools import assert_equal


class TestQueue(object):

    # 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()
        assert_equal(queue.dequeue(), None)

        print('Test: Enqueue to an empty queue')
        queue.enqueue(1)

        print('Test: Dequeue a queue with one element')
        assert_equal(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')
        assert_equal(queue.dequeue(), 2)
        assert_equal(queue.dequeue(), 3)
        assert_equal(queue.dequeue(), 4)

        print('Success: test_end_to_end')


def main():
    test = TestQueue()
    test.test_end_to_end()


if __name__ == '__main__':
    main()

%run -i test_queue_list.py

"""
Explanation: Unit Test
End of explanation
"""


