Stacks · learnDataStructures

Call stack, Complexity, Pros/Cons, and Implementations

Call stack (what happens during function calls)

Every function call creates a stack frame that stores parameters, locals, and a return address. New calls push a frame and become the active one; when a function returns, its frame is popped and control resumes in the caller. Recursion grows the call stack until a base case; then frames unwind in reverse order. A stack overflow occurs when too many frames are pushed (for example, in deep or unbounded recursion). Prefer iterative solutions when appropriate, or ensure base cases are reached quickly.

Typical time complexity

Operation	Array-backed	Linked-list-backed	Notes
`push(x)`	Amortized O(1)	O(1)	Array may occasionally resize → one O(n) copy
`pop()`	O(1)	O(1)	Remove the top
`peek()`	O(1)	O(1)	Read top element
`isEmpty()`	O(1)	O(1)	Check size/head
`size()`	O(1)	O(1)	Keep a counter

Pros and cons

Stacks have a tiny, easy API and provide O(1) operations, which makes them a great fit for undo/redo, parsing, and search. The limitation is that only the top is visible; array-backed stacks sometimes pay a resizing cost, while linked-list stacks add per-node memory overhead.

Implementations by language — how to create & use

Python

Python list as a stack (recommended)

Best for everyday Python. Lists provide append and pop at the end in amortized O(1), plus easy peek with s[-1].

s = []
s.append(10)     # push
s.append(20)
top = s[-1]      # peek -> 20
x = s.pop()      # pop -> 20
empty = (len(s) == 0)
n = len(s)

collections.deque used as a stack

Also O(1) for push/pop on the right; implemented in C and memory efficient under heavy churn.

from collections import deque
s = deque()
s.append("A")    # push
s.append("B")
print(s[-1])     # peek -> "B"
print(s.pop())   # pop  -> "B"
print(len(s))

Educational: minimal array-backed Stack class

Fixed-capacity example to show the core logic; raises on overflow/underflow.

class ArrayStack:
    def __init__(self, capacity=8):
        self._a = [None] * capacity
        self._n = 0
    def push(self, x):
        if self._n == len(self._a):
            raise IndexError("stack full")
        self._a[self._n] = x
        self._n += 1
    def pop(self):
        if self._n == 0:
            raise IndexError("stack empty")
        self._n -= 1
        x = self._a[self._n]
        self._a[self._n] = None
        return x
    def peek(self):
        if self._n == 0:
            raise IndexError("stack empty")
        return self._a[self._n-1]
    def isEmpty(self): return self._n == 0
    def size(self):    return self._n

Java

ArrayDeque as a stack (recommended)

Modern, fast stack API: push, pop, peek, isEmpty, size. Prefer over legacy Stack.

import java.util.*;
public class JStackDemo {
  public static void main(String[] args) {
    ArrayDeque<Integer> s = new ArrayDeque<>();
    s.push(1); s.push(2); s.push(3);
    System.out.println(s.peek()); // 3
    System.out.println(s.pop());  // 3
    System.out.println(s.size()); // 2
  }
}

Educational: minimal linked-list stack

Shows how a stack can be built by hand; all operations O(1).

public class LinkedStack<T> {
  private static class Node<T> { T v; Node<T> next; Node(T v){ this.v=v; } }
  private Node<T> top; private int n = 0;

  public void push(T x){ Node<T> t = new Node<>(x); t.next = top; top = t; n++; }
  public T pop(){
    if (n == 0) throw new java.util.NoSuchElementException();
    T v = top.v; top = top.next; n--; return v;
  }
  public T peek(){
    if (n == 0) throw new java.util.NoSuchElementException();
    return top.v;
  }
  public boolean isEmpty(){ return n==0; }
  public int size(){ return n; }
}

Legacy java.util.Stack (for completeness)

Older synchronized class; API is fine but ArrayDeque is the modern choice.

import java.util.Stack;
Stack<String> s = new Stack<>();
s.push("x"); s.push("y");
System.out.println(s.peek());
System.out.println(s.pop());

C++

std::stack (standard adapter)

Simple LIFO adapter over another container (defaults to std::deque<T>).

#include <stack>
#include <iostream>
int main(){
  std::stack<int> s;
  s.push(10); s.push(20); s.push(30);
  std::cout << s.top() << "\n"; // 30
  s.pop();
  std::cout << s.size() << "\n"; // 2
}

DIY with std::vector (fast and cache-friendly)

When you want full control and no abstraction overhead.

#include <vector>
#include <iostream>
int main(){
  std::vector<int> s;
  s.push_back(1); s.push_back(2); s.push_back(3);
  std::cout << s.back() << "\n"; // 3
  s.pop_back();
  std::cout << s.size() << "\n"; // 2
}

Conceptual Questions

What does LIFO mean in the context of stacks?
If you push 1, then 2, then 3, which number will be removed first if you pop once?
Why might an array-backed stack sometimes take more than constant time for a push?
How does the call stack allow recursion to work?
Why can deep recursion lead to a stack overflow?
Give one real-world example of a stack.

Answers: (1) Last-In, First-Out — the last pushed is the first popped. (2) 3. (3) The array may need to resize and copy elements when it runs out of capacity. (4) Each call pushes a new frame with its locals and return address; returns pop frames to resume the caller. (5) Too many frames exhaust the fixed stack space. (6) Examples include a pile of plates, browser back button history, or undo/redo in an editor.

learnDataStructures

Stacks (LIFO)

Stack — tiny reference snippets

Operations (pseudocode)

Interactive stack simulator