This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

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



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.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









    



Overwriting queue_list.py



In [2]:

    
%run queue_list.py

Unit Test



In [3]:

    
%%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()









    



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

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