Stack — LIFO semantics, push - pop - peek, array and linked list implementations
WHY does a stack exist?
WHAT is a stack? (precise definition)
HOW to implement it — Implementation 1: Array
Derivation of the index logic from scratch.
Start with an empty stack. There is no element, so the natural sentinel is top = -1 (one below index 0).
- To push: we want the new element to live at the next free index, which is
top + 1. So: increment first, then store. - To pop: the top element is at
arr[top]. Read it, then movetopback down so that slot is "forgotten". - isEmpty: empty exactly when
top == -1. - isFull (fixed array of size
n): full whentop == n-1.
class ArrayStack:
def __init__(self, capacity):
self.arr = [None] * capacity
self.cap = capacity
self.top = -1 # WHY -1: empty sentinel, one below index 0
def is_empty(self): return self.top == -1
def is_full(self): return self.top == self.cap - 1
def push(self, x):
if self.is_full(): raise OverflowError("stack full")
self.top += 1 # WHY first: next free slot is top+1
self.arr[self.top] = x
def pop(self):
if self.is_empty(): raise IndexError("pop from empty")
x = self.arr[self.top] # WHY read first: top still points to it
self.arr[self.top] = None # optional: help garbage collection
self.top -= 1 # WHY: forget that slot
return x
def peek(self):
if self.is_empty(): raise IndexError("peek from empty")
return self.arr[self.top] # WHY no decrement: peek must NOT removeHOW — Implementation 2: Linked List
Derivation from scratch. A node holds (data, next). The stack stores only a pointer head.
- push(x): create a node whose
nextpoints to the current head, then make it the new head. (WHY this order: if you overwriteheadfirst you lose the old list.) - pop(): the top is
head.data. Read it, then advanceheadtohead.next. - isEmpty:
head is None.
class Node:
def __init__(self, data, nxt=None):
self.data = data
self.next = nxt
class LinkedStack:
def __init__(self):
self.head = None # head == top
self.size = 0
def is_empty(self): return self.head is None
def push(self, x):
self.head = Node(x, self.head) # WHY: new node points to old top, becomes top
self.size += 1
def pop(self):
if self.is_empty(): raise IndexError("pop from empty")
x = self.head.data
self.head = self.head.next # WHY: old head is now unreferenced -> freed
self.size -= 1
return x
def peek(self):
if self.is_empty(): raise IndexError("peek from empty")
return self.head.dataWorked examples
Common mistakes (Steel-man + fix)
Recall Feynman: explain to a 12-year-old
Imagine a tube of Pringles. You can only take the top chip, and when you add a chip it goes on top too. The chip you ate last is the one you just put in. That's a stack. "Push" = drop a chip in, "pop" = eat the top chip, "peek" = look at the top chip without eating it. Computers use this to remember "what was I doing before I got interrupted?" — they finish the newest job first, then go back.
Active recall
What does LIFO stand for and what does it mean?
What are the four core stack operations?
Why does an array stack initialize top = -1?
In array push, what is the correct order of the two steps?
top += 1), then store arr[top] = x.In array pop, why must you read before decrementing?
Difference between pop and peek?
In linked-list push, what is the safe order of operations?
Why is the head of a linked list used as the stack top?
Time complexity of push/pop/peek for both array and linked-list stacks?
One advantage of array stack and one of linked-list stack?
Why use a stack (not a counter) to validate nested brackets like ([)]?
How do you reverse a sequence with a stack?
Connections
- Queue — FIFO semantics — opposite ordering (First-In-First-Out).
- Linked List — singly linked — the backbone of the linked-list stack.
- Dynamic Array / Amortized Analysis — why Python
listpush is amortized . - Recursion and the Call Stack — the system uses a stack to manage function calls.
- Expression Evaluation — infix to postfix — stacks power operator-precedence parsing.
- Depth-First Search — DFS = graph traversal driven by a stack (explicit or recursive).
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Stack ek aisi data structure hai jaha sirf ek hi end se kaam hota hai — usko hum top bolte hain. Soch lo Pringles ka tube ya plates ki dher: jo chip ya plate sabse last me rakhi, wahi sabse pehle nikalti hai. Isi ko LIFO (Last-In First-Out) kehte hain. Bas char operations yaad rakho: push (top pe element daalo), pop (top wala element nikaalo aur return karo), peek (top wala dekho but nikaalo mat), aur isEmpty.
Array implementation me ek variable top rakhte hain jo last filled index batata hai. Empty stack me top = -1 (kyunki index 0 se neeche). Push me pehle top += 1 phir arr[top] = x. Pop me pehle padho arr[top], phir top -= 1 — order ulta kiya to galat value milegi, yahi sabse common galti hai. Linked-list version me head ko hi top maan lo: push me naye node ka next purane head pe lagao, phir head ko naya node bana do. Important: pehle next set karo, baad me head badlo, warna list khoo jaayegi ya self-loop ban jaayega.
Dono me push/pop/peek O(1) hote hain. Array fast aur cache-friendly hai par capacity fixed hoti hai (overflow ho sakta hai); linked list unbounded hai par har node me ek extra pointer ka memory lagta hai. Real life me stack bahut kaam aata hai: function call stack, undo button, aur brackets ([{}]) ka matching. Bracket check ke liye counter kaafi nahi — kyunki humein yaad rakhna padta hai ki kaunsa bracket open hua tha, aur wahi LIFO order stack deta hai. Yaad rakho: "Last to arrive, first to leave."