Implement Stack using Arrays
Build a stack — push, pop, top, size — on a fixed array.
02
Intuition
A stack is just an array plus one integer: top, the index of the last element. Push writes at top+1; pop reads at top and steps back. Nothing ever moves — that's why every operation is O(1).
03
Approach
1
One pointer does everything
top = -1 means empty. push: top += 1; a[top] = x. pop: read a[top], top -= 1.
2
Guard the edges
Pop/peek on empty (top == −1) is underflow; push on a full fixed array (top == cap−1) is overflow — check both.
3
Dynamic variant
Doubling the array on overflow gives amortized O(1) push — that's exactly what Python's list.append does.
04
Solution & live demo
python
▶1class Stack:
▶2 def __init__(self, cap):
▶3 self.a = [0] * cap
▶4 self.top = -1
▶5
▶6 def push(self, x):
▶7 if self.top == len(self.a) - 1: raise OverflowError
▶8 self.top += 1
▶9 self.a[self.top] = x
▶10
▶11 def pop(self):
▶12 if self.top == -1: raise IndexError("empty")
▶13 v = self.a[self.top]
▶14 self.top -= 1
▶15 return v
▶16
▶17 def peek(self):
▶18 return self.a[self.top] if self.top >= 0 else None
05
Edge cases
Pop from empty stack
Explicit underflow check; raise or return sentinel.
Interleaved push/pop at capacity
top bounces at the boundary; indices never leak past it.
06
Complexity
Time
O(1) per op
Space
O(cap)
No shifting, ever.