1.6.3 Queues1.6.2 Stacks1.6 Abstract Data Types1.6.3.1 Implementation as an Array

1.6.3 Queues

A  queue is a sequence of elements accessed from both ends: on one end (the tail or rear) new elements are added ("enqueue"), from the other end (the head or front) elements are removed ("dequeue"). A queue is therefore a  FIFO data structure (fist in, first out): the first element enqueued is also the first element dequeued. This idea is illustrated by the following picture.


Queue

Queue Operations
 


The following applet illustrates the various queue operations.

If you don't see the applet your Browser does not support Java. Click here, to view a precomputed image.

Applet

The abstract datatype "queue of integers" is represented by the following Java interface:

  interface Queue
  {
    // -----------------------------------------------------
    // b = isEmpty()
    // 'b' is true exactly if 'this' queue has no elements
    // -----------------------------------------------------
    boolean isEmpty();

    // -----------------------------------------------------
    // enqueue(e)
    // enqueue 'e' to tail of 'this' queue
    //
    // Output:
    //   'this' is the old queue with 't' at the end
    // -----------------------------------------------------
    void enqueue(int e);

    // -----------------------------------------------------
    // t = dequeue()
    // 'e' is the result of removing the head of 'this'
    // 
    // Input:
    //   '!isEmpty()'
    // Output:
    //   't' is the head of 'this' queue.
    //   'this' is the old queue without the head
    // -----------------------------------------------------
    int dequeue();

    // -----------------------------------------------------
    // t = peek()
    // 't' is the head of 'this' queue.
    //
    // Input:
    //   '!isEmpty()'
    // Output:
    //   't' is the head of 'this' queue
    //   'this' queue remains unchanged.
    // -----------------------------------------------------
    int peek();
  }

For the ADT queue, there exist two popular implementations.


© Wolfgang Schreiner; February 3, 2005

1.6.3 Queues1.6.2 Stacks1.6 Abstract Data Types1.6.3.1 Implementation as an Array