Trace Array Implementation
Think about an array-based implementation of Stack such that the core operations are constant time.
Exercise Complete the table below: update the array values at indices 0, 1, 2, 3, and 4 as you trace the operations; show value returned if any.
| Operation | [ 0 ] | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | Return Value |
|---|---|---|---|---|---|---|
push(6) | ||||||
push(10) | ||||||
push(2) | ||||||
top() | ||||||
pop() | ||||||
push(15) | ||||||
pop() | ||||||
pop() | ||||||
push(5) | ||||||
top() |
Solution
| Operation | [ 0 ] | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | Return Value |
|---|---|---|---|---|---|---|
push(6) | 6 | |||||
push(10) | 6 | 10 | ||||
push(2) | 6 | 10 | 2 | |||
top() | 6 | 10 | 2 | 2 | ||
pop() | 6 | 10 | ||||
push(15) | 6 | 10 | 15 | |||
pop() | 6 | 10 | ||||
pop() | 6 | |||||
push(5) | 6 | 5 | ||||
top() | 6 | 5 | 5 |
Resources
- USFCA interactive demo of Stack (Array Implementation).