List-Based Queues

YouTube Video

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
function enqueue (data)
list.append(data)
end function
dequeue
function dequeue() returns data
return removeFirst()
end function
isEmpty
function isEmpty() returns Boolean
return list.isEmpty()
end function
peek
function peek() returns data
return list.peek()
end function
toString
function toString() returns data
return list.toString()
end function

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.