How it works
Both can be built on arrays or linked nodes. An array-backed queue needs circular indexing to avoid shifting every element on removal.
Wrap indices with modular arithmetic so vacated front slots are reused.
Common error
A naive array queue that shifts on every dequeue, turning a constant-time operation linear.
Worked example
Example
Array-backed stack: end insertion/removal
Linked queue with head and tail: endpoint updates
Array front removal with shifting: linear work
ArrayDeque: circular-array dequeAn abstract data type states behavior; an implementation determines operation costs. A queue need not shift an entire array on every removal: a circular buffer can advance a front index.
Exercises
4.3.1 · Explain
Why is repeatedly removing index 0 from an ArrayList a poor queue implementation for large inputs?
Show solution
Each removal shifts later elements left, taking linear time in the current list size. A suitable deque avoids that repeated shifting.
4.3.2 · Explain
What additional reference makes appending to a singly linked queue constant-time?
Show solution
A maintained tail reference identifies the last node without scanning from the head. Empty-list insertion must update both head and tail.