Stack Data Structure

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The most recently added element is the first one to be removed - like a stack of plates where you can only add or remove from the top.

Core Operations

Stacks support two primary operations:

1. Push - Add an element to the top 2. Pop - Remove the element from the top

Additional operations:

• Peek/Top - View the top element without removing it
• IsEmpty - Check if the stack is empty
• Size - Get the number of elements

graph TD
    A[Empty Stack] -->|Push 1| B[Stack: 1]
    B -->|Push 2| C[Stack: 1, 2]
    C -->|Push 3| D[Stack: 1, 2, 3]
    D -->|Pop| E[Returns 3, Stack: 1, 2]
    E -->|Pop| F[Returns 2, Stack: 1]

    style A fill:#f0f0f0
    style D fill:#e8f5e9
    style E fill:#fff4e1

Visual Representation

Visual stack operations:

Initial state:
┌─────────────┐
│   (empty)   │
└─────────────┘

After push(5):
┌─────────────┐
│      5      │ ← top
└─────────────┘

After push(10):
┌─────────────┐
│     10      │ ← top
├─────────────┤
│      5      │
└─────────────┘

After push(15):
┌─────────────┐
│     15      │ ← top
├─────────────┤
│     10      │
├─────────────┤
│      5      │
└─────────────┘

After pop() → returns 15:
┌─────────────┐
│     10      │ ← top
├─────────────┤
│      5      │
└─────────────┘

