Queue Abstract Data Type

The ADT designer writes the queue ADT specification:

Prototype: Queue();

Purpose: Create an empty queue.

Precondition: None.

Postcondition: An empty queue has been created.

Prototype: void Enqueue( /* in */ Item newItem );

Purpose: Add a newItem to the rear of the queue.

Precondition: The queue is not full.

Postcondition: The newItem has been added to the rear of the queue.

Prototype: Item Dequeue();

Purpose: Remove and return the item from the front of a queue.

Precondition: The queue is not empty.

Postcondition: The queue's front item has been removed from the queue.

Function value = the item that was at the front of the queue.

Prototype: Item Front() const;

Purpose: Return a copy of the item at the front of a queue.

Precondition: The queue is not empty.

Postcondition: Function value = a copy of the item at the front of a queue.

Prototype: bool IsEmpty() const;

Purpose: Test whether the queue is empty.

Precondition: None

Postcondition: Function value = true, if the queue is empty; false if the queue is not empty.

Prototype: bool IsFull() const;

Purpose: Test whether the queue is full.

Precondition: None.

Postcondition: Function value = true, if the queue is full; false if the queue is not full.

The ADT implementer codes the queue header and the queue implementation.

Header file: queue.h

#ifndef QUEUE_H

#define QUEUE_H

typedef int Item;

const int MAX_SIZE = 100;

class Queue {

public:

Queue();

void Enqueue( /* in */ Item newItem );

Item Front() const;

Item Dequeue();

bool IsEmpty() const;

bool IsFull() const;

private:

Item items[MAX_SIZE];

int front; // index of slot before front item. 0..MAX_SIZE-1

int rear; // index of rear item 0..MAX_SIZE-1

int size;

};

#endif

Implementation file: queue.cpp

#include "queue.h"

Queue::Queue( void )

{

front = 0;

rear = 0;

size = 0;

}

void Queue::Enqueue( /* in */ Item newItem )

{

if ( rear == MAX_SIZE-1 ) // rear = (rear+1) % MAX_SIZE;

rear = 0; //

else //

rear++; //

items[rear] = newItem;

size++;

}

Item Queue::Front( void ) const

{

if ( front == MAX_SIZE-1 ) // return items[ (front+1) % MAX_SIZE ];

return items[0]; //

else //

return items[front+1]; //

}

Item Queue::Dequeue( void )

{

size--;

if ( front == MAX_SIZE-1 ) // front = ( front + 1 ) % MAX_SIZE

front = 0; //

else //

front++; //

return items[front];

}

bool Queue::IsEmpty( void ) const

{

return ( size == 0 );

}

bool Queue::IsFull( void ) const

{

return ( size == MAX_SIZE );

}