Explain the concept of a stack as a "last in, first out" (LIFO) data structure

LIFO — Last In, First Out

A stack is a linear data structure where elements are added and removed from the same end, called the top. The last element pushed onto the stack is the first one to be popped off — like a pile of plates.

Core Operations

Operation	Action	Stack Pointer (SP)
push	Store data onto the top of the stack	SP increases by 1
pop	Retrieve and remove data from the top	SP decreases by 1
isEmpty()	Check whether the stack contains data, returning True or False
peek	Allows you to view the data at the top of the stack without removing the data

Stack Pointer (SP)

The Stack Pointer (SP) is a register that always points to the top of the stack — the most recently pushed item. Every PUSH increments SP; every POP decrements it.

Error Conditions

Condition	Meaning
Stack Overflow	Stack grows beyond its allocated memory — usually from excessive PUSH without POP, means keep PUSHING into a full stack
Stack Underflow	Attempting to POP from an empty stack

Memory Layout — Stack, Heap & Code

In a program’s memory:

┌─────────────────┐  ← High address
│  Code / Text    │  Instructions
├─────────────────┤
│ Static / Global │  Global variables
├─────────────────┤
│    Heap         │  Dynamically allocated (grows downward)
│       ↕         │
│   Unallocated   │
│       ↕         │
│    Stack        │  Stack frames (grows upward)
│   (SP → top)    │  ← Stack Pointer
└─────────────────┘  ← Low address

Stack Frames

When a function is called, a stack frame (also called an activation record) is pushed onto the call stack:

┌─────────────────────┐
│  Function2 Frame    │ ← Top (SP)
│  - Local variables  │
│  - Arguments        │
│  - Return address   │
├─────────────────────┤
│  Function1 Frame    │
│  - Local variables  │
│  - Arguments        │
│  - Return address   │
├─────────────────────┤
│  Main Frame         │ ← Bottom
└─────────────────────┘

Each frame contains:

• Local variables declared within the function
• Arguments passed to the function
• Return address — where execution should resume after the function returns

When the function finishes, its frame is popped and control returns to the previous frame.

Implementation in Python

stack = []

# PUSH
stack.append(1)   # stack = [1]
stack.append(2)   # stack = [1, 2]
stack.append(3)   # stack = [1, 2, 3]
stack.append(4)   # stack = [1, 2, 3, 4]

# POP
stack.pop()       # returns 4 — last in, first out
stack.pop()       # returns 3

---

Applications of Stacks

Application	How it uses a stack
Undo/Redo in text editors	Each action is PUSHed; undo POPs the last action
Backtracking in algorithms	DFS uses a stack to track visited paths and backtrack
Balancing symbols	Compilers PUSH opening brackets and POP on closing ones to check balance
Function call management	Call stack tracks active functions via stack frames
Expression evaluation	Shunting-yard algorithm uses stacks for infix → postfix conversion
Browser back button	URLs are PUSHed; back button POPs the history
Reversing a string	The characters in the string can be PUSHed separately into the stack. POPing them reverses the order of the string.