Queues
- Tags
- comp-sci
Is a data structure where elements are queued one behind the other and you only ever have access to the element at the very beginning of the queue. Adding new elements only pushes them to the back of the queue. Think of a [see page 7, stack] as a line of people with a last in, last out policy.
Table 1:
see page 8, [Operations] on queues.
| Method | Description |
|---|---|
Enqueue(Q,x) | Push element x to the tail of the queue Q. |
Dequeue(Q,x) | Remove and return the element at the top of the queue. |
Q.head | Pointer to the value at the front of the queue array. |
Q.tail | Pointer to the value at the end of the queue array. |
Note: to save performance implementations of queues maintain a pointer to the start and end of the queue. When new elements are added the tail moves forward (wrapping back around to the start if required). When elements are removed the head is moved forward.