3. (Carrano) Implement Programming Problem #8 p. 394. Use the structure of Priority Queue Cap 14. In its implementation.

You have to create the main.

LinkedList.h

#ifndef _LINKED_LIST

#define _LINKED_LIST

#include "ListInterface.h"

#include "Node.h"

#include "PrecondViolatedExcep.h"

template

class LinkedList : public ListInterface

{

private:

Node* headPtr; // Pointer to first node in the chain;

// (contains the first entry in the list)

int itemCount; // Current count of list items

// Locates a specified node in this linked list.

// @pre position is the number of the desired node;

// position >= 1 and position

// @post The node is found and a pointer to it is returned.

// @param position The number of the node to locate.

// @return A pointer to the node at the given position.

Node* getNodeAt(int position) const;

public:

LinkedList();

LinkedList(const LinkedList& aList);

virtual ~LinkedList();

bool isEmpty() const;

int getLength() const;

bool insert(int newPosition, const ItemType& newEntry);

bool remove(int position);

void clear();

/** @throw PrecondViolatedExcep if position

position > getLength(). */

ItemType getEntry(int position) const throw(PrecondViolatedExcep);

/** @throw PrecondViolatedExcep if position

position > getLength(). */

void setEntry(int position, const ItemType& newEntry)

throw(PrecondViolatedExcep);

}; // end LinkedList

#include

template

LinkedList::LinkedList() : headPtr(nullptr), itemCount(0)

{

} // end default constructor

template

LinkedList::LinkedList(const LinkedList& aList) : itemCount(aList.itemCount)

{

Node* origChainPtr = aList.headPtr; // Points to nodes in original chain

if (origChainPtr == nullptr)

headPtr = nullptr; // Original list is empty

else

{

// Copy first node

headPtr = new Node();

headPtr->setItem(origChainPtr->getItem());

// Copy remaining nodes

Node* newChainPtr = headPtr; // Points to last node in new chain

origChainPtr = origChainPtr->getNext(); // Advance original-chain pointer

while (origChainPtr != nullptr)

{

// Get next item from original chain

ItemType nextItem = origChainPtr->getItem();

// Create a new node containing the next item

Node* newNodePtr = new Node(nextItem);

// Link new node to end of new chain

newChainPtr->setNext(newNodePtr);

// Advance pointer to new last node

newChainPtr = newChainPtr->getNext();

// Advance original-chain pointer

origChainPtr = origChainPtr->getNext();

} // end while

newChainPtr->setNext(nullptr); // Flag end of chain

} // end if

} // end copy constructor

template

LinkedList::~LinkedList()

{

clear();

} // end destructor

template

bool LinkedList::isEmpty() const

{

return itemCount == 0;

} // end isEmpty

template

int LinkedList::getLength() const

{

return itemCount;

} // end getLength

template

bool LinkedList::insert(int newPosition, const ItemType& newEntry)

