Stack Implementation using Arrays

The problem. Build a stack on top of a plain array. Support push(x), pop() (return the removed value, or -1 if the stack is empty), top() (return the top value, or -1 if empty), isEmpty() and size().

An array of capacity 6 holding 5, 8 and 3 in slots 0 to 2. A variable n equals 3: it counts the items and is also the index of the next free slot. The top of the stack is data[n - 1], which is 3.

Example

push(10)   push(20)   top()  -> 20
pop()      -> 20       pop()  -> 10
pop()      -> -1  (empty)       isEmpty() -> true

The whole question is which end of the array is the top. Pick the wrong end and every operation moves every element.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 5 more sections, 3 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: the top at index 0
2. Optimal: the top at the end, with a fixed capacity
3. Best solution: a growing array (doubling)
Comparing the three approaches
Edge cases to test

Prev Next

Mark completed

Was this helpful?

QueueFirst-in, first-out — the structure behind task scheduling and breadth-first traversal.4 lessons · 5 problems
Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems
ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems

Stack Implementation using Arrays

Example

Keep reading. It's free.

Keep exploring