// QueueLinked.h

#include #include

using namespace std;

#include "Queue.h"

template class QueueLinked : public Queue { public: QueueLinked(int maxNumber = Queue::MAX_QUEUE_SIZE); QueueLinked(const QueueLinked& other); QueueLinked& operator=(const QueueLinked& other); ~QueueLinked();

void enqueue(const DataType& newDataItem) throw (logic_error); DataType dequeue() throw (logic_error);

void clear();

bool isEmpty() const; bool isFull() const;

// Programming Exercise 2 void putFront(const DataType& newDataItem) throw (logic_error); DataType getRear() throw (logic_error); // Programming Exercise 3 int getLength() const;

void showStructure() const;

private: class QueueNode { public: QueueNode(const DataType& nodeData, QueueNode* nextPtr);

DataType dataItem; QueueNode* next; };

QueueNode* front; QueueNode* back; };

//-------------------------------------------------------------------- // // Laboratory 7 QueueLinked.cpp // // // //--------------------------------------------------------------------

#ifndef QUEUELINKED_CPP #define QUEUELINKED_CPP

#include

#include "QueueLinked.h"

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

template QueueLinked::QueueNode::QueueNode(const DataType& newDataItem, QueueNode* nextPtr)

// Creates a queue node containing data item nodeDataItem and next // pointer nextPtr.

: dataItem(newDataItem), next(nextPtr) { }

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

template QueueLinked::QueueLinked(int maxNumber) : front(0), back(0)

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

{}

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

template QueueLinked::~QueueLinked()

// Frees the memory used by a queue.

{ clear(); }

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

template void QueueLinked::enqueue(const DataType& newDataItem) throw (logic_error)

// Inserts newDataItem at the rear of a queue.

{ if (isFull()) { throw logic_error("push() while queue full"); }

QueueNode* temp = new QueueNode(newDataItem, 0);

if (isEmpty()) { front = temp; } else { back->next = temp; } back = temp; }

template DataType QueueLinked::dequeue() throw (logic_error)

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

{ if (isEmpty()) { throw logic_error("dequeue() while queue empty"); }

// Add code here }

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

template void QueueLinked::clear()

// Removes all the elements from a queue.

{ // Add code here

back = 0; }

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

template bool QueueLinked::isEmpty() const

// Returns true if a queue is empty. Otherwise, returns false.

{ // Add code here }

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

template bool QueueLinked::isFull() const

// Returns true if a queue is full. Otherwise, returns false. // The main reason it is included in the linked implementation is for // operation compatibility with the array-based implementation.

{ return false;

}

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

template < typename DataType > void QueueLinked::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* p; // Iterates through the queue

if (isEmpty()) cout << "Empty queue" << endl; else { cout << "Front\t"; for (p = front; p != 0; p = p->next) { if (p == front) { cout << "[" << p->dataItem << "] "; } else { cout << p->dataItem << " "; } } cout << "\trear" << endl; } }

//-------------------------------------------------------------------- // Programming Exercise 2 //--------------------------------------------------------------------

template void QueueLinked::putFront(const DataType& newDataItem) throw (logic_error)

// Enqueues newDataItem at the front of the queue -- // deque behavior -- instead of at the back as would normally happen.

{ if (isFull()) { throw logic_error("putFront() while queue full"); }

// Add code here }

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

template DataType QueueLinked::getRear() throw (logic_error)

// Removes and returns the dataItem at the rear of the queue -- // deque behavior -- instead of at the head as would normally happen.

{ if (isEmpty()) { throw logic_error("getRear() while queue empty"); }

DataType value = back->dataItem; // Save return value QueueNode* temp; if (front->next == 0) { // Only one item in queue. Remove it and reset queue pointers. delete back; front = back = 0; } else // Have more than one item in the queue. Find, remove, and return // rearmost. { // First, find the next-to-last node. for (temp = front; temp->next != back; temp = temp->next) /* do nothing */;

temp->next = 0; // Unlink the back/rear item from queue delete back; // Deallocate the back node back = temp; // Repoint back pointer at new back node. }

return value; }

//-------------------------------------------------------------------- // Programming Exercise 3 //--------------------------------------------------------------------

template int QueueLinked::getLength() const

// Calculates and returns the length of the queue.

{ // Add code here }

#endif // #ifndef QUEUELINKED_CPP