Revision as of 03:56, 19 November 2009

A queue is a data structure containing zero or more items, all of the same type, which supports two basic operations:

• Push an element onto the queue.
• Pop the first value off the queue, returning its value in the process.

In practice, we might choose to include the following operations as well:

• Construct an empty queue.
• Copy the contents of one queue to another.
• Peek at the first element in the queue (the one which would be popped next), without removing it.
• Empty an already existing queue.
• Find size of a queue.
• Test if empty.

Unlike with a stack, a peek operation cannot be implemented on a queue as a pop followed by a push. (The test if empty operation is still the same as the find size operation followed by a test of whether or not the size is zero.)

Terminology

The term queue is based off of real-life queues; they are often referred to as lines, as in the case of a queue for a ride in an amusement park. In a queue like this, we join the end of the queue (become last) and wait until we are at the front (become first) before we are popped (let in). In computer science, the most recently pushed element is last, whereas the least recently pushed element is first. An element can be described as before another if the latter was pushed later; the latter is referred to as being after the former. To push means to add an element, and to pop means to remove an element.

Implementation

Array implementation

In an array implementation of a queue, the contents of the queue are stored in consecutive indices in an array. The first element of the queue is normally at the lowest index (i.e. 0) and the last is at the highest. Following is an exemplary implementation:

object queue
     function construct(max_size)
          let A be an array that can hold at least max_size elements
          let last = 0
     function push(x)
          A[last] = x
          last = last + 1
     function pop
          return_val = A[0]
          move memory from A[1..last] to A[0..last - 1]
          last = last - 1
          return return_val
     function peek
          return A[0]
     function size
          return last
     function empty
          last = 0