{

bool ableToInsert = (newPosition >= 1) && (newPosition

if (ableToInsert)

{

// Create a new node containing the new entry

Node* newNodePtr = new Node(newEntry);

// Attach new node to chain

if (newPosition == 1)

{

// Insert new node at beginning of chain

newNodePtr->setNext(headPtr);

headPtr = newNodePtr;

}

else

{

// Find node that will be before new node

Node* prevPtr = getNodeAt(newPosition - 1);

// Insert new node after node to which prevPtr points

newNodePtr->setNext(prevPtr->getNext());

prevPtr->setNext(newNodePtr);

} // end if

itemCount++; // Increase count of entries

} // end if

return ableToInsert;

} // end insert

template

bool LinkedList::remove(int position)

{

bool ableToRemove = (position >= 1) && (position

if (ableToRemove)

{

Node* curPtr = nullptr;

if (position == 1)

{

// Remove the first node in the chain

curPtr = headPtr; // Save pointer to node

headPtr = headPtr->getNext();

}

else

{

// Find node that is before the one to delete

Node* prevPtr = getNodeAt(position - 1);

// Point to node to delete

curPtr = prevPtr->getNext();

// Disconnect indicated node from chain by connecting the

// prior node with the one after

prevPtr->setNext(curPtr->getNext());

} // end if

// Return node to system

curPtr->setNext(nullptr);

delete curPtr;

curPtr = nullptr;

itemCount--; // Decrease count of entries

} // end if

return ableToRemove;

} // end remove

template

void LinkedList::clear()

{

while (!isEmpty())

remove(1);

} // end clear

template

ItemType LinkedList::getEntry(int position) const throw(PrecondViolatedExcep)

{

// Enforce precondition

bool ableToGet = (position >= 1) && (position

if (ableToGet)

{

Node* nodePtr = getNodeAt(position);

return nodePtr->getItem();

}

else

{

string message = "getEntry() called with an empty list or ";

message = message + "invalid position.";

throw(PrecondViolatedExcep(message));

} // end if

} // end getEntry

template

void LinkedList::setEntry(int position, const ItemType& newEntry) throw(PrecondViolatedExcep)

{

// Enforce precondition

bool ableToSet = (position >= 1) && (position

if (ableToSet)

{

Node* nodePtr = getNodeAt(position);

nodePtr->setItem(newEntry);

}

else

{

string message = "setEntry() called with an invalid position.";

throw(PrecondViolatedExcep(message));

} // end if

} // end setEntry

template

Node* LinkedList::getNodeAt(int position) const

{

// Debugging check of precondition

assert((position >= 1) && (position

// Count from the beginning of the chain

Node* curPtr = headPtr;

for (int skip = 1; skip

curPtr = curPtr->getNext();

return curPtr;

} // end getNodeAt

// End of implementation file.

#endif

ListInterFace.h

#ifndef _LIST_INTERFACE

#define _LIST_INTERFACE

template

class ListInterface

{

public:

/** Sees whether this list is empty.

@return True if the list is empty; otherwise returns false. */

virtual bool isEmpty() const = 0;

/** Gets the current number of entries in this list.

@return The integer number of entries currently in the list. */

virtual int getLength() const = 0;

/** Inserts an entry into this list at a given position.

@pre None.

@post If 1

successful, newEntry is at the given position in the list,

other entries are renumbered accordingly, and the returned

value is true.

@param newPosition The list position at which to insert newEntry.

@param newEntry The entry to insert into the list.

@return True if insertion is successful, or false if not. */

virtual bool insert(int newPosition, const ItemType& newEntry) = 0;

/** Removes the entry at a given position from this list.

@pre None.

@post If 1

the entry at the given position in the list is removed, other

items are renumbered accordingly, and the returned value is true.

@param position The list position of the entry to remove.

@return True if removal is successful, or false if not. */

virtual bool remove(int position) = 0;

/** Removes all entries from this list.

@post List contains no entries and the count of items is 0. */

virtual void clear() = 0;

/** Gets the entry at the given position in this list.

@pre 1

@post The desired entry has been returned.

@param position The list position of the desired entry.

@return The entry at the given position. */

virtual ItemType getEntry(int position) const = 0;

/** Replaces the entry at the given position in this list.

@pre 1

@post The entry at the given position is newEntry.

@param position The list position of the entry to replace.

@param newEntry The replacement entry. */

virtual void setEntry(int position, const ItemType& newEntry) = 0;

}; // end ListInterface

#endif

ListQueue.h

#ifndef _LIST_QUEUE

#define _LIST_QUEUE

#include "QueueInterface.h"

#include "LinkedList.h"

#include "PrecondViolatedExcep.h"

template

class ListQueue : public QueueInterface

{

private:

LinkedList* listPtr; // Pointer to list of queue items

public:

ListQueue();

ListQueue(const ListQueue& aQueue);

~ListQueue();

bool isEmpty() const;

bool enqueue(const ItemType& newEntry);

bool dequeue();

/** @throw PrecondViolatedExcep if queue is empty. */

ItemType peekFront() const throw(PrecondViolatedExcep);

}; // end ListQueue

template

ListQueue::ListQueue()

{

listPtr = new LinkedList();

} // end default constructor

template

ListQueue::ListQueue(const ListQueue& aQueue)

{

// First, create our own list

listPtr = new LinkedList();

// Then add items to it using public methods

for (int position = 1; position getLength(); position++)

{

listPtr->insert(position, aQueue.listPtr->getEntry(position));

} // end for

} // end copy constructor

template

ListQueue::~ListQueue()

{

} // end destructor

template

bool ListQueue::isEmpty() const

{

return listPtr->isEmpty();

} // end isEmpty

template

bool ListQueue::enqueue(const ItemType& newEntry)

{

return listPtr->insert(listPtr->getLength() + 1, newEntry);

} // end enqueue

template

bool ListQueue::dequeue()

{

return listPtr->remove(1);

} // end dequeue

template

ItemType ListQueue::peekFront() const throw(PrecondViolatedExcep)

{

if (isEmpty())

throw PrecondViolatedExcep("peekFront() called with empty queue.");

// Queue is not empty; return front

return listPtr->getEntry(1);

} // end peekFront

// End of implementation file.

#endif

Node.h

#ifndef _NODE

#define _NODE

template

class Node

{

private:

ItemType item; // A data item

Node* next; // Pointer to next node

public:

Node();

Node(const ItemType& anItem);

Node(const ItemType& anItem, Node* nextNodePtr);

void setItem(const ItemType& anItem);

void setNext(Node* nextNodePtr);

ItemType getItem() const;

Node* getNext() const;

}; // end Node

#include

template

Node::Node() : next(nullptr)

{

} // end default constructor

template

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)

{

} // end constructor

template

Node::Node(const ItemType& anItem, Node* nextNodePtr) :

item(anItem), next(nextNodePtr)

{

} // end constructor

template

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

template

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

template

ItemType Node::getItem() const

{

return item;

} // end getItem

template

Node* Node::getNext() const

{

return next;

} // end getNext

#endif

PrecondViolatedExcep.h

#ifndef _PRECOND_VIOLATED_EXCEP

#define _PRECOND_VIOLATED_EXCEP

#include

#include

using namespace std;

class PrecondViolatedExcep : public logic_error

{

public:

PrecondViolatedExcep(const string& message = "");

}; // end PrecondViolatedExcep

PrecondViolatedExcep::PrecondViolatedExcep(const string& message) : logic_error("Precondition Violated Exception: " + message)

{

} // end constructor

// End of implementation file.

#endif

QueueInterface.h

#ifndef _QUEUE_INTERFACE

#define _QUEUE_INTERFACE

template

class QueueInterface

{

public:

/** Sees whether this queue is empty.

@return True if the queue is empty, or false if not. */

virtual bool isEmpty() const = 0;

/** Adds a new entry to the back of this queue.

@post If the operation was successful, newEntry is at the

back of the queue.

@param newEntry The object to be added as a new entry.

@return True if the addition is successful or false if not. */

virtual bool enqueue(const ItemType& newEntry) = 0;

/** Removes the front of this queue.

@post If the operation was successful, the front of the queue

has been removed.

@return True if the removal is successful or false if not. */

virtual bool dequeue() = 0;

/** Returns the front of this queue.

@pre The queue is not empty.

@post The front of the queue has been returned, and the

queue is unchanged.

@return The front of the queue. */

virtual ItemType peekFront() const = 0;

}; // end QueueInterface

#endif

8 The people who run the Motorvehicle Department (MVD ) have a problem. They are concerned that people do not spend cnough time waiting in lines to appreciate the privilege of owning and driving an automobile. The current arrangement is as follows: When people walk in the door, they must wait in a line to sign in. Once they have signed in, they are told either to stand in line for registration renewal or to wait until they are called for license renewal. Once they have completed their desired transaction, they must go and wait in line for the cashier. When they finally get to the front of the cashier's line, if they expect to pay by check, they are told that all checks must get approved. To do this, it is necessary to go to the check-approver's table and then reenter the cashier's line at the encd