List-Based Queues

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.

function enqueue (data)
    list.append(data)
end function

function dequeue() returns data
    return removeFirst()
end function

function isEmpty() returns Boolean
    return list.isEmpty()
end function

function peek() returns data
    return list.peek()
end function

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.