Trace Array 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()`

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

Resources

USFCA interactive demo of Queue (Array Implementation)