DSA Module
The dsa module provides data structures and algorithms including stack, queue, heap, binary tree, graph, and utility functions for sorting and searching.
Import
Collection Interface
All DSA data structures implement the Collection<T> interface:
| Method | Returns | Description |
|---|---|---|
len() | int | Returns the number of elements |
is_empty() | bool | Returns true if the collection is empty |
clear() | void | Removes all elements |
to_list() | list<T> | Returns elements as a list |
Stack
A LIFO (last-in, first-out) collection.
Stack Methods
| Method | Returns | Description |
|---|---|---|
Stack<T>.new() | Stack<T> | Creates an empty stack |
push(T value) | void | Adds an element to the top |
pop() | optional<T> | Removes and returns the top element |
peek() | optional<T> | Returns the top element without removing it |
Also implements len(), is_empty(), clear(), to_list().
Queue
A FIFO (first-in, first-out) collection.
Queue Methods
| Method | Returns | Description |
|---|---|---|
Queue<T>.new() | Queue<T> | Creates an empty queue |
enqueue(T value) | void | Adds an element to the back |
dequeue() | optional<T> | Removes and returns the front element |
peek() | optional<T> | Returns the front element without removing it |
Also implements len(), is_empty(), clear(), to_list().
Heap
A min-heap collection where the smallest element is always at the top.
Heap Methods
| Method | Returns | Description |
|---|---|---|
Heap<T>.new() | Heap<T> | Creates an empty heap |
push(T value) | void | Adds an element |
pop() | optional<T> | Removes and returns the minimum element |
peek() | optional<T> | Returns the minimum element without removing it |
Type constraint: T is Comparable
Also implements len(), is_empty(), clear(), to_list().
BinaryTree
A binary search tree with set semantics (duplicates are ignored).
BinaryTree Methods
| Method | Returns | Description |
|---|---|---|
BinaryTree<T>.new() | BinaryTree<T> | Creates an empty tree |
insert(T value) | void | Adds an element |
remove(T value) | void | Removes an element |
contains(T value) | bool | Checks if an element exists |
Type constraint: T is Comparable
Also implements len(), is_empty(), clear(), to_list() (returns elements in sorted order via inorder traversal).
Graph
A directed graph using adjacency lists.
Graph Methods
| Method | Returns | Description |
|---|---|---|
Graph<T>.new() | Graph<T> | Creates an empty graph |
add_vertex(T value) | void | Adds a vertex |
add_edge(T from, T to) | void | Adds a directed edge |
neighbors(T value) | list<T> | Returns neighbors of a vertex |
bfs(T start) | list<T> | Breadth-first search traversal |
Type constraint: T is Hashable & Stringable
Also implements len(), is_empty(), clear(), to_list() (returns vertices in insertion order).
Algorithm Functions
Functions
| Function | Signature | Description |
|---|---|---|
sort | <T is Comparable>(list<T> items) returns list<T> | Quicksort algorithm |
binary_search | <T is Comparable, E is Collection<T>>(E items, T target) returns int | Returns index or -1 if not found |
max | <T is Comparable & Stringable, E is Collection<T>>(E collection) returns optional<T> | Returns maximum element |
min | <T is Comparable & Stringable, E is Collection<T>>(E collection) returns optional<T> | Returns minimum element |
reverse | <T, E is Collection<T>>(E collection) returns list<T> | Returns reversed list |