Trace Array Implementation
- Trace the core operations of Queue (array-based implementation).
Think about an array-based implementation of queue 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 |
|---|---|---|---|---|---|---|
enqueue(1) | ||||||
enqueue(2) | ||||||
enqueue(3) | ||||||
dequeue() | ||||||
enqueue(4) | ||||||
dequeue() | ||||||
enqueue(5) | ||||||
front() | ||||||
dequeue() | ||||||
front() | ||||||
enqueue(6) |
Solution
| Operation | [ 0 ] | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | Return Value |
|---|---|---|---|---|---|---|
enqueue(1) | 1 | |||||
enqueue(2) | 1 | 2 | ||||
enqueue(3) | 1 | 2 | 3 | |||
dequeue() | 2 | 3 | ||||
enqueue(4) | 2 | 3 | 4 | |||
dequeue() | 3 | 4 | ||||
enqueue(5) | 3 | 4 | 5 | |||
front() | 3 | 4 | 5 | 3 | ||
dequeue() | 4 | 5 | ||||
front() | 4 | 5 | 4 | |||
enqueue(6) | 6 | 4 | 5 |
Resources
- USFCA interactive demo of Queue (Array Implementation)