DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Complete implementations of stacks in three ways — dynamic array (Python list), fixed-size array, and singly linked list. Each implementation handles all edge cases with error checking, includes performance analysis, and discusses when to choose each approach.
Implementation 1 — Dynamic Array Stack
The most practical implementation for most use cases.
Example
class DynamicArrayStack:
"""
Stack implemented with Python list.
list.append() and list.pop() are both O(1) amortized.
"""
def __init__(self):
self._items = []
def push(self, item) -> None:
self._items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Stack underflow: pop from empty stack")
return self._items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack underflow: peek at empty stack")
return self._items[-1]
def is_empty(self) -> bool:
return len(self._items) == 0
def size(self) -> int:
return len(self._items)
def clear(self) -> None:
self._items.clear()
def __len__(self) -> int:
return len(self._items)
def __contains__(self, item) -> bool:
return item in self._items # O(n) search
def __iter__(self):
"""Iterate from top to bottom."""
return reversed(self._items)
def __repr__(self) -> str:
if not self._items:
return "Stack(empty)"
items = list(reversed(self._items))
return "Stack(top→bottom): " + " → ".join(map(str, items))
Implementation 3 — Linked List Stack
When you need guaranteed O(1) (not just amortized) for every push and pop.
python example
class _Node:
__slots__ = ('data', 'next') # Memory optimization
def __init__(self, data):
self.data = data
self.next = None
class LinkedListStack:
"""
Stack using singly linked list.
head = top of stack → guaranteed O(1) push and pop (no amortized).
"""
def __init__(self):
self._top = None # Linked list head
self._size = 0
def push(self, item) -> None:
"""O(1) guaranteed."""
node = _Node(item)
node.next = self._top
self._top = node
self._size += 1
def pop(self):
"""O(1) guaranteed."""
if self.is_empty():
raise IndexError("Stack underflow")
item = self._top.data
self._top = self._top.next
self._size -= 1
return item
def peek(self):
"""O(1) guaranteed."""
if self.is_empty():
raise IndexError("Stack underflow")
return self._top.data
def is_empty(self) -> bool:
return self._top is None
def size(self) -> int:
return self._size
def to_list(self) -> list:
"""Convert to list from top to bottom. O(n)."""
result = []
current = self._top
while current:
result.append(current.data)
current = current.next
return result
def __repr__(self) -> str:
if self.is_empty():
return "LinkedStack(empty)"
return "LinkedStack(top→bottom): " + " → ".join(map(str, self.to_list()))Comparison of Three Implementations
| Feature | Dynamic Array | Fixed Array | Linked List |
|---|---|---|---|
| Push | O(1) amortized | O(1) always | O(1) always |
| Pop | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) |
| Memory per element | ~8 bytes (8B ref) | ~8 bytes (pre-alloc) | ~24 bytes (data + ptr) |
| Max size | Unlimited (RAM) | Fixed at creation | Unlimited (RAM) |
| Overflow possible | No (until RAM full) | Yes (at capacity) | No |
| Cache performance | Excellent | Excellent | Poor |
| Memory wasted | Some (over-alloc) | Yes (pre-alloc) | None |
| Best for | General use | Known max size | Real-time systems |
Two Stacks in One Array
A classic interview problem: implement two stacks using a single array efficiently.
Example
class TwoStacksInArray:
"""
Two stacks sharing a single array.
Stack 1 grows from the left (index 0 forward).
Stack 2 grows from the right (index n-1 backward).
Total space used is minimized — neither stack wastes space.
"""
def __init__(self, capacity: int):
self._data = [None] * capacity
self._cap = capacity
self._top1 = -1 # Stack 1 top (grows right)
self._top2 = capacity # Stack 2 top (grows left)
def push1(self, item):
if self._top1 + 1 == self._top2:
raise OverflowError("Both stacks are full")
self._top1 += 1
self._data[self._top1] = item
def push2(self, item):
if self._top1 + 1 == self._top2:
raise OverflowError("Both stacks are full")
self._top2 -= 1
self._data[self._top2] = item
def pop1(self):
if self._top1 == -1:
raise IndexError("Stack 1 is empty")
item = self._data[self._top1]
self._top1 -= 1
return item
def pop2(self):
if self._top2 == self._cap:
raise IndexError("Stack 2 is empty")
item = self._data[self._top2]
self._top2 += 1
return item
def peek1(self):
if self._top1 == -1:
raise IndexError("Stack 1 is empty")
return self._data[self._top1]
def peek2(self):
if self._top2 == self._cap:
raise IndexError("Stack 2 is empty")
return self._data[self._top2]
Stack with Minimum Element — O(1)
Example
class MinStack:
"""
Stack that supports push, pop, peek, AND getMin() — all in O(1).
The trick: maintain a parallel 'min_stack' that tracks
the current minimum at every level.
"""
def __init__(self):
self._stack = []
self._min_stack = [] # Parallel stack tracking minimums
def push(self, val: int) -> None:
self._stack.append(val)
# Push current min onto min_stack
current_min = val if not self._min_stack else min(val, self._min_stack[-1])
self._min_stack.append(current_min)
def pop(self) -> int:
if not self._stack:
raise IndexError("pop from empty stack")
self._min_stack.pop()
return self._stack.pop()
def peek(self) -> int:
return self._stack[-1]
def get_min(self) -> int:
"""Return current minimum. O(1)."""
return self._min_stack[-1]
# Testing:
ms = MinStack()
ms.push(3); ms.push(5); ms.push(2); ms.push(1)
print(ms.get_min()) # 1
ms.pop()
print(ms.get_min()) # 2
ms.pop()
print(ms.get_min()) # 3
Java Stack Implementation
For completeness, the standard Java approach:
java example
// Using Java's built-in Deque as a stack (preferred over legacy Stack class)
import java.util.ArrayDeque;
import java.util.Deque;
Deque<Integer> stack = new ArrayDeque<>();
// Push
stack.push(1); // or stack.addFirst(1)
// Pop
int top = stack.pop(); // or stack.removeFirst()
// Peek
int peek = stack.peek(); // or stack.peekFirst()
// Check empty
boolean empty = stack.isEmpty();
// Size
int size = stack.size();
// Why Deque instead of Stack?
// Java's legacy Stack class is synchronized (thread-safe but slow).
// ArrayDeque is faster and is the modern standard for stacks in Java.Summary
Three implementations for different needs:
- Dynamic Array Stack (Python list): General-purpose, simplest code, excellent cache performance — use by default
- Fixed Array Stack: When maximum size is known and memory must be bounded — embedded systems, OS kernels
- Linked List Stack: When guaranteed O(1) (not amortized) is required — real-time systems
Special-purpose stacks:
- Two Stacks in One Array: Efficient space sharing when you need exactly two stacks
- Min Stack: Supports O(1) minimum query using a parallel min-tracking stack
*Next Lesson: Stack Using Arrays — Deep dive into array-backed stacks with memory layout, capacity management, and performance.*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Stack Implementation — Three Complete Implementations with Edge Cases.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, stacks, stack, implementation
Related Data Structures & Algorithms Topics
Continue learning this concept
StacksStack Interview Problems — 10 Classic Problems with Complete SolutionsSolve 10 classic stack interview problems with full solutions — valid parentheses, evaluate reverse polish notation, daily temperatures, next greater element, asteroid collision, largest rectangle in histogram, remove k digits, decode string, and more.StacksStack — Complete Introduction to LIFO Data StructureA thorough introduction to stacks — the LIFO (Last In, First Out) data structure. Learn the stack model, all operations with complexity, real-world applications, stack implementations using arrays and linked lists, and the fundamental programming constructs that depend on stacks.StacksStack Using Arrays — Memory Layout, Capacity Management, and PerformanceDeep dive into array-based stack implementation — internal memory layout, capacity management strategies, why arrays give better cache performance than linked lists, how to implement a stack with circular buffer optimization, and performance benchmarks.StacksStack Using Linked List — Implementation, Analysis, and When to Use ItComplete linked list stack implementation with all operations, memory analysis, comparison with array-based stack, understanding the true O(1) guarantee vs amortized O(1), and the practical scenarios where linked list stacks are preferred over array stacks.StacksBalanced Parentheses — Stack-Based Validation with All VariantsMaster the balanced parentheses problem — validating matching brackets using a stack, all variants (multiple bracket types, minimum additions to balance, longest valid substring), why stacks are the perfect data structure for bracket matching, and interview patterns.StacksInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationMaster expression notation conversion using stacks — infix to postfix (Shunting Yard algorithm), infix to prefix, postfix evaluation, prefix evaluation, why postfix and prefix are easier to evaluate than infix, operator precedence handling, and complete traced examples.