Skip to content

Stacks & Queues

WARNING: This page may include outdated or invalid syntax. Examples are illustrative and will be updated to current Harneet standards (var/mandatory parameter types/valid function syntax).

Stacks and Queues are fundamental data structures that provide ordered access to elements with different retrieval patterns. Harneet provides enhanced implementations with improved performance characteristics and additional functionality.

Stack (LIFO - Last In, First Out)

A stack follows the Last-In-First-Out principle, where the most recently added element is the first one to be removed. Think of it like a stack of plates - you add and remove plates from the top.

Creating a Stack

Creating a Stack
1
2
3
import collections

var stack = collections.new_stack()

Basic Operations

Push - Adding Elements

Push Elements
1
2
3
4
5
6
stack.push(42)
stack.push("hello")
stack.push([1, 2, 3])
stack.push({"key": "value"})

fmt.Println("Stack size:", stack.size())  // 4

Pop - Removing Elements

Pop Elements
1
2
3
4
5
6
7
8
var item = stack.pop()
fmt.Println("Popped:", item)  // {"key": "value"}

// Always check if stack is empty before popping
if !stack.is_empty() {
    var next_item = stack.pop()
    fmt.Println("Next:", next_item)  // [1, 2, 3]
}

Peek - Viewing Top Element

Peek Top Element
1
2
3
4
5
6
if !stack.is_empty() {
    var top = stack.peek()
    fmt.Println("Top element:", top)  // "hello"
    // Element remains in stack
    fmt.Println("Size still:", stack.size())  // 2
}

Enhanced Stack Features

Memory Pre-allocation

Memory Pre-allocation
1
2
3
// Pre-allocate capacity for better performance
var large_stack = collections.new_stack()
large_stack.reserve(1000)  // Pre-allocate space for 1000 elements

Batch Operations

Batch Operations
1
2
3
4
5
6
7
8
// Push multiple elements at once
var items = [1, 2, 3, 4, 5]
for item in items {
    stack.push(item)
}

// Or use functional approach
items.for_each(((item) =>) stack.push(item))

Conversion and Inspection

Conversion and Inspection
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Convert to array (maintains stack order)
var array = stack.to_array()
fmt.Println("As array:", array)

// Clear all elements
stack.clear()
fmt.Println("After clear:", stack.is_empty())  // true

// String representation
fmt.Println("Stack:", stack.inspect())

Stack Use Cases

1. Function Call Management

Function Call Management
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// Simulating function call stack
var call_stack = collections.new_stack()

function enter_function(name) {
    call_stack.push(name)
    fmt.Println("Entering:", name)
}

function exit_function() {
    if !call_stack.is_empty() {
        var name = call_stack.pop()
        fmt.Println("Exiting:", name)
    }
}

enter_function("main")
enter_function("process_data")
enter_function("validate_input")
exit_function()  // validate_input
exit_function()  // process_data
exit_function()  // main

2. Expression Evaluation

Expression Evaluation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Parentheses matching
function is_balanced(expression) {
    var stack = collections.new_stack()

    for char in expression {
        if char == "(" || char == "[" || char == "{" {
            stack.push(char)
        } else if char == ")" || char == "]" || char == "}" {
            if stack.is_empty() {
                return false
            }
            var open = stack.pop()
            if !matches(open, char) {
                return false
            }
        }
    }

    return stack.is_empty()
}

function matches(open, close) {
    return (open == "(" && close == ")") ||
           (open == "[" && close == "]") ||
           (open == "{" && close == "}")
}

3. Undo Operations

Undo Operations
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// Simple undo system
var undo_stack = collections.new_stack()
var current_state = "initial"

function perform_action(action, new_state) {
    undo_stack.push(current_state)
    current_state = new_state
    fmt.Println("Action:", action, "-> State:", current_state)
}

function undo() {
    if !undo_stack.is_empty() {
        current_state = undo_stack.pop()
        fmt.Println("Undone -> State:", current_state)
    }
}

