Week 12

This week we learned about the big-O notation, which I have already learned in another course CSC165 in last semester. This is the big-O notation:

Big-O notation was not the only knowledge we`ve learned. A new Queue method should be the most important one.

# implement Queue using linked list node
from node_sol import LLNode


class Queue:
    ''' Represent a FIFO queue.
    '''

    def __init__(self):
        ''' (Queue) -> NoneType

        Create and initialize new queue self.
        '''
        self._front = self._back = None

    def enqueue(self, o):
        ''' (Queue, object) -> NoneType

        Add o at the back of this queue.
        '''
        new_node = LLNode(o)
        if self._back:
            self._back.nxt = new_node
            self._back = new_node
        else:
            self._back = self._front = new_node            

    def dequeue(self):
        ''' (Queue) -> object

        Remove and return front object from self.

        >>> q = Queue()
        >>> q.enqueue(3)
        >>> q.enqueue(5)
        >>> q.dequeue()
        3
        >>> q.enqueue(7)
        >>> q.dequeue()
        5
        '''
        new_value = self._front.value
        self._front = self._front.nxt
        return new_value

    def is_empty(self):
        ''' (Queue) -> bool

        Return True queue self is empty, False otherwise.

        >>> q = Queue()
        >>> q.enqueue(5)
        >>> q.is_empty()
        False
        >>> q.dequeue()
        5
        >>> q.is_empty()
        True
        '''
        return self._front == None


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    q = Queue()
    for num in [1000, 10000, 100000, 1000000]:
        q = Queue()
        for i in range(num):
            q.enqueue(i)
        import time
        start = time.time()
        for n in range(1000):
            q.enqueue(n)
        for n in range(1000):
            q.dequeue()
        print('Enqueue and dequeue 1000 items')
        print('starting with {} items in {} seconds.'.format(
            num, time.time() - start))

Finally we approach the end of the term. Final exam is incoming, I am a little bit afraid about it. Just keep calm and carry on, wish I can get a good mark on it.