Reverse an array with a stack
Updated
Push every array element left to right, then pop until empty. The pop sequence is the reversed array. The stack is extra memory. The input array is not mutated unless you write the pops back.
What to focus on
For a = [4, 1, 9], pushes leave [4, 1, 9], pops yield 9,1,4. One-item reverse is identity. This is O(n) time and O(n) extra.
Worked examples
three
a = [4, 1, 9]- push 4,1,9
- pop 9,1,4
Result: [9, 1, 4]
one
a = [7]- push 7
- pop 7
Result: [7]
palindrome-ish
a = [1, 2, 1]- push 1,2,1
- pop 1,2,1
Result: [1, 2, 1]
Try it
Write reverseWithStack(a). a is an array of integers. Push every element left to right, then pop until empty. Return the pop sequence. Do not copy by peeking in order. Reverse [4, 1, 9] to [9, 1, 4]. [7] to [7]. [1, 2, 1] to itself.
a is a list of integers. Length is at least 1.