After peek() → returns 10 (doesn't remove):
┌─────────────┐
│     10      │ ← top (still here)
├─────────────┤
│      5      │
└─────────────┘

LIFO Principle

Last-In-First-Out means the order of removal is the reverse of the order of insertion:

Push order: 1 → 2 → 3 → 4
Pop order:  4 → 3 → 2 → 1

Like stacking books:
┌────────┐
│ Book 4 │ ← Added last, removed first
├────────┤
│ Book 3 │
├────────┤
│ Book 2 │
├────────┤
│ Book 1 │ ← Added first, removed last
└────────┘

This contrasts with:

• Queue (FIFO): First-In-First-Out (like a line of people)
• Deque: Can add/remove from both ends
• Priority Queue: Ordered by priority, not insertion order

Implementation Approaches

Array-Based Stack

class ArrayStack
  def initialize
    @items = []
  end
 
  def push(item)
    @items.push(item)
  end
 
  def pop
    @items.pop
  end
 
  def peek
    @items.last
  end
 
  def empty?
    @items.empty?
  end
 
  def size
    @items.length
  end
end

Advantages:

• Simple implementation
• Fast access (O(1) for all operations)
• Cache-friendly (contiguous memory)

Disadvantages:

• May need resizing (amortized O(1))
• Wasted space if over-allocated

Linked-List-Based Stack

class Node
  attr_accessor :value, :next
 
  def initialize(value)
    @value = value
    @next = nil
  end
end
 
class LinkedStack
  def initialize
    @top = nil
    @size = 0
  end
 
  def push(value)
    node = Node.new(value)
    node.next = @top
    @top = node
    @size += 1
  end
 
  def pop
    return nil if @top.nil?
 
    value = @top.value
    @top = @top.next
    @size -= 1
    value
  end
 
  def peek
    @top&.value
  end
 
  def empty?
    @top.nil?
  end
 
  def size
    @size
  end
end

Advantages:

• No resizing needed
• Efficient memory use (no over-allocation)
• Dynamic size

Disadvantages:

• Extra memory for pointers
• Less cache-friendly (scattered memory)
• Slightly more complex implementation

Time Complexity

All primary stack operations are O(1) - constant time:

Operation	Array-Based	Linked-List-Based
Push	O(1)*	O(1)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
IsEmpty	O(1)	O(1)
Size	O(1)	O(1)

*Amortized O(1) for array-based (occasional resizing)

Real-World Applications

1. Function Call Stack

Programming languages use stacks to manage function calls:

def factorial(n)
  return 1 if n <= 1
  n * factorial(n - 1)
end
 
factorial(3)
 
# Call stack:
# ┌──────────────┐
# │ factorial(1) │ ← top (executes first)
# ├──────────────┤
# │ factorial(2) │
# ├──────────────┤
# │ factorial(3) │
# └──────────────┘
#
# Return stack (unwinding):
# factorial(1) returns 1
# factorial(2) returns 2 * 1 = 2
# factorial(3) returns 3 * 2 = 6

See recursion and call stack for deeper exploration.

2. Undo/Redo Functionality

Text editors and applications use stacks for undo/redo:

User actions:
1. Type "Hello"
2. Type " World"
3. Delete " World"

Undo stack:
┌──────────────────┐
│ Delete " World"  │ ← Undo this first
├──────────────────┤
│ Type " World"    │
├──────────────────┤
│ Type "Hello"     │
└──────────────────┘

3. Expression Evaluation

Stacks evaluate mathematical expressions and parse syntax:

Expression: 2 + 3 * 4

Using stack (postfix evaluation):
Push 2 → [2]
Push 3 → [2, 3]
Push 4 → [2, 3, 4]
Pop 4, 3, multiply, push 12 → [2, 12]
Pop 12, 2, add, push 14 → [14]

See reverse Polish notation for more on expression evaluation.

4. Virtual Machines

YARV and other stack-based VMs use stacks as their primary execution mechanism:

# Ruby code: 5 + 3
# YARV instructions:
push 5    # Stack: [5]
push 3    # Stack: [5, 3]
add       # Stack: [8]

See YARV stack instructions for detailed examples.

5. Browser History

Web browsers use stacks for back/forward navigation:

Visit sequence: Home → Page1 → Page2 → Page3

Back stack:
┌─────────┐
│ Page3   │ ← Current page
├─────────┤
│ Page2   │ ← Back goes here
├─────────┤
│ Page1   │
├─────────┤
│ Home    │
└─────────┘

6. Syntax Parsing

Compilers use stacks to parse balanced expressions:

def is_balanced(expression)
  stack = []
  pairs = {'(' => ')', '[' => ']', '{' => '}'}
 
  expression.each_char do |char|
    if pairs.key?(char)
      stack.push(char)
    elsif pairs.value?(char)
      return false if stack.empty?
      return false if pairs[stack.pop] != char
    end
  end
 
  stack.empty?
end
 
is_balanced("([{}])")  # => true
is_balanced("([)]")    # => false

Stack Overflow

When a stack grows beyond its allocated size, a stack overflow occurs:

def infinite_recursion
  infinite_recursion  # Never returns, keeps pushing stack frames
end
 
infinite_recursion
# => SystemStackError: stack level too deep

This is why the popular programming site is called “Stack Overflow” - it references a common programming error!

Causes:

• Infinite or excessive recursion
• Very deep recursion without tail-call optimization
• Allocating large arrays on the stack (in languages like C)

Prevention:

• Use iteration instead of deep recursion
• Implement tail recursion when possible
• Increase stack size (language/platform dependent)
• Move data to heap instead of stack

Stack vs Heap

Stacks are often contrasted with the heap in memory management:

Aspect	Stack	Heap
Allocation	Automatic	Manual
Deallocation	Automatic (LIFO)	Manual or GC
Access pattern	LIFO only	Random access
Speed	Faster	Slower
Size	Limited	Large
Lifetime	Function scope	Arbitrary

Memory layout in a typical program:

┌─────────────────┐ High addresses
│     Stack       │ ← Grows downward
│       ↓         │
│                 │
│   (free space)  │
│                 │
│       ↑         │
│     Heap        │ ← Grows upward
├─────────────────┤
│   Static Data   │
├─────────────────┤
│   Code/Text     │
└─────────────────┘ Low addresses

Advanced Stack Operations

Reverse a String

def reverse_string(str)
  stack = []
  str.each_char { |c| stack.push(c) }
 
  result = ""
  result += stack.pop until stack.empty?
  result
end
 
reverse_string("hello")  # => "olleh"

Check Palindrome

def is_palindrome(str)
  stack = []
  str.each_char { |c| stack.push(c) }
 
  str.each_char do |char|
    return false if char != stack.pop
  end
 
  true
end
 
is_palindrome("racecar")  # => true

Infix to Postfix Conversion

Converting 2 + 3 * 4 to 2 3 4 * + using a stack (used by compilers):

def infix_to_postfix(expression)
  stack = []
  output = []
  precedence = {'+' => 1, '-' => 1, '*' => 2, '/' => 2}
 
  expression.split.each do |token|
    if token =~ /\d+/  # Operand
      output << token
    elsif precedence[token]  # Operator
      while !stack.empty? && precedence[stack.last].to_i >= precedence[token]
        output << stack.pop
      end
      stack.push(token)
    end
  end
 
  output.concat(stack.reverse)
  output.join(' ')
end
 
infix_to_postfix("2 + 3 * 4")  # => "2 3 4 * +"