Stack & Queue

Stack — LIFO

Last In, First Out. All operations O(1).

Operations

Real-world uses

• Function call management (call stack)
• Undo/redo functionality
• Browser back/forward history
• DFS traversal (explicit stack)
• Expression evaluation (parentheses matching)

Python Implementation

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        return self.items.pop() if self.items else None

    def peek(self):
        return self.items[-1] if self.items else None

    def size(self):
        return len(self.items)

    def is_empty(self):
        return len(self.items) == 0

In Python interviews, just use a list as a stack — append() = push, pop() = pop, [-1] = peek.

# In practice
stack = []
stack.append(1)   # push
stack.pop()       # pop
stack[-1]         # peek

---

Queue — FIFO

First In, First Out. Use collections.deque — O(1) on both ends.

Operations

⚠️ Never use list for a queue — list.pop(0) is O(n). Always use deque.

Python Implementation

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, val):
        self.items.append(val)       # add to right (back)

    def dequeue(self):
        return self.items.popleft() if self.items else None  # remove from left (front)

    def peek(self):
        return self.items[0] if self.items else None

    def size(self):
        return len(self.items)

    def is_empty(self):
        return len(self.items) == 0

In practice during interviews, just use deque directly.

from collections import deque
queue = deque()
queue.append(1)     # enqueue
queue.popleft()     # dequeue
queue[0]            # peek front

---

Queue using Linked List — O(1) everywhere

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

class LLQueue:
    def __init__(self):
        self.head = None  # front (dequeue here)
        self.tail = None  # back (enqueue here)

    def enqueue(self, val):
        node = Node(val)
        if self.tail:
            self.tail.next = node
        self.tail = node
        if not self.head:
            self.head = node

    def dequeue(self):
        if not self.head:
            return None
        val = self.head.val
        self.head = self.head.next
        if not self.head:
            self.tail = None
        return val

---

Interview Patterns → see [[Stacks]]