Queues

Queues are similar to stacks. The main difference is that queues are FIFO instead of LIFO. I like to imagine the drive through line at In N Out when I think of queues — the first car will be served before the rest. In a stack, we push and pop from a dynamic array; however, queues are different because it require that we enqueue and dequeue by implementing a linked list. We will start with a ListNode object:

Figure 1

When we enqueue, we add an element to the tail of the queue. Linked lists can get the tail element in O(1) time so enqueuing a stack is a constant time operation.

def enqueue(self, val):
    node = ListNode(val)

    if self.right:
        self.right.next = node
        self.right = self.right.next
    else:
        self.left, self.right = node, node

Figure 2

Like the name suggests, dequeuing removes the element from the front of the queue. This is also a constant time operation.

def dequeue(self):
    if not self.left:
        return None
    
    val = self.left.val
    self.left = self.left.next
    # Check to see if no more elements left
    if not self.left:
        self.right = None
    return val

Figure 3