algo-stacks-queues

name	algo-stacks-queues
description	Implement Stack (LIFO)/Queue (FIFO) in Python (array, linked-list, two-stack) with O(1) ops; validate balanced brackets/RNA dot-bracket notation. Use for stack/queue from scratch, backing BFS/DFS, or checking parens.
tool_type	python
primary_tool	Python

Stacks and Queues

When to Use

• Implementing a stack or queue from scratch (interviewer disallows list/collections.deque)
• Validating balanced brackets/parentheses, or nested notations like RNA secondary-structure dot-bracket strings ((((...))))
• Building undo/redo, browser back-button history, or expression (postfix/infix) evaluators
• Backing a BFS (queue) or DFS/backtracking (stack) traversal — see algo-bfs-dfs
• Explaining why list.pop(0) is a queue anti-pattern, or the "queue with two stacks" interview question

Version Compatibility

Pure Python standard library only — no third-party dependencies. Works on Python ≥3.8 (uses typing.Optional); collections.deque and queue.PriorityQueue are stdlib since Python 2, unchanged in behavior through Python 3.13.

Prerequisites

• Comfort with Python classes and references (a linked node's next is a reference, not a copy)
• Big-O notation — see algo-complexity-analysis
• No external packages needed

Stack (LIFO)

All operations O(1). Use for: DFS, backtracking, bracket matching, undo/redo, recursion-to-iteration.

Goal: a stack with push/pop/peek that raises on empty rather than returning None (silent None hides bugs).

Approach: array-based version wraps a Python list (amortized O(1) append/pop from the end); linked-list version prepends nodes at _top for true O(1) push with no resize.

from typing import Any, Optional, List


class ArrayStack:
    """Stack backed by a Python list. push/pop/peek are O(1) amortized."""

    def __init__(self) -> None:
        self._items: List[Any] = []

    def push(self, item: Any) -> None:
        self._items.append(item)

    def pop(self) -> Any:
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self._items.pop()

    def peek(self) -> Any:
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def () -> :
         (._items)

     () -> :
         (._items) > 


 :
    

     () -> :
        .value = value
        . = next_node


 :
    

     () -> :
        ._top: [StackNode] = 
        ._size = 

     () -> :
        ._top = StackNode(item, ._top)
        ._size += 

     () -> :
         ._top  :
             IndexError()
        value = ._top.value
        ._top = ._top.
        ._size -= 
         value

     () -> :
         ._top  :
             IndexError()
         ._top.value

     () -> :
         ._top  

     () -> :
         ._size


 __name__ == :
     Stack  (ArrayStack, LinkedStack):
        s = Stack()
         v  [, , ]:
            s.push(v)
         s.peek() ==   (s) == 
         s.pop() ==   s.pop() ==   s.pop() == 
         s.is_empty()
        :
            s.pop()
             , 
         IndexError:
            
    ()

Queue (FIFO)

All operations O(1). Use for: BFS, task scheduling, message buffers, simulation.

Goal: enqueue at the rear, dequeue from the front, both O(1) — never shift a Python list.

Approach: LinkedQueue keeps _front/_rear pointers so both ends are reachable without scanning; QueueWithTwoStacks shows the classic "simulate a queue with two stacks" trick (push-only inbox, pop-only outbox, transfer on demand — O(1) amortized per operation since each element moves at most 4 times total).

from typing import Any, Optional


class QueueNode:
    def __init__(self, value: Any, next_node: Optional["QueueNode"] = None) -> None:
        self.value = value
        self.next = next_node


class LinkedQueue:
    """Queue backed by a singly linked list with cached front/rear pointers."""

    def __init__(self) -> None:
        self._front: Optional[QueueNode] = None
        self._rear: Optional[QueueNode] = None
        self._size = 0

    def enqueue(self, item: Any) -> None:
        node = QueueNode(item)
        if self._rear is None:
            self._front = self._rear = node
        else:
            self._rear.next = node
            self._rear = node
        self._size += 1

     () -> :
         ._front  :
             IndexError()
        value = ._front.value
        ._front = ._front.
         ._front  :
            ._rear = 
        ._size -= 
         value

     () -> :
         ._front  :
             IndexError()
         ._front.value

     () -> :
         ._front  

     () -> :
         ._size


 :
    

     () -> :
        ._inbox: ArrayStack = ArrayStack()
        ._outbox: ArrayStack = ArrayStack()

     () -> :
        
        ._inbox.push(item)

     () -> :
        
         ._outbox.is_empty():
              ._inbox.is_empty():
                ._outbox.push(._inbox.pop())
         ._outbox.is_empty():
             IndexError()
         ._outbox.pop()

     () -> :
         ._inbox.is_empty()  ._outbox.is_empty()


 __name__ == :
     Queue  (LinkedQueue, QueueWithTwoStacks):
        q = Queue()
         v  [, , ]:
            q.enqueue(v)
         q.dequeue() ==   q.dequeue() ==   q.dequeue() == 
         q.is_empty()
    ()

Application: Bracket / Dot-Bracket Matching

Goal: validate that brackets are balanced — the same algorithm validates RNA secondary-structure dot-bracket notation ((((..)).)) where ( must pair with a later ) and unmatched/crossed brackets indicate invalid structure.

Approach: push each opening symbol; on a closing symbol, pop and check it matches. Balanced iff the stack ends empty.

def is_balanced(expression: str, pairs: dict = None) -> bool:
    """
    Check that brackets in `expression` are balanced and properly nested.

    Works for plain brackets ("(){}[]") and RNA dot-bracket notation
    (only "()" used; "." is ignored) by passing pairs={')': '('}.

    >>> is_balanced("({[]})")
    True
    >>> is_balanced("([)]")
    False
    >>> is_balanced("(((...)).)")   # RNA dot-bracket, one unmatched '('
    False
    """
    matching = pairs if pairs is not None else {')': '(', ']': '[', '}': '{'}
    opening = set(matching.values())
    closing = set(matching.keys())

    stack = ArrayStack()
    for char in expression:
        if char in opening:
            stack.push(char)
        elif char in closing:
            if stack.is_empty() or stack.pop() != matching[char]:
                return False
    return stack.is_empty()


if __name__ == "__main__":
    assert is_balanced("({[]})") is True
    assert is_balanced("([)]") is False
    assert is_balanced("(((...))") is   
     is_balanced(, pairs={: })    
    ()

Python stdlib equivalents

• Stack: just use list (append/pop)
• Queue: collections.deque (append/appendleft + pop/popleft, all O(1))
• Priority queue: heapq or queue.PriorityQueue

Pitfalls

• Using list.pop(0) as a queue is O(n) (shifts every remaining element) — use collections.deque.popleft() instead
• Array-based stack push is O(1) amortized but O(n) worst case during list resize
• In QueueWithTwoStacks, only transfer inbox→outbox when outbox is empty — transferring on every call breaks the O(1)-amortized guarantee and re-reverses order incorrectly
• Bracket matching must check stack.is_empty() before popping on a closing symbol, otherwise a lone ) raises instead of returning False
• For RNA dot-bracket validation, remember pseudoknots (crossed pairs, e.g. ([)]) are invalid under simple bracket matching — they need a different representation (extended bracket alphabet or base-pair list)

See Also

• algo-linked-lists — the node/pointer mechanics LinkedStack/LinkedQueue are built on
• algo-bfs-dfs — BFS uses a queue, DFS uses a stack (or recursion)
• algo-dynamic-arrays — why array-based push/pop is O(1) amortized, not worst-case
• bio-rna-structure-secondary-structure-prediction — dot-bracket notation in a real RNA-folding context