perform_action("create_file", "file_created")
perform_action("edit_file", "file_edited")
undo()  // Back to file_created
undo()  // Back to initial

Queue (FIFO - First In, First Out)

A queue follows the First-In-First-Out principle, where the first element added is the first one to be removed. Think of it like a line at a store - first person in line is served first.

Creating a Queue

Creating a Queue
1
2
3
import collections

var queue = collections.new_queue()

Basic Operations

Enqueue - Adding Elements

Enqueue Elements
1
2
3
4
5
queue.enqueue("first")
queue.enqueue("second")
queue.enqueue("third")

fmt.Println("Queue size:", queue.size())  // 3

Dequeue - Removing Elements

Dequeue Elements
1
2
3
4
5
6
7
8
var item = queue.dequeue()
fmt.Println("Dequeued:", item)  // "first"

// Always check if queue is empty
if !queue.is_empty() {
    var next_item = queue.dequeue()
    fmt.Println("Next:", next_item)  // "second"
}

Peek - Viewing Front Element

Peek Front Element
1
2
3
4
5
6
if !queue.is_empty() {
    var front = queue.peek()
    fmt.Println("Front element:", front)  // "third"
    // Element remains in queue
    fmt.Println("Size still:", queue.size())  // 1
}

Enhanced Queue Features

Circular Buffer Implementation

The enhanced queue uses a circular buffer internally for O(1) enqueue and dequeue operations without element shifting:

Circular Buffer
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Efficient for high-throughput scenarios
var buffer = collections.new_queue()
buffer.reserve(1000)  // Pre-allocate circular buffer

// Fast operations even with many elements
for i in range(10000) {
    buffer.enqueue(i)
}

for i in range(5000) {
    buffer.dequeue()  // Still O(1), no shifting needed
}

Batch Processing

Batch Processing
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// Process items in batches
function process_batch(queue, batch_size) {
    var batch = []

    for i in range(batch_size) {
        if queue.is_empty() {
            break
        }
        batch.append(queue.dequeue())
    }

    if batch.size() > 0 {
        fmt.Println("Processing batch:", batch)
        // Process batch...
    }
}

Queue Use Cases

1. Task Scheduling

Task Scheduling
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Simple task scheduler
var task_queue = collections.new_queue()

struct Task {
    name: string
    priority: int
    action: function()
}

function schedule_task(task) {
    task_queue.enqueue(task)
    fmt.Println("Scheduled:", task.name)
}

function process_tasks() {
    for !task_queue.is_empty() {
        var task = task_queue.dequeue()
        fmt.Println("Processing:", task.name)
        task.action()
    }
}

// Usage
schedule_task(Task{name: "backup", priority: 1, action: || fmt.Println("Backing up...")})
schedule_task(Task{name: "cleanup", priority: 2, action: || fmt.Println("Cleaning up...")})
process_tasks()
Breadth-First Search
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// BFS algorithm using queue
function bfs(graph, start) {
    var queue = collections.new_queue()
    var visited = collections.new_set()

    queue.enqueue(start)
    visited.add(start)

    for !queue.is_empty() {
        var node = queue.dequeue()
        fmt.Println("Visiting:", node)

        for neighbor in graph.get_neighbors(node) {
            if !visited.contains(neighbor) {
                visited.add(neighbor)
                queue.enqueue(neighbor)
            }
        }
    }
}

3. Producer-Consumer Pattern

Producer-Consumer Pattern
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Simple producer-consumer with queue
var work_queue = collections.new_concurrent_queue()  // Thread-safe version

function producer() {
    for i in range(10) {
        var work_item = "task_" + i.to_string()
        work_queue.enqueue(work_item)
        fmt.Println("Produced:", work_item)
        // Simulate work
        sleep(100)
    }
}

function consumer() {
    for {
        if !work_queue.is_empty() {
            var item = work_queue.dequeue()
            fmt.Println("Consumed:", item)
            // Process item...
        } else {
            sleep(50)  // Wait for more work
        }
    }
}

// Start producer and consumer concurrently
do producer()
do consumer()

