B2.2.3 Explain the concept of a stack as a “last in, first out” (LIFO) data structure.

The Big Idea

A stack is a fundamental abstract data type (ADT) based on the Last In, First Out (LIFO) principle. This means that the last item added to the stack is the first one to be removed, much like a stack of plates or a web browser’s back button history. You can only access the top item directly.

Stacks are used in a wide range of programming scenarios: function calls, undo/redo operations, syntax parsing, and backtracking algorithms all rely on stacks because of their simple yet powerful LIFO structure.

---

1. Key Concepts and Operations

A stack typically supports the following four core operations:

Operation	Description	Example
push(item)	Adds an item to the top of the stack	Pushing 5 places it above existing items
pop()	Removes and returns the item at the top	Removes 5 if it was the last pushed item
peek() or top()	Returns (but does not remove) the top item	See what’s on top without changing the stack
isEmpty()	Returns true if the stack has no items	Used to prevent underflow (popping from an empty stack)

---

2. Stack Behavior (LIFO in Action)

Imagine the following sequence of operations:

Stack = []
push(10)
push(20)
push(30)

Now the stack looks like this (top is on the right):

[10, 20, 30]

• pop() → removes 30
• peek() → returns 20 (but does not remove it)
• isEmpty() → returns False

---

3. Implementation: Arrays vs Linked Structures

Stacks can be implemented using:

• Arrays (fixed or dynamic like Python lists or Java ArrayList)
• Linked lists (each node points to the next)

Example in Python (using built-in list):

stack = []
stack.append(1)       # push
stack.append(2)
print(stack.pop())    # pop → 2
print(stack[-1])      # peek → 1
print(len(stack) == 0) # isEmpty

Example in Java (using Stack<T> from java.util):

import java.util.Stack;
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
System.out.println(stack.pop());    // 20
System.out.println(stack.peek());   // 10
System.out.println(stack.isEmpty()); // false

---

4. Performance and Memory Considerations

Time Complexity (Big-O):

Operation	Time Complexity
push	O(1)
pop	O(1)
peek	O(1)
isEmpty	O(1)

• All fundamental stack operations run in constant time, regardless of the number of elements.
• Stacks are very efficient for managing short-term memory needs.

Memory Considerations:

• Array-based stacks may waste memory if over-allocated or may need to reallocate if resized.
• Linked list stacks use extra memory per element to store pointers (next reference), increasing overhead but allowing more flexible growth.

---

5. Real-World Use Case

Problem: Evaluating a Postfix Expression (Reverse Polish Notation)

Postfix expressions like "5 1 2 + 4 * + 3 -" can be evaluated using a stack:

1. Traverse tokens left to right.
2. If token is a number, push it onto the stack.
3. If token is an operator, pop two numbers, apply the operator, and push the result.
4. At the end, the stack will contain the final result.

Why a stack?
Because the last two numbers encountered are the ones to be operated on next—this is naturally modeled by the LIFO rule.

---

Other Use Cases

Use Case	Why Stack Works
Function calls (call stack)	When a function calls another, the previous state must be saved.
Undo/redo systems	The most recent action is the first to be reversed.
Syntax parsing (e.g. parentheses matching)	Last opened parenthesis must be closed first.
Backtracking algorithms (e.g. DFS)	The most recent path is explored first.

---

6. Stack Underflow and Overflow

• Underflow: Trying to pop() from an empty stack.
• Overflow: In fixed-size implementations, pushing more items than space allows (e.g., array-based stacks with no resizing).

Most high-level languages with dynamic memory (like Python, Java) manage this automatically, but lower-level languages like C require manual checks.

---

Summary

Feature	Stack (LIFO)
Access Pattern	Last-In, First-Out
Fundamental Ops	push, pop, peek, isEmpty
Time Complexity	All O(1) operations
Common Implementations	Arrays, Linked Lists
Typical Uses	Function calls, undo systems, parsing, DFS
Memory Impact	Efficient but depends on underlying storage

---

Final Thoughts

The stack is deceptively simple but extremely powerful. By adhering to a strict LIFO discipline, it provides an elegant solution to many common computational problems, especially those that involve reversing, tracking state, or managing recursive flows. Understanding stacks is not just about learning how to push and pop—but about recognizing when and why this controlled access pattern provides the most appropriate and efficient way to handle data.