Description
In today’s lab we will design and implement the Queue ADT using linked list.
quetype.h
#ifndef QUETYPE_H_INCLUDED
#define QUETYPE_H_INCLUDED
class FullQueue
{};
class EmptyQueue
{};
template
class QueType
{
struct NodeType
{
ItemType info;
NodeType* next;
};
public:
QueType();
~QueType();
void MakeEmpty();
void Enqueue(ItemType);
void Dequeue(ItemType&);
bool IsEmpty();
bool IsFull();
private:
NodeType *front, *rear;
};
#endif // QUETYPE_H_INCLUDED
quetype.cpp
#include “quetype.h”
#include
using namespace std;
template
QueType::QueType()
{
front = NULL;
rear = NULL;
}
template
bool QueType::IsEmpty()
{
return (front == NULL);
}
template
bool QueType::IsFull()
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc& exception)
{
return true;
}
}
template
void QueType::Enqueue(ItemType newItem)
{
if (IsFull())
throw FullQueue();
else
{
NodeType* newNode;
newNode = new NodeType;
newNode->info = newItem;
newNode->next = NULL;
if (rear == NULL)
front = newNode;
else
rear->next = newNode;
rear = newNode;
}
}
template
void QueType::Dequeue(ItemType& item)
{
if (IsEmpty())
throw EmptyQueue();
else
{
NodeType* tempPtr;
tempPtr = front;
item = front->info;
front = front->next;
if (front == NULL)
rear = NULL;
delete tempPtr;
}
}
template
void QueType::MakeEmpty()
{
NodeType* tempPtr;
while (front != NULL)
{
tempPtr = front;
front = front->next;
delete tempPtr;
}
rear = NULL;
}
template
QueType::~QueType()
{
MakeEmpty();
}
Generate the Driver file (main.cpp) and check your program with the following outputs:
Operation to Be Tested and Description of Action Input Values Expected Output
• Given a set of coin values and an amount of money,
determine the minimum number of coins to make the given
amount of money. The input starts with an integer n,
specifying the number of coin types. Next n integers are the
coin values.
The final integer is the amount of money you
have to make. You can assume that the amount will always
be possible to make using the given coin types.
3 2 3 5 11
3 5 20 30 40
3
2
• Try the input 3 2 3 5 200. Explain your program’s outcome
with this input.