4.3 DynamicArray This class encapsulates a dynamic array. The array grows as more space is needed. See dynamicArray.h for details. Compress and upload your dynamicArray.cpp to the correct upload slot when done. For this task and all the following tasks, your archive must not contain any folders or subfolders.

#ifndef PRIORITYQUEUE_H

#define PRIORITYQUEUE_H

#include "queue.h"

#include "linearStructure.h"

template

class PriorityQueue : public Queue

{

public:

/*

The constructor initializes the PriorityQueue with

the structure which will contain the elements.

*/

PriorityQueue(LinearStructure* c);

/*

Copy constructor

*/

PriorityQueue(const PriorityQueue& other);

/*

Overloaded assignment operator.

*/

virtual PriorityQueue& operator=(const PriorityQueue& other);

/*

Destructor.

*/

virtual ~PriorityQueue();

/*

This function removes and returns the element

with the highest priority in the PriorityQueue.

*/

virtual T remove();

/*

This function returns, but does NOT remove, the

element with the higest priority.

*/

virtual T next();

/*

Simply flips the max member variable.

*/

virtual void reverse();

private:

/*

This flag determines whether the largest or smallest

element in the queue is returned next. If it is set

to true, then return the largest element. Otherwise

return the smallest element. This flag should be initialized

to true in your constructor.

*/

bool max;

};

#include "priorityQueue.cpp"

#endif

4.4 LinkedList A circular doubly-linked list class. See linkedList.h for details. Compress and upload your linkedList.cpp to the correct upload slot when done. Test the class thoroughly before uploading!

#ifndef LINKEDLIST_H

#define LINKEDLIST_H

#include "linearStructure.h"

#include "node.h"

template

class LinkedList;

template

ostream& operator<<(ostream&,LinkedList&);

/*

Circular doubly-linked list.

Note: head->prev must point to the last node at all times.

*/

template

class LinkedList : public LinearStructure

{

public:

/*The overloaded stream operator for the LinkedList class. If

a LinkedList object is printed and contains the elements a,c,b and m, with

element 'a' at index 0 (head) and element 'm' at index 3 (first to last), the

output MUST be in the following format:

[a,c,b,m]

with no white space or new lines.

NOTE: if the list is empty, output empty square brackets:

[]

*/

friend ostream& operator<< (ostream&,LinkedList&);

/*

The constructor initializes an empty list.

*/

LinkedList();

/*

The copy constructor.

*/

LinkedList(const LinkedList& other);

/*

The overloaded assignment operator.

*/

LinkedList& operator=(const LinkedList& other);

/*

Creates a dynamically allocated deep copy of the object and returns

a pointer to it

*/

virtual LinkedList* clone();

/*

The destructor.

*/

virtual ~LinkedList();

/*

Inserts an element at the given index. The following holds

for this function:

1.) It is valid to insert at index 0 of an empty list.

2.) It is valid to insert at the index returned by size(). Simply

append the element to the back of the list.

3.) Only indices between 0 and size() are valid.

4.) For an invalid index, throw an exception message "invalid index".

*/

virtual void insert(int index, T element);

/*

Removes and returns the element at the index passed in

as a parameter. If an invalid index is provided,

throw the string "No element found".

*/

virtual T remove(int index);

/*

Returns the element at the index passed in

as a parameter. The element is not removed from the data structure.

If an invalid index is given, throw the string "No element found".

*/

virtual T get(int index) const;

/*

Returns the first element from the list, i.e. element stored at head.

If the list is empty, throw the string "No element found".

*/

virtual const T& getFirst() const;

/*

Returns the last element from the list.

If the list is empty, throw the string "No element found".

*/

virtual const T& getLast() const;

/*

Returns the index of the first (head) element in the list.

If the list is empty, throw the string "No element found".

*/

virtual int getIndexFirst() const;

/*

Returns the index of the last element in the list.

If list is empty, throw the string "No element found".

*/

virtual int getIndexLast() const;

/*

Returns true if the list is empty, and false

otherwise.

*/

virtual bool isEmpty();

/*

Removes all of the nodes from the list. After this function has

been called on a LinkedList object, the list must be empty.

*/

virtual void clear();

/*

Returns the head, not the element at the head.

*/

Node* getLeader();

protected:

ostream& print(ostream& os);

private:

/*

Use this function to calculate the total number of nodes in the list.

*/

int size() const;

/*

The first node in the list (index 0 would always correspond to the head)

*/

Node* head;

};

#include "linkedList.cpp"

#endif

4.5 OrderedContainer This class provides an interface for all types of ordered containers. An ordered container may be implemented in a variety of ways. As an example, a stack may be implemented as either a linked list or an array. The ordered container is given an implementation object (either a linked list or a dynamic array), and data elements are stored in the specified structure. The subclasses (stack, queue, etc.) will have to manipulate their underlying implementations to produce the correct results.

#ifndef ORDEREDCONTAINER_H

#define ORDEREDCONTAINER_H

#include "linearStructure.h"

template

class OrderedContainer

