Stacks and Queues

Stacks and Queues are both array like structures that have different methods for storing and removing values from them. You can only add elements to the head of a stack or a queue by design.

Stacks

Stacks follow the LIFO rule: Last In, First Out. This can be thought of as a stack of plates, where you add plates to the top of the stack, and then also remove them from the top. This is typically implemented with a singularly linked list or a dynamic array.

class Node:
    def __init__(self, val):
        self.next = None
        self.val = val

class Stack:
    def __init__(self):
        self.head = None

    def push(self, node):
        node.next = self.head
        self.head = node

    def pop(self):
        ret = self.head
        self.head = self.head.next
        return ret
    
    def peek(self):
        return self.head.val if self.head else None

Complexity

• Pushing onto stack: O(1)
• Popping off stack: O(1)
• Peeking the top element: O(1)
• Searching: O(n)

Queue

Queues follow the FIFO rule: First In, First Out. This can be thought of a line of people, where the first person in the line is the first to leave. These are typically implemented with a doubly linked list

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, node):
        self.head.prev = node
        node.next = self.head
        self.head = node

    def dequeue(self, node):
        ret = self.tail
        self.tail = self.tail.prev
        self.tail.next = None
        return ret

    def peek(self):
        return self.tail.val if self.tail else None

Complexity

• Enqueuing (adding) to queue: O(1)
• Dequeuing (removing) from queue: O(1)
• Peeking the front element: O(1)
• Searching: O(n)