Discover how stacks power essential computer science concepts: function calls, expression evaluation, undo operations, and much more. See stacks in action with interactive examples and visualizations.

Learning Objectives

Function Calls

Understand how programs manage function execution

Expression Evaluation

Learn infix, postfix, and prefix notations

Undo/Redo

Implement reversible operations

Browser History

Navigate through page history

Function Call Stack

Every time you call a function, the program uses a call stack to keep track of: function parameters, local variables, and return addresses. This is fundamental to how all programming languages work.

How Function Calls Work

Function called → pushed onto stack

Parameters and local variables stored

Function executes

Function returns → popped from stack

Code Example

function factorial(n) {

if (n === 0) return 1;

return n * factorial(n - 1);

}

factorial(3); // Call this

Call Stack Visualization

factorial(1)

n=1, returns 1

factorial(2)

n=2, waits for factorial(1)

factorial(3)

n=3, waits for factorial(2)

main()

Called factorial(3)

↑ Stack grows upward with each function call

Expression Evaluation & Notation Conversion

Infix Notation

Operators between operands (human-readable)

A + B

(A + B) * C

A + B * C - D

Postfix Notation

Operators after operands (stack-friendly)

A B +

A B + C *

A B C * + D -

Prefix Notation

Operators before operands (Polish notation)

+ A B

* + A B C

- + A * B C D

Interactive: Postfix Evaluation with Stack

Watch how the expression "3 4 + 2 * 7 /" is evaluated using a stack:

Expression: 3 4 + 2 * 7 /

Step-by-step evaluation:

Read 3 → Push to stack[3]

Read 4 → Push to stack[3, 4]

Read + → Pop 4,3 → Push 3+4=7[7]

Read 2 → Push to stack[7, 2]

Read * → Pop 2,7 → Push 7*2=14[14]

Read 7 → Push to stack[14, 7]

Read / → Pop 7,14 → Push 14/7=2[2] ✓

Algorithm Steps:

If operand → push to stack

If operator → pop two operands

Apply operator → push result

Final result = top of stack

Why Use Postfix?

• No parentheses needed
• No operator precedence rules
• Perfect for stack evaluation
• Used in calculators & compilers

Bonus: Balanced Parentheses Checker

Stacks are perfect for checking if parentheses are balanced in expressions:

✓ (a + b) * (c - d)

✓ {[a + b] * c}

✗ (a + b * (c - d)

✗ )a + b(

Algorithm:

1. For opening brackets: push to stack

2. For closing brackets: pop and match

3. Stack empty at end = balanced ✓

Undo/Redo Operations

Text editors, image editors, and many applications use two stacks to implement undo and redo functionality. This allows users to reverse actions and then redo them if needed.

How It Works

Action Stack: Stores completed actions

Undo: Pop from action stack, push to redo stack

Redo: Pop from redo stack, push to action stack

New Action: Clear redo stack, push to action stack

Real-World Examples

Text Editors:

• Type text → push to stack

• Ctrl+Z → undo last action

• Ctrl+Y → redo action

Image Editors:

• Apply filter → push to stack

• Undo → revert filter

• Redo → reapply filter

Interactive Example

Typing "HELLO" in a text editor:

After typing "HELLO":

Action Stack:

Type 'O'

Type 'L'

Type 'E'

Type 'H'

Redo Stack:

(empty)

After 2 undos (text: "HEL"):

Action Stack:

Type 'L'

Type 'E'

Type 'H'

Redo Stack:

Type 'O'

Type 'L'

Now you can redo to get back "HELLO" or continue editing to clear the redo stack.

Browser History Navigation

Web browsers use stacks to manage page history. When you click "Back", you're essentially popping from a history stack. When you visit a new page, it's pushed onto the stack.

Browser Navigation Logic

Visit new page: Push to history stack

Back button: Pop from history stack

Forward button: Use forward stack

New page from back: Clear forward stack

Other Stack Applications

Memory Management: Stack memory for local variables

Syntax Parsing: Compilers use stacks for parsing code

Backtracking: AI algorithms use stacks to backtrack

Depth-First Search: Graph traversal algorithms

Browser History Simulation

Navigation sequence:

1. Visit google.com

History: [google.com]

2. Click link → facebook.com

History: [google.com, facebook.com]

3. Navigate to twitter.com

History: [google.com, facebook.com, twitter.com]

4. Press Back button

Pop twitter.com → Now at facebook.com
History: [google.com, facebook.com]
Forward: [twitter.com]

5. Press Forward button

Back to twitter.com
History: [google.com, facebook.com, twitter.com]

Note: If you visit a new page while having forward history, the forward stack gets cleared (you can't go forward to the old pages anymore).

Stack Applications Summary

Key Applications:

Function call management

Expression evaluation (postfix, infix)

Undo/Redo operations

Browser history navigation

Syntax checking & parsing

Why Stacks Are Perfect:

• LIFO nature matches natural undo/redo behavior

• O(1) operations for push/pop make them efficient

• Simple implementation with arrays or linked lists

• Memory efficient for recursive function calls

• Natural fit for nested structures (parentheses, HTML tags)

Previous: Stack Operations Next: Queue Fundamentals