🧩 What is a Stack?
A stack is a fundamental linear data structure that follows the principle of LIFO (Last In, First Out). This means that the last element added to the stack is the first one to be removed.
Think of a stack like a pile of plates:
- You add plates to the top.
- You remove plates from the top.
- The last plate placed is the first one taken off.
In technical terms, a stack supports a restricted set of operations, primarily:
- Push → Add an element to the stack
- Pop → Remove the top element
- Peek/Top → View the top element without removing it
🧠 Key Characteristics of Stacks
🔹 1. LIFO Principle
The most defining property of a stack is the Last In, First Out rule.
🔹 2. Restricted Access
Elements can only be accessed from one end called the top.
🔹 3. Dynamic or Static Implementation
Stacks can be implemented using:
- Arrays (fixed size)
- Linked lists (dynamic size)
🔹 4. Efficient Operations
Most stack operations run in O(1) time complexity.
🧱 Basic Structure of a Stack
A stack consists of:
- Top pointer → indicates the current top element
- Elements → stored in a linear order
⚙️ Core Stack Operations
🔹 1. Push Operation
Adds an element to the top of the stack.
stack.append(10)
🔹 2. Pop Operation
Removes the top element.
stack.pop()
🔹 3. Peek (Top)
stack[-1]
Returns the top element without removing it.
🔹 4. isEmpty Operation
len(stack) == 0
Checks whether the stack is empty.
🔹 5. isFull Operation (Array-based stack)
Checks if the stack has reached its maximum capacity.
🧮 Types of Stacks
🔹 1. Simple Stack
Basic implementation following LIFO.
🔹 2. Dynamic Stack
Implemented using linked lists; size can grow dynamically.
🔹 3. Fixed Stack
Implemented using arrays with fixed capacity.
🔹 4. Multiple Stacks
More than one stack in a single array.
⚠️ Stack Conditions
🔴 Stack Overflow
Occurs when trying to push into a full stack.
🔵 Stack Underflow
Occurs when trying to pop from an empty stack.
🧑💻 Stack Implementation
🔹 1. Using Arrays
class Stack:
def __init__(self):
self.stack = []
def push(self, data):
self.stack.append(data)
def pop(self):
if self.is_empty():
return "Underflow"
return self.stack.pop()
def peek(self):
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
🔹 2. Using Linked Lists
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.top is None:
return "Underflow"
temp = self.top
self.top = self.top.next
return temp.data
🧮 Time Complexity of Stack Operations
| Operation | Time Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| Search | O(n) |
⚡ Advantages of Stacks
- Simple and easy to implement
- Efficient operations (constant time)
- Useful for recursion and backtracking
- Memory-efficient (linked list implementation)
⚠️ Disadvantages of Stacks
- Limited access (only top element)
- Not suitable for random access
- Overflow/underflow issues
🧠 Advanced Stack Concepts
🔹 1. Expression Evaluation
Stacks are used to evaluate expressions:
- Infix → Postfix
- Postfix → Evaluation
🔹 2. Recursion and Call Stack
Every recursive call uses the call stack.
🔹 3. Backtracking Algorithms
Used in:
- Maze solving
- DFS traversal
🔹 4. Monotonic Stack
Used in advanced problems like:
- Next Greater Element
- Histogram problems
🔬 Applications of Stacks
📱 1. Undo/Redo Operations
Used in editors like Word, Photoshop.
🌐 2. Browser History
Back button uses stack behavior.
🧾 3. Syntax Parsing
Used in compilers to check correctness.
🎮 4. Game Development
Managing game states and moves.
🧮 5. Depth First Search (DFS)
Used in graph traversal.
🔁 Stack vs Queue
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO | FIFO |
| Insertion | Top | Rear |
| Deletion | Top | Front |
🧪 Memory Representation
Array-Based:
[10, 20, 30]
↑
Top
Linked List-Based:
Top → [30] → [20] → [10]
🚀 Real-World Importance
Stacks are essential in:
- Programming languages (function calls)
- Operating systems
- Compilers and interpreters
- Artificial intelligence algorithms
- Data processing systems
🧾 Conclusion
Stacks are one of the simplest yet most powerful data structures in computer science. Their LIFO nature makes them indispensable in many applications, from basic algorithms to complex system-level operations.
Understanding stacks thoroughly is crucial for mastering algorithms, recursion, and system design.