🧱 Data Structures & Logic Gates
Stack, queue, sorting algorithms, logic gates.
🧱 Building Blocks of Computing
Data Structures organize data for efficient access and modification. Choosing the right structure is key to writing efficient programs.
Linear structures (sequential):
• Array — fixed-size, same-type elements. Index-based. O(1) access. O(n) search.
• Linked List — nodes with data + pointer to next. Dynamic size. O(n) access. Efficient insert/delete.
• Stack — LIFO (Last In First Out). Push (add) and Pop (remove) from top. Used in: undo/redo, recursion, browser back button.
• Queue — FIFO (First In First Out). Enqueue (add) at rear, Dequeue (remove) from front. Used in: print queue, task scheduling, BFS.
Non-linear structures:
• Tree — hierarchical. Binary tree: max 2 children. BST (Binary Search Tree): left < root < right. Used in file systems, databases.
• Graph — vertices connected by edges. Directed/Undirected, Weighted. Used in maps, social networks.
Bubble Sort — compare adjacent, swap if wrong order. O(n²). Simple but slow.
Selection Sort — find minimum, place at beginning. O(n²).
Insertion Sort — insert each element into sorted portion. O(n²). Good for nearly sorted.
Merge Sort — divide and conquer. O(n log n). Stable.
Quick Sort — pivot-based. O(n log n) average, O(n²) worst. Fastest in practice.
Binary Search — on sorted array. O(log n). Linear Search O(n).
AND gate — output 1 only if ALL inputs are 1. Symbol: D-shape.
OR gate — output 1 if ANY input is 1.
NOT gate (Inverter) — flips input. 0→1, 1→0.
NAND gate — NOT AND. Universal gate — any circuit can be built with only NAND gates.
NOR gate — NOT OR. Also universal gate.
XOR gate — output 1 if inputs are DIFFERENT.
XNOR gate — output 1 if inputs are SAME.
Boolean algebra: A·B (AND), A+B (OR), A' or ¬A (NOT)
Stack vs Queue — Visualized
AnimationStack and Queue are used in almost every program. Logic gates are the physical circuits that execute binary operations.
Data Structures & Algorithms Explorer
InteractiveExample: Sort [5, 3, 8, 1, 4]
Pass 1:
[5,3,8,1,4] → compare 5,3 → swap → [3,5,8,1,4]
[3,5,8,1,4] → compare 5,8 → no swap
[3,5,8,1,4] → compare 8,1 → swap → [3,5,1,8,4]
[3,5,1,8,4] → compare 8,4 → swap → [3,5,1,4,8] ✓ 8 is in place
Pass 2:
[3,5,1,4,8] → [3,1,4,5,8] ✓ 5 is in place
Pass 3:
[3,1,4,5,8] → [1,3,4,5,8] ✓ 4 is in place
Final: [1,3,4,5,8] — sorted!
Time complexity: O(n²) — n-1 passes, each up to n-1 comparisons
Space complexity: O(1) — in-place sorting
Stable sort: Yes — equal elements maintain relative order
Best case (already sorted): O(n) with optimization flag
Worst case: O(n²)
• Last element added is the first to be removed
• Operations: PUSH (add to top), POP (remove from top), PEEK (view top)
• Like a stack of plates — you add and remove from the top
Real-life examples:
• Ctrl+Z (Undo) — last action is undone first
• Browser Back button — last page visited is first to go back
• Function call stack — last function called returns first (recursion)
• Expression evaluation — bracket matching
Queue — FIFO (First In, First Out):
• First element added is the first to be removed
• Operations: ENQUEUE (add to rear), DEQUEUE (remove from front)
• Like a ticket queue — first person in line is first served
Real-life examples:
• Print queue — documents print in order received
• CPU scheduling (Round Robin) — processes wait in queue
• Keyboard buffer — keystrokes processed in order typed
• WhatsApp message queue — messages delivered in order
• BFS (Breadth First Search) in graphs uses a queue
Key difference: Stack = LIFO (recent items first), Queue = FIFO (older items first)