Stack Theory: LIFO Principle

Welcome to the world of Abstract Data Types (ADTs)! Our first stop is the Stack, a fundamental ADT with widespread applications in computer science. At its core, a stack operates on a simple yet powerful principle: Last In, First Out (LIFO).

1. The LIFO Principle

Imagine a stack of plates in a cafeteria. When you add a new plate, you place it on top of the existing stack. When you want to take a plate, you naturally take the one from the top. The plate that was last added is the first one to be removed. This is precisely how a stack data structure behaves.

Concept: Elements are added and removed from the same end, conventionally called the "top" of the stack.
Analogy:
- A stack of physical objects (plates, books, trays).
- A pile of clothes in your laundry basket (you usually grab the most recently added item from the top).
- The "undo" functionality in text editors (the last action performed is the first one undone).

2. Core Stack Operations

Stacks are defined by a specific set of operations that manipulate their elements. While the exact naming might vary, the conceptual operations remain consistent.

2.1. Push: `.push(element)`

Adds a new element to the top of the stack.

Concept:
1. Place the element on top of the current stack.
2. Increment the stack's size.
Time Complexity: O(1) (typically constant time, as you're always operating on one end).
Space Complexity: O(1) (for the new element).

2.2. Pop: `.pop()`

Removes and returns the element from the top of the stack.

Concept:
1. Check if the stack is empty. If so, indicate an error (or return null/undefined).
2. Remove the element currently at the top.
3. Decrement the stack's size.
4. Return the removed element.
Time Complexity: O(1) (constant time, as you're always operating on one end).
Space Complexity: O(1)

2.3. Peek (or Top): `.peek()`

Returns the element at the top of the stack without removing it.

Concept:
1. Check if the stack is empty. If so, indicate an error.
2. Return the element currently at the top.
Time Complexity: O(1)
Space Complexity: O(1)

2.4. IsEmpty: `.isEmpty()`

Checks if the stack contains any elements.

Concept:
1. Return true if the stack's size is zero; otherwise, return false.
Time Complexity: O(1)
Space Complexity: O(1)

2.5. Size: `.size()`

Returns the number of elements currently in the stack.

Concept:
1. Return the current count of elements in the stack.
Time Complexity: O(1)
Space Complexity: O(1)

Key Takeaway: The LIFO principle is the defining characteristic of a stack. All fundamental operations revolve around adding to and removing from a single point—the "top" of the stack—ensuring efficient O(1) time complexity for these core actions.