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 |
|
Stacks can be implemented using a similar method - namely adding and removing from the end of the list. This can even be done using a singly-linked list, and is very efficient.