queues.py

'queue implemented with a list (dyanmic array) with O(n) time operations'
class Queue:
    def __init__(self):
        self.data = [] # using a python list here instead of array (we need dynamic sizing)

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

    def dequeue(self):
        remaining = self.data[1:] # slices from index 1 to the end of the list
        self.data = remaining
        first_item = self.data[0]
        return first_item.val

my_queue = Queue()
my_queue.enqueue('wulymammoth')
my_queue.enqueue('builder_of_things')
my_queue.dequeue() # 'wulymammoth'

'queue implemented with a singly-linked list with O(1) time operations'
class Node: # singly-linked list node
    def __init__(self, val):
        self.val = val
        self.next = None

class QueueWithLL:
    def __init__(self):
        # the head of the queue (singly-linked list node)
        # when the queue is initialized, both these fields point at the empty node
        self.head = self.tail = None 

    def enqueue(self, item):
        new_node = Node(item)
        if self.head is None and self.tail is None: # empty queue
            self.head = self.tail = new_node
        else: 
            self.tail.next = new_node # set the current tail's next to the new item
            self.tail = new_node # update the tail to new item

    def dequeue(self):
        first_item = self.head
        first_item.next = None
        self.head = self.head.next
        return first_item.val

my_queue2 = QueueWithLL()
my_queue2.enqueue('wulymammoth')
my_queue2.enqueue('builder_of_things')
my_queue2.dequeue() # 'wulymammoth'