//--------------------------------------------------------------------
//
//  Laboratory 6                                        queuelnk.cpp
//
//  SOLUTION: Linked list implementation of the Queue ADT
//
//--------------------------------------------------------------------

#include <assert.h>
#include <alloc.h>
#include "queuelnk.h"

//--------------------------------------------------------------------

template < class QE >
QueueNode<QE>:: QueueNode( const QE &elem, QueueNode<QE> *nextPtr )

// Creates a queue node containing element elem and next pointer
// nextPtr.

  : element(elem),
    next(nextPtr)
{}

//--------------------------------------------------------------------

template < class QE >
Queue<QE>:: Queue ( int ignored )

// Creates an empty queue. Parameter is provided for compatability
// with the array implementation and is ignored.

  : front(0),
    rear(0)
{}

//--------------------------------------------------------------------

template < class QE >
Queue<QE>:: ~Queue ()

// Frees the memory used by a queue.

{
    clear();
}

//--------------------------------------------------------------------

template < class QE >
void Queue<QE>:: enqueue ( const QE &newElement )

// Inserts newElement at the rear of a queue.

{
    QueueNode<QE> *p;   // Pointer to enqueued element

    p = new QueueNode<QE>(newElement,0);
    assert ( p != 0 );

    if ( front == 0 )
       front = p;
    else
       rear->next = p;
    rear = p;
}

//--------------------------------------------------------------------

template < class QE >
QE Queue<QE>:: dequeue ()

// Removes the least recently (front) element from a queue and
// returns it.

{
    QueueNode<QE> *p;   // Pointer to dequeued node
    QE temp;            // Temporarily stores dequeued element

    assert ( front != 0 );     // Requires that the queue is not empty

    temp = front->element;
    p = front;
    front = front->next;
    if ( front == 0 )
       rear = 0;
    delete p;

    return temp;
}

//--------------------------------------------------------------------

template < class QE >
void Queue<QE>:: clear ()

// Removes all the elements from a queue.

{
    QueueNode<QE> *p,       // Points to successive nodes
                  *nextP;   // Stores pointer to next node
    p = front;
    while ( p != 0 )
    {
        nextP = p->next;
        delete p;
        p = nextP;
    }

    front = 0;
    rear  = 0;
}


//--------------------------------------------------------------------

template < class QE >
int Queue<QE>:: empty () const

// Returns 1 if a queue is empty. Otherwise, returns 0.

{
    return ( front == 0 );
}

//--------------------------------------------------------------------

template < class QE >
int Queue<QE>:: full () const

// Returns 1 if a queue is full. Otherwise, returns 0. Cannot be
// done cleanly in generic C++ because there is sometimes overhead
// associated with a memory allocation.

{
    return ( coreleft() < sizeof(QE) );
}


//--------------------------------------------------------------------

template < class QE >
void Queue<QE>:: showStructure () const

// Linked list implementation. Outputs the elements in a queue. If
// the queue is empty, outputs "Empty queue". This operation is
// intended for testing and debugging purposes only.

{
    QueueNode<QE> *p;   // Iterates through the queue

    if ( front == 0 )
       cout << "Empty queue" << endl;
    else
    {
       cout << "front ";
       for ( p = front ; p != 0 ; p = p->next )
           cout << p->element << " ";
       cout << "rear" << endl;
    }
}