Implementing a queue with a doubly linked list is straightforward and efficient. The core queue operations (enqueue
, dequeue
, isEmpty
, and peek
) can all be implemented by directly calling list operations that run in constant time. The only other major operation is the toString
operation, which is also implemented by directly calling the list toString
operation; however, it runs in order $N$ time due to the fact that the list toString
operation must iterate through each item in the list.
The key queue operations and their list-based implementations are shown below.
Operation | Implementation |
---|---|
enqueue |
|
dequeue |
|
isEmpty |
|
peek |
|
toString |
|