Performance Characteristics

Time Complexity

Operation Stack Queue Notes
Push/Enqueue O(1) O(1) Amortized for dynamic resizing
Pop/Dequeue O(1) O(1) No element shifting in enhanced queue
Peek O(1) O(1) View without removal
Size O(1) O(1) Cached size counter
Is Empty O(1) O(1) Simple size check
Clear O(1) O(1) Reset pointers, GC handles cleanup

Space Complexity

  • Stack: O(n) where n is the number of elements
  • Queue: O(n) with circular buffer overhead (typically 25-50% extra capacity)

Memory Management

Both structures automatically manage memory:

Automatic Memory Management
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Automatic resizing
var stack = collections.new_stack()
for i in range(1000000) {
    stack.push(i)  // Automatically grows as needed
}

// Memory is reclaimed when elements are removed
for i in range(500000) {
    stack.pop()  // Memory may be reclaimed based on shrink threshold
}

Error Handling

Both stacks and queues handle errors consistently:

Error Handling
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// Safe operations
var stack = collections.new_stack()

// Pop from empty stack returns error
var result = stack.pop()
if result.type() == "ERROR" {
    fmt.Println("Cannot pop from empty stack")
}

// Better: check before operating
if !stack.is_empty() {
    var item = stack.pop()  // Safe
}

// Peek is always safe (returns null for empty)
var top = stack.peek()
if top != null {
    fmt.Println("Top:", top)
}

Best Practices

1. Choose the Right Structure

  • Use Stack for: Undo operations, function calls, expression parsing, backtracking algorithms
  • Use Queue for: Task scheduling, BFS algorithms, producer-consumer patterns, buffering

2. Pre-allocate When Possible

Pre-allocate Capacity
1
2
3
// If you know approximate size, pre-allocate
var large_stack = collections.new_stack()
large_stack.reserve(10000)  // Avoids multiple reallocations

3. Check Emptiness Before Operations

Check Emptiness
1
2
3
4
// Always check before pop/dequeue
if !collection.is_empty() {
    var item = collection.pop()  // or dequeue()
}

4. Use Concurrent Versions for Multi-threading

Concurrent Versions
1
2
3
// For concurrent access
var shared_queue = collections.new_concurrent_queue()
// Thread-safe operations

5. Batch Operations for Performance

Batch Operations Performance
1
2
3
4
5
6
7
// Instead of individual operations in loops
for item in large_array {
    queue.enqueue(item)  // Many individual calls
}

// Consider batching if available
queue.enqueue_all(large_array)  // Single batch operation

Advanced Examples

Stack-based Calculator

Stack-based Calculator
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function evaluate_postfix(expression) {
    var stack = collections.new_stack()
    var tokens = expression.split(" ")

    for token in tokens {
        if is_number(token) {
            stack.push(token.to_int())
        } else {
            var b = stack.pop()
            var a = stack.pop()
            var result = apply_operator(a, b, token)
            stack.push(result)
        }
    }

    return stack.pop()
}

// Usage: evaluate_postfix("3 4 + 2 *") -> 14

Queue-based Rate Limiter

Queue-based Rate Limiter
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct RateLimiter {
    requests: Queue
    max_requests: int
    time_window: int  // milliseconds
}

function new_rate_limiter(max_requests, time_window) {
    return RateLimiter{
        requests: collections.new_queue(),
        max_requests: max_requests,
        time_window: time_window
    }
}

function (rl *RateLimiter) allow_request() {
    var now = current_time_millis()

    // Remove old requests outside time window
    for !rl.requests.is_empty() {
        var oldest = rl.requests.peek()
        if now - oldest > rl.time_window {
            rl.requests.dequeue()
        } else {
            break
        }
    }

    // Check if we can allow this request
    if rl.requests.size() < rl.max_requests {
        rl.requests.enqueue(now)
        return true
    }

    return false
}

See Also

This comprehensive guide covers the enhanced stack and queue implementations in Harneet, providing both basic usage and advanced patterns for real-world applications.