Queue.h

Classes

Queue -- A First-In-First-Out (FIFO) data structure. (full description)

template<class T> class Queue

Interface

Public Members

Queue()

Queue(const Queue<T> &other)

~Queue()

Queue<T> &operator=(const Queue<T> &other)

void enqueue(const T &value)

void operator()(const T &value)

void dequeue(T &value)

T operator()()

void clear()

void compress()

uInt nelements() const

Description

Review Status

Reviewed By:

Gareth Hunt

Date Reviewed:

94Jan06

Programs:

Tests:

tQueue

Synopsis

A Queue as implemented here is a simple container which can grow with time, and which returns its elements (only) in the order they are inserted. That is, the fundamental operations are to insert an element in the queue (at the "back") and retrieve an element (from the "front").

     Queue<Int> queue;
     Int x;
     queue(1);                          // enqueue
     queue.enqueue(2);                  // enqueue
     queue(3);                          // enqueue
     queue(4);                          // enqueue
     queue.dequeue(x);                  // dequeue
     cout << x << endl;
     ...
     while (queue.nelements() > 0) 
         cout << queue() << " ";        // dequeue
     cout << endl;

Presently the implementation is rather simple. It stores the elements in a Block which resizes (exponentially to avoid quadratic behaviour) when necessary. New elements are added to the end of the block, old elements are pulled off the front of the Block. The positions at the beginning are only reclaimed when the queue is empty or the compress() member is called. This implementation is reasonably time efficient, but not necessarily space efficient. A more sophisticated implementation may be necessary eventually.

To be used in a Queue, a class must have a default constructor, assignment operator, and copy constructor.

Motivation

This class was written for an application which thought it needed to queue up some Glish events while it processed other Glish events. In fact that application (Clean) was simplified so that it doesn't presently operate that way.

To Do

It is conceivable that an iterator might be useful for this class.
If this class is ever heavily used, a more space efficient implementation may be necessary.

Member Description

Queue()

Create a Queue with no elements.

Queue(const Queue<T> &other)

Create a queue which is a copy of other. Compresses unused heap storage.

~Queue()

Queue<T> &operator=(const Queue<T> &other)

Create a queue which is a copy of other. Compresses unused heap storage.

void operator()(const T &value)

Place an element in the queue. After calling this, nelements() is increaed by one.

Short-hand for enqueue();

void enqueue(const T &value)

Place an element in the queue. After calling this, nelements() is increaed by one.

T operator()()

Remove an element from the head of the queue and decrease nelements() by one. If called when nelements() is zero, an exception is thrown.

Short-hand for dequeue.

void dequeue(T &value)

Remove an element from the head of the queue and decrease nelements() by one. If called when nelements() is zero, an exception is thrown.

void clear()

Delete all the elements from the queue, and free up any resources.

void compress()

Leave this queue logically unchanged, but remove unused storage. With the present Block based implementation, removes the unused entries at the beginning of the block.

uInt nelements() const

How many elements are in the queue?