GeeksforGeeks Easy

Implement Stack using Arrays

Build a stack — push, pop, top, size — on a fixed array.

stackdesign

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).

How to spot this pattern

The foundational exercise: a stack is an array plus one index. Everything interesting is in the boundary conditions — top == -1 means empty, top == capacity - 1 means full. Getting those two right is the whole problem, and they're the same two checks every fixed-capacity structure needs.

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

▶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

Common pitfalls

Incrementing the index after writing

✗ Wrong

self.a[self.top] = x
self.top += 1

✓ Right

self.top += 1
self.a[self.top] = x

With top starting at −1 as the empty marker, writing first targets index −1, which in Python silently overwrites the last slot of the array. Advance to the new position, then write to it.

Checking overflow against the wrong bound

✗ Wrong

if self.top == len(self.a): raise OverflowError

✓ Right

if self.top == len(self.a) - 1: raise OverflowError

top is the index of the last stored item, so a full array has top == capacity - 1. Comparing against capacity lets one extra push run off the end.

Returning a value after decrementing

✗ Wrong

self.top -= 1
return self.a[self.top]

✓ Right

v = self.a[self.top]
self.top -= 1
return v

Decrementing first returns the element below the top — the one that should survive the pop. Read the value while the index still points at it.

06

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.

07

Complexity

Time

O(1) per op

Space

O(cap)

No shifting, ever.