Queues
| Operation | Time | Space | Description |
|---|---|---|---|
| empty() | O(1) | O(1) | Create an empty queue. |
| enqueue(q, e) | O(1) | O(1) | Append e into queue q. |
| dequeue(q) | O(1) | O(1) | Remove and return the earliest element from q. |
| is_empty(q) | O(1) | O(1) | Return whether or not q is an empty queue. |
Array-based queues #
We can maintain a queue using an array, two indices first and last into the array, and an integer len to store the number of elements in the queue. When the queue is non-empty, first and last are indices of the first and last elements in the queue. When the queue is empty, len will be 0 and the values of first and last should be the same.