{

public:

/*

The constructor initializes the Container with the

structure passed in as a parameter. You will have to

make a copy of the LinearStructure as parties outside

of this class may have pointers to it still. The

elements added to the container must be stored in the

object to which dataStructure points.

*/

OrderedContainer(LinearStructure* c);

/*

Copy constructor

*/

OrderedContainer(const OrderedContainer& other);

/*

Overloaded assignment operator.

*/

virtual OrderedContainer& operator=(const OrderedContainer& other);

/*

Destructor.

*/

virtual ~OrderedContainer();

/*

Removes an element from the container. See subclasses

for more details.

*/

virtual T remove() = 0;

/*

Returns an element from the container. See subclasses

for more details.

*/

virtual T next() = 0;

/*

Inserts an element into the container. See subclasses

for more details.

*/

virtual void insert(T el) = 0;

/*

Returns true if the container is empty, and false

if the container contains elements.

*/

virtual bool isEmpty();

/*

This function reverses the order of the elements

in the container.

*/

virtual void reverse() = 0;

/*

Returns a pointer to the linear structure in which the elements

are contained.

*/

virtual LinearStructure* getImplementation();

protected:

/*

A pointer to an object of type LinearStructure. This

structure should contain the elements inserted into

the container. This member should be initialized

in the constructor.

*/

LinearStructure* dataStructure;

};

#include "orderedContainer.cpp"

#endif

4.6 Stack A stack is a linear structure which does not allow access to arbitrary elements stored in it. The top of the stack is the only entry point of a stack structure, and when an element is added to a stack, it must be stored on top of the stack. When an element is read from the stack, only the top element can be accessed. Removal of elements can also only be applied to the top element. Because of this property, stacks are known as LIFO (last-in-first-out) structures. Compress and upload all your source (.cpp) files to the correct upload slot when done. Both linear data structures (DynamicArray and LinkedList) will be used to test your stack.

#ifndef STACK_H

#define STACK_H

#include "orderedContainer.h"

#include "linearStructure.h"

template

class Stack : public OrderedContainer

{

public:

/*

The constructor initializes the stack with the

structure which will contain the elements. Remember to

make a deep copy of the input structure.

*/

Stack(LinearStructure* c);

/*

Copy constructor

*/

Stack(const Stack& other);

/*

Overloaded assignment operator.

*/

Stack& operator=(const Stack& other);

/*

Destructor.

*/

virtual ~Stack();

/*

This function pops and returns the element

on the top of the Stack.

*/

virtual T remove();

/*

This function returns, but does NOT remove, the

element at the top of the stack.

*/

virtual T next();

/*

This function pushes the element sent in as a

parameter onto the top of the Stack.

*/

virtual void insert(T el);

/*

This function reverses the order of the elements

in the stack. For example, if the stack contains the

elements w, x, y and z, where w is at the top of the

stack, then the stack should be z, y, x, w after the

reverse with z now being at the top of the stack.

*/

virtual void reverse();

};

#include "stack.cpp"

#endif

4.7 Queue A queue is also a linear structure which does not allow access to arbitrary elements stored in it. A queue has two entry points: front and rear. When an element is added, it is always added at the rear end. When an element is read or removed, it is always read/removed from the front of the queue. Queues are also known as FIFO (first-in-first-out) structures, which means that elements are removed and returned from a queue in the order in which they were inserted. Compress and upload all your source (.cpp) files to the correct upload slot when done. Both linear data structures (DynamicArray and LinkedList) will be used to test your queue.

#ifndef QUEUE_H

#define QUEUE_H

#include "orderedContainer.h"

#include "linearStructure.h"

template

class Queue : public OrderedContainer

{

public:

/*

The constructor initializes the Queue with the

structure which will contain the elements. Remember to

make a deep copy of the input structure.

*/

Queue(LinearStructure* c);

/*

Copy constructor

*/

Queue(const Queue& other);

/*

Overloaded assignment operator.

*/

virtual Queue& operator=(const Queue& other);

/*

Destructor.

*/

virtual ~Queue();

/*

This function removes and returns the element

at the front of the Queue.

*/

virtual T remove();

/*

This function returns, but does NOT remove, the

element at the front of the queue.

*/

virtual T next();

/*

This function places the element sent in as a

parameter at the back of the Queue.

*/

virtual void insert(T el);

/*

This function reverses the order of the elements

in the queue. For example, if the stack contains the

elements w, x, y and z, where w is at the front (first element)

of the queue, then the queue should be z, y, x, w after the

reverse with z now being at the front of the queue.

*/

virtual void reverse();

};

#include "queue.cpp"

#endif

4.8 PriorityQueue PriorityQueue inherits from Queue. Priority queues recognize the fact that some elements might be more important than others, and return elements with the highest importance first, regardless of the order in which the elements were inserted.

#ifndef PRIORITYQUEUE_H

#define PRIORITYQUEUE_H

#include "queue.h"

#include "linearStructure.h"

template

class PriorityQueue : public Queue

{

public:

/*

The constructor initializes the PriorityQueue with

the structure which will contain the elements.

*/

PriorityQueue(LinearStructure* c);

/*

Copy constructor

*/

PriorityQueue(const PriorityQueue& other);

/*

Overloaded assignment operator.

*/

virtual PriorityQueue& operator=(const PriorityQueue& other);

/*

Destructor.

*/

virtual ~PriorityQueue();

/*

This function removes and returns the element

with the highest priority in the PriorityQueue.

*/

virtual T remove();

/*

This function returns, but does NOT remove, the

element with the higest priority.

*/

virtual T next();

/*

Simply flips the max member variable.

*/

virtual void reverse();

private:

/*

This flag determines whether the largest or smallest

element in the queue is returned next. If it is set

to true, then return the largest element. Otherwise

return the smallest element. This flag should be initialized

to true in your constructor.

*/

bool max;

};

#include "priorityQueue.cpp"

#endif