//-------------------------------------------------------------------- // // Laboratory 7 QueueArray.cpp // // // //--------------------------------------------------------------------

#ifndef QUEUEARRAY_CPP #define QUEUEARRAY_CPP

#include

#include "QueueArray.h"

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

template QueueArray::QueueArray(int maxNumber)

// Creates an empty queue. Allocates enough memory for maxNumber // data items (defaults to MAX_QUEUE_SIZE in class declaration).

: maxSize(maxNumber), front(-1), back(-1) { dataItems = new DataType[maxNumber]; }

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

template QueueArray::~QueueArray()

// Frees the memory used by a queue.

{ // Add code here }

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

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

// Inserts newDataItem at the rear of a queue.

{ if (isFull()) { throw logic_error("enqueue() while queue full"); // Add code here

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

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

// Removes the least recently added (front) data item from a queue // and returns it.

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

int retIndex = front; if (front == back) { front = -1; back = -1; } else front = (++front) % maxSize;

return dataItems[retIndex]; }

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

template void QueueArray::clear()

// Removes all the data items from a queue.

{ // Add code here }

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

template bool QueueArray::isEmpty() const { // Add code here }

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

template bool QueueArray::isFull() const { // Add code here }

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

#if LAB7_TEST2 template void QueueArray::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 QueueArray::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"); }

int valuePos = back; --back; if (back == front - 1) { // Just removed last item back = front = -1; } else if (back < 0) { back = maxSize - 1; }

return dataItems[valuePos]; } #endif

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

#if LAB7_TEST3 template int QueueArray::getLength() const

// Calculates and returns the length of the queue.

{ if (isEmpty()) { return 0; } else if (front > back) { return (maxSize - front) + (back + 1); } else { return (back - front) + 1; } } #endif

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

template void QueueArray::showStructure() const // Array implementation. Outputs the data items in a queue. If the // queue is empty, outputs "Empty queue". This operation is intended // for testing and debugging purposes only.

{ int j; // Loop counter

if (front == -1) cout << "Empty queue" << endl; else { cout << "Front = " << front << " Back = " << back << endl; for (j = 0; j < maxSize; j++) cout << j << "\t"; cout << endl; if (back >= front) for (j = 0; j < maxSize; j++) if ((j >= front) && (j <= back)) cout << dataItems[j] << "\t"; else cout << " \t"; else for (j = 0; j < maxSize; j++) if ((j >= front) || (j <= back)) cout << dataItems[j] << "\t"; else cout << " \t"; cout << endl; } }

#endif //#ifndef QUEUEARRAY_CPP

//-------------------------------------------------------------------- // // 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