Stacks Top Priority Queues Contents

Queues

Synopsis

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.

Structure

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.

Vocabulary

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.

Supports

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

Dependencies

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.

Operations

enqueue

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.

dequeue

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.

peek

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.

is-empty

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.

is-full

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

Traversals

Queues, in general, do not support traversals.

Concept Inventory

     
  1. These values are enqueued onto a queue in the order given: 3, 8, 1. A dequeue operation would return which value?
    1. 1
    2. 3
    3. 8
    4. 3 and 1
    5. 3 and 8
     
  2. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  3. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  4. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  5. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  6. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant

lusth@cs.ua.edu


Stacks Top Priority Queues Contents