Two Queues, Side by Side

We now have two implementations of the Queue contract, so we can put the costs side by side:

Operation	`LinkedQueue`	`ArrayQueue`
`enqueue`	$O (1)$	$O (1)$ amortized
`dequeue`	$O (1)$	$O (1)$
`front`	$O (1)$	$O (1)$
`isEmpty`	$O (1)$	$O (1)$

The table looks just like the one for the two stacks, and for most programs the amortized enqueue does not matter.

The memory trade-off is also the same one we saw with the two stacks.

The lesson about small interfaces still holds, with one adjustment. Restricting access makes an efficient implementation possible, but it does not guarantee one. The circular array works because a queue only uses its two ends, so the items can be stored anywhere in the array as long as we keep track of front and size.

So which one should you use? Either one works. Remember a client should program to the interface, declaring Queue<T> without caring which class is behind it.