CSC148 Stuff by Cem Yildirim: 2014-01-26

As requested, here is my implementation of the Queue class with Linked Lists in Python. Although Python is quite a high level language to utilize a data type as simple as a Linked Lists, it still greatly improves the performance of a Queue class which uses lists. I used timequeue.py given in lab 2 to benchmark and compare the both implementations and here are the results:

-------Linked List Queue--------------------------------
Running time on 10000 items: 0.07587790489196777
Running time on 20000 items: 0.06835103034973145
Running time on 30000 items: 0.07256507873535156
Running time on 40000 items: 0.07469511032104492
Running time on 50000 items: 0.07767081260681152
Running time on 60000 items: 0.09958291053771973
Running time on 70000 items: 0.1073610782623291
Running time on 80000 items: 0.11011409759521484
Running time on 90000 items: 0.07159709930419922
Running time on 100000 items: 0.11853194236755371
----------------- List Queue--------------------------------
Running time on 10000 items: 0.3262810707092285
Running time on 20000 items: 0.6386370658874512
Running time on 30000 items: 0.948969841003418
Running time on 40000 items: 1.2549891471862793
Running time on 50000 items: 1.5696308612823486
Running time on 60000 items: 1.8530290126800537
Running time on 70000 items: 4.520461082458496
Running time on 80000 items: 5.268892049789429
Running time on 90000 items: 5.846363067626953
Running time on 100000 items: 6.589374780654907

Here is my code for the two cases:

Linked List Queue:

class Node:

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

    def __str__(self):
        return str(self.data)


class Queue:

    def is_empty(self):
        if self.head and not self.curr:
            return False
        elif not self.curr:
            return True
        elif self.curr.next:
            return False
        else:
            return True

    def __init__(self):
        self.head = None
        self.curr = None
        self.tail = None

    def __iter__(self):
        return self

    def dequeue(self):
        return self.next().data

    def next(self):
        if self.head and not self.curr:
            self.curr = self.head
            return self.curr
        elif self.curr.next:
            self.curr = self.curr.next
            return self.curr
        else:
            raise StopIteration

    def enqueue(self, data):
        n = Node(data)
        if not self.head:
            self.head = n
            self.tail = n
        else:
            self.tail.next = n
            self.tail = self.tail.next

    def front(self):
        a = self.dequeue()
        self.enqueue(a)
        return a

List Queue:

class Queue:

    def __init__(self):
        self._items = []

    def enqueue(self, item):
        self._items.append(item)

    def dequeue(self):
        a = self._items[0]
        del self._items[0]
        return a

    def front(self):
        return self._items[0]

    def is_empty(self):
        return self._items == []

Actually after a bit of research, the best way to use a Queue class would be to take advantage of the deque objects in collections package. I may implement and benchmark it if I ever find the time. For more info: http://docs.python.org/2/library/collections.html#collections.deque

CSC148 Stuff by Cem Yildirim

Tuesday, 28 January 2014

Queue Implementation with Linked Lists