Queues - List vs Double List Implementation

Queues Implemented with Lists

• Enqueue: Add elements to the end of the list ($O(n)$).
• Dequeue: Remove elements from the front ($O(1)$).

Queues Implemented with Double Lists

• Uses two lists: ins (where new elements are added) and outs (where elements are taken from).
• Enqueue: New elements are added to the front of the ins list in constant time ($O(1)$).
• Dequeue: Elements are removed from the front of the outs list.
• If outs is empty, the ins list is reversed and becomes the new outs list.

Time Complexity

• Enqueue (inserting 100 elements): 100 units of work.
• Transferring to the outs list: 100 units of work.
• Dequeue (removing elements): 100 units of work.
• Total: 300 units of work (3 units per item). The cost (time complexity) scales linearly.

Queue Operations

• empty: Creates an empty queue.
• enqueue: Adds an element to the queue.
• dequeue: Removes an element from the queue, returns Nothing if the queue is empty.
• isEmpty: Checks if the queue is empty.

Testing Queue Performance

• QueueOp data type: Represents operations on a queue (enqueue, dequeue, dequeue all).
• doOps function: Executes a list of queue operations using a fold function.

Performance Comparison

• List implementation scales quadratically and is slow.
• Two-list implementation scales linearly and is much faster.

Scaling Considerations

• The list implementation's append operation ($++$) has linear time complexity ($O(n)$).
• The cost of enqueuing $n$ elements is the triangular number for $n$, which is $n * (n + 1) / 2$.

Stacks vs. Queues

• Stacks and queues can be compared using a tree traversal example.
• The order in which elements are accessed differs between stacks and queues.
• This affects execution time/order.

Usage Patterns

• Need to test under different usage patterns, not just scale.