Stacks and The Call Stack

        
          
#include <stdio.h>
#include <stdlib.h> // For malloc, realloc, free

typedef struct {
  int *data;
  int top;      // Index of the top element (or -1 if empty)
  int capacity; // Current allocated capacity
} ArrayStack;

// Initialize stack
void init_array_stack(ArrayStack *s, int initialCapacity) {
  s->data = (int *) malloc(sizeof(int) * initialCapacity);
  if (s->data == NULL) { /* Handle error */ exit(EXIT_FAILURE); }
  s->top = -1; // Stack is empty
  s->capacity = initialCapacity;
}

// Check if stack is empty
int is_empty_array_stack(ArrayStack *s) {
  return s->top == -1;
}

// Push an element (amortized O(1))
void push_array_stack(ArrayStack *s, int item) {
  if (s->top == s->capacity - 1) { // Stack is full, resize
      s->capacity *= 2;
      s->data = (int *) realloc(s->data, sizeof(int) * s->capacity);
      if (s->data == NULL) { /* Handle error */ exit(EXIT_FAILURE); }
      printf("Stack resized to capacity: %d\n", s->capacity);
  }
  s->data[++(s->top)] = item; // Increment top, then add
}

// Pop an element (O(1))
int pop_array_stack(ArrayStack *s) {
  if (is_empty_array_stack(s)) {
      printf("Error: Stack is empty!\n");
      exit(EXIT_FAILURE);
  }
  return s->data[(s->top)--]; // Return top, then decrement
}

// Peek at the top element (O(1))
int peek_array_stack(ArrayStack *s) {
  if (is_empty_array_stack(s)) {
      printf("Error: Stack is empty for peek!\n");
      exit(EXIT_FAILURE);
  }
  return s->data[s->top];
}

// Cleanup
void free_array_stack(ArrayStack *s) {
  free(s->data);
  s->data = NULL;
  s->top = -1;
  s->capacity = 0;
}

int main() {
  ArrayStack s;
  init_array_stack(&s, 2);

  push_array_stack(&s, 10); // [10]
  push_array_stack(&s, 20); // [10, 20]
  printf("Peek: %d\n", peek_array_stack(&s)); // 20
  push_array_stack(&s, 30); // [10, 20, 30] (resizes)

  printf("Popped: %d\n", pop_array_stack(&s)); // 30
  printf("Popped: %d\n", pop_array_stack(&s)); // 20
  printf("Is Empty: %d\n", is_empty_array_stack(&s)); // 0 (false)
  printf("Popped: %d\n", pop_array_stack(&s)); // 10
  printf("Is Empty: %d\n", is_empty_array_stack(&s)); // 1 (true)

  free_array_stack(&s);
  return 0;
}
        
      

        
          
class Stack:
  def __init__(self):
      self._items = [] # Use a Python list as the underlying storage

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

  def push(self, item):
      self._items.append(item) # O(1) amortized

  def pop(self):
      if self.is_empty():
          raise IndexError("pop from empty stack")
      return self._items.pop() # O(1)

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

  def size(self):
      return len(self._items)

# Main for demonstration
s = Stack()
s.push(10) # [10]
s.push(20) # [10, 20]
print(f"Peek: {s.peek()}") # 20
s.push(30) # [10, 20, 30]

print(f"Popped: {s.pop()}") # 30
print(f"Popped: {s.pop()}") # 20
print(f"Is Empty: {s.is_empty()}") # False
print(f"Popped: {s.pop()}") # 10
print(f"Is Empty: {s.is_empty()}") # True

        
      

        
          
class Stack {
  constructor() {
      this._items = []; // Use a JavaScript array as the underlying storage
  }

  isEmpty() {
      return this._items.length === 0;
  }

  push(item) {
      this._items.push(item); // O(1) amortized
  }

  pop() {
      if (this.isEmpty()) {
          throw new Error("pop from empty stack");
      }
      return this._items.pop(); // O(1)
  }

  peek() {
      if (this.isEmpty()) {
          throw new Error("peek from empty stack");
      }
      return this._items[this._items.length - 1]; // O(1)
  }

  size() {
      return this._items.length;
  }
}

// Main for demonstration
const s = new Stack();
s.push(10); // [10]
s.push(20); // [10, 20]
console.log("Peek:", s.peek()); // 20
s.push(30); // [10, 20, 30]

console.log("Popped:", s.pop()); // 30
console.log("Popped:", s.pop()); // 20
console.log("Is Empty:", s.isEmpty()); // false
console.log("Popped:", s.pop()); // 10
console.log("Is Empty:", s.isEmpty()); // true

        
      

        
          
#include <stdio.h>

void infinite_recursion() {
  printf("Pushing another frame...\n");
  infinite_recursion(); // Calls itself endlessly
}

int main() {
  infinite_recursion();
  return 0;
}
// This program will eventually crash with a 'Stack Overflow' error.

        
      

        
          
import sys

# Python has a default recursion limit (e.g., 1000)
# You can increase it, but will still hit stack overflow for deep recursion.
# sys.setrecursionlimit(2000)

def infinite_recursion():
  print("Pushing another frame...")
  infinite_recursion() # Calls itself endlessly

# This program will eventually hit Python's recursion limit and raise
# a RecursionError, which is Python's way of preventing a C-level stack overflow.
try:
  infinite_recursion()
except RecursionError:
  print("Caught RecursionError (Python's stack overflow)")

        
      

        
          
function infiniteRecursion() {
  console.log("Pushing another frame...");
  infiniteRecursion(); // Calls itself endlessly
}

// This program will eventually crash with a 'Maximum call stack size exceeded' error.
try {
  infiniteRecursion();
} catch (e) {
  console.error("Caught error:", e.message); // Will be "Maximum call stack size exceeded"
}