Stack -- Standard Library Specification¶

This document covers the standard library stack implementations in Go, Java, and Python: their APIs, performance characteristics, internal mechanics, and best practices.

Table of Contents¶

1. Go: Slice as Stack
2. Java: Stack, ArrayDeque, and Deque Interface
3. Python: list as Stack
4. Comparison Table
5. Best Practices

Go: Slice as Stack¶

Go has no dedicated stack type. The idiomatic approach is to use a slice ([]T) as a stack.

API Pattern¶

// Declare
var stack []int

// Push
stack = append(stack, value)

// Pop
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]

// Peek
top := stack[len(stack)-1]

// IsEmpty
isEmpty := len(stack) == 0

// Size
size := len(stack)

Internal Mechanics¶

Go slices are backed by a dynamically resizable array. Key details:

Growth Behavior¶

s := []int{}
// cap: 0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> ...
for i := 0; i < 100; i++ {
    s = append(s, i)
    fmt.Printf("len=%d cap=%d\n", len(s), cap(s))
}

Memory Considerations¶

Slice does not release memory on pop. When you do stack = stack[:len(stack)-1], the underlying array retains its capacity. The "popped" element is still in memory (though inaccessible via the slice).

To release memory for large stacks that shrink significantly:

// Manual shrink if utilization is low
if len(stack) > 0 && len(stack) < cap(stack)/4 {
    newStack := make([]int, len(stack))
    copy(newStack, stack)
    stack = newStack
}

Pre-allocation¶

If you know the approximate size, pre-allocate to avoid repeated growth:

stack := make([]int, 0, 1000) // capacity 1000, length 0

Thread Safety¶

Go slices are NOT thread-safe. For concurrent access, wrap with a sync.Mutex:

type SafeStack struct {
    mu   sync.Mutex
    data []int
}

func (s *SafeStack) Push(val int) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.data = append(s.data, val)
}

func (s *SafeStack) Pop() (int, bool) {
    s.mu.Lock()
    defer s.mu.Unlock()
    if len(s.data) == 0 {
        return 0, false
    }
    top := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return top, true
}

Java: Stack, ArrayDeque, and Deque Interface¶

Java has multiple stack-capable classes. The recommended one is ArrayDeque.

java.util.Stack (Legacy -- Do NOT Use)¶

Stack extends Vector, which is synchronized on every operation. This makes it slow for single-threaded use and poorly designed for concurrent use.

Stack<Integer> stack = new Stack<>();
stack.push(1);
int top = stack.pop();
int peek = stack.peek();
boolean empty = stack.isEmpty();
int size = stack.size();

Why avoid it: - Inherits from Vector (synchronized, slow). - Allows get(index) and insertElementAt() -- breaks stack abstraction. - Iterator traverses bottom-to-top, which is confusing for a stack.

java.util.ArrayDeque (Recommended)¶

ArrayDeque is a resizable circular array implementing the Deque interface. It is the best general-purpose stack in Java.

Deque<Integer> stack = new ArrayDeque<>();

// Push
stack.push(value);       // adds to front (acts as top)

// Pop
int top = stack.pop();   // removes from front

// Peek
int top = stack.peek();  // reads front without removing

// IsEmpty
boolean empty = stack.isEmpty();

// Size
int size = stack.size();

Internal Mechanics¶

Deque Interface Methods (Stack Usage)¶

LinkedList as Stack (Not Recommended)¶

LinkedList also implements Deque but has higher overhead per element (node objects + pointers).

Deque<Integer> stack = new LinkedList<>(); // works but slower

Thread-Safe Options¶

// Concurrent stack
Deque<Integer> stack = new ConcurrentLinkedDeque<>();
stack.push(1);
int top = stack.pop();

Python: list as Stack¶

Python's built-in list is the standard stack implementation.

API¶

stack = []

# Push
stack.append(value)

# Pop
top = stack.pop()         # raises IndexError if empty

# Peek
top = stack[-1]           # raises IndexError if empty

# IsEmpty
is_empty = len(stack) == 0
# or: is_empty = not stack

# Size
size = len(stack)

Internal Mechanics¶

Growth Formula (CPython)¶

From CPython source (Objects/listobject.c):

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

This grows by approximately 12.5% plus a small constant, which is more conservative than Go or Java's doubling strategy.

Performance of append/pop¶

Important: pop(0) shifts all elements and is O(n). For FIFO behavior, use collections.deque.

collections.deque as Stack¶

deque can also serve as a stack with O(1) append/pop on both ends. However, for pure stack usage, list is slightly faster due to simpler memory layout.

from collections import deque

stack = deque()
stack.append(1)      # push
top = stack.pop()    # pop
top = stack[-1]      # peek

Thread Safety¶

Python's GIL makes individual list.append() and list.pop() operations thread-safe at the bytecode level. However, compound operations (check-then-act) are NOT atomic:

# NOT thread-safe compound operation:
if stack:           # another thread could pop between these
    stack.pop()     # two bytecode operations

# Use a lock for compound operations:
import threading
lock = threading.Lock()

with lock:
    if stack:
        stack.pop()

For truly concurrent stacks, use queue.LifoQueue:

from queue import LifoQueue

stack = LifoQueue()
stack.put(1)          # push (thread-safe, blocking)
top = stack.get()     # pop (thread-safe, blocking)
empty = stack.empty()

typing and Type Hints¶

from typing import List

stack: List[int] = []
# or in Python 3.9+:
stack: list[int] = []

Comparison Table¶

*Individual operations only; compound check-then-act is not safe.

Best Practices¶

Go¶

1. Use []T slices -- do not import external stack libraries for simple cases.
2. Pre-allocate with make([]T, 0, expectedSize) when the size is known.
3. For concurrent access, use sync.Mutex or a channel-based approach.
4. Be aware that popped elements are retained in memory until the slice is reallocated.

Java¶

1. Never use java.util.Stack. Use ArrayDeque instead.
2. Program to the Deque interface for flexibility.
3. Use ConcurrentLinkedDeque for concurrent scenarios.
4. Remember that ArrayDeque does not allow null elements.

Python¶

1. Use list for single-threaded stacks -- it is the fastest option.
2. Use collections.deque if you also need efficient front operations.
3. Use queue.LifoQueue for thread-safe, blocking stack behavior.
4. Never use list.pop(0) for stack operations -- it is O(n).
5. Catch IndexError on pop/peek of empty stacks, or check if stack: first.