Contents |

A queue is an *ordered* data structure in that the order
of items are added to the structure affect the
order in which those items are removed.
In particular, a queue enforces *FIFO* ordering,
where *FIFO* stands for *First-In-First-Out*.
For example, suppose the values 5, 13, and 7 were
added to a queue in the order given. Then the
first item removed from the queue would be 5,
the second 13, and the last 7.

Queues can either be *bounded* or *unbounded*.
A bounded queue can only store a fixed number
of values while an unbounded queue can store
an unlimited number of values, subject to memory constraints.

A typical queue has one component, plus operations:

class queue { var store = ?; //operations ... }

The *store* can be set to a circular array, a dynamic
circular array or a linked-list.
If a circular array is used as the store, a
capacity is typically given as an argument to the constructor;
this capacity is used to allocate the array.

The terms used in describing a queue are:

- enqueue
- The name of the operation that adds a value to a queue. Analagous to the push operation of stacks.
- dequeue
- The name of the operation that removes a value from a queue.
Usually, the value removed is returned by the
*dequeue*operation. The*dequeue*operation returns the least recent value enqueued that has not already been dequeued. Analagous to the pop operation of a stack. - peek
- Like
*dequeue*, but the value is not removed from the queue. Consecutive peeks, with no intervening enqueues or dequeues, always return the same value. Sometimes,*peek*is named*front*. - front of the queue
- The least recently enqueued item that has not been dequeued.
- back of the queue
- The most recently enqueued item that has not been dequeued.

A queue is a top-level data structure that is used in various algorithms.

A bounded queue can be implemented with a circular array, while an unbounded queue can be built from either a dynamic circular array or a singly linked-list that holds a tail pointer.

A queue can also be built using two stacks.

This operation adds a given *value* to the end of
the queue. If the queue is implemented with a circular array
(dynamic or otherwise) or a singly linked-list as its store,
the *enqueue* operation translates to
the store's *add-to-back* operation.

Enqueuing a value is expected to take *Θ(1)* time.

This operation removes (and returns) the *value* at the beginning of
the queue. If the queue's store is a circular array
(dynamic or otherwise) or singly-linked list,
the *dequeue* operation translates to
the store's *remove-from-front* operation.

Removing a value from a queue is expected to take *Θ(1)* time.

This operation returns the value that is to be dequeued next,
without modifying the state of the queue.
Unlike a
stack,
a *peek* operation cannot be implemented
by a *dequeue* followed by an *enqueue*. Thus the implementation
of this operator must use an appropriate operation of the store.

This operation returns true if all pushed values have been popped, false otherwise. This can be done simply by incrementing a counter (initialized to zero) every time a push is performed and decrementing the counter every time a pop is performed. At points in time when the counter is zero, the queue is empty.

It would be an error, of course, if the counter was ever less than zero, indicating there were more pops than pushes.

The *is-empty* operation is expected to take *Θ(1)* time.

This operation returns true if the store is full, but only needs to be implemented for bounded queues.

Queues, in general, do not support traversals.

- These values are enqueued onto a queue in the order given: 3, 8, 1. A dequeue operation would return which value?
- 1
- 3
- 8
- 3 and 1
- 3 and 8

- Consider a queue based upon a regular array with enqueues onto the back of the array. What is the best one can do in terms of worst case behavior for
*enqueue*and*dequeue*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a queue based upon a circular array with enqueues onto the back of the array. What is the best one can do in terms of worst case behavior for
*enqueue*and*dequeue*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a queue based upon a singly-linked list without a tail pointer with enqueues onto the front of the list. What is the best one can do in terms of worst case behavior for
*enqueue*and*dequeue*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a queue based upon a singly-linked list with a tail pointer with enqueues onto the back of the list. What is the best one can do in terms of worst case behavior for
*enqueue*and*dequeue*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a queue based upon a doubly-linked list with a tail pointer with enqueues onto the front of the list. What is the best one can do in terms of worst case behavior for
*enqueue*and*dequeue*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

Contents |