North South University - Spring 2023

Course: CSE225L Assessment: Lab 1 / HW 1 / PS 1

Section:06 NSU ID:2211364642 Name:Anindita Das Mishi

// Task-1 Codes

#ifndef UNSORTEDTYPE_H_INCLUDED
#define UNSORTEDTYPE_H_INCLUDED
const int MAX_ITEMS = 5;
template <class ItemType>
class UnsortedType
{
public :
UnsortedType();
void MakeEmpty();
bool IsFull();
int LengthIs();
void InsertItem(ItemType);
void DeleteItem(ItemType);
void RetrieveItem(ItemType&, bool&);
void ResetList();
void GetNextItem(ItemType&);
private:
int length;
ItemType info[MAX_ITEMS];
int currentPos;
};
#endif // UNSORTEDTYPE_H_INCLUDED

#include "unsortedType.h"
template <class ItemType>
UnsortedType<ItemType>::UnsortedType()
{
length = 0;
currentPos = -1;

N.B. Do not make any changes in the format of that template. Page 1
}
template <class ItemType>
void UnsortedType<ItemType>::MakeEmpty()
{
length = 0;
}
template <class ItemType>
bool UnsortedType<ItemType>::IsFull()
{
return (length == MAX_ITEMS);
}
template <class ItemType>
int UnsortedType<ItemType>::LengthIs()
{
return length;
}
template <class ItemType>
void UnsortedType<ItemType>::ResetList()
{
currentPos = -1;
}
template <class ItemType>
void
UnsortedType<ItemType>::GetNextItem(ItemType& item)
{
currentPos++;
item = info [currentPos] ;
}
template <class ItemType>
void
UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool &found)
{
int location = 0;
bool moreToSearch = (location < length);

N.B. Do not make any changes in the format of that template. Page 2
found = false;
while (moreToSearch && !found)
{
if(item == info[location])
{
found = true;
item = info[location];
}
else
{
location++;
moreToSearch = (location < length);
}
}
}
template <class ItemType>
void UnsortedType<ItemType>::InsertItem(ItemType item)
{
info[length] = item;
length++;
}
template <class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item)
{
int location = 0;
while (item != info[location])
location++;
info[location] = info[length - 1];
length--;
}

#include <iostream>
#include "src/unsortedType.cpp"

N.B. Do not make any changes in the format of that template. Page 3
using namespace std;

class studentInfo
{
public:
studentInfo() {}

studentInfo(int id, string name, float cgpa)

{
studentID=id;
studentName=name;
studentCGPA=cgpa;
}

void PrintInfo()
{
cout << studentID << ", " << studentName << ", " << studentCGPA <<
endl;
}

int GetStudentID()
{
return studentID;
}

void SetStudentID(int id)

{
studentID = id;
}

string GetStudentName()
{
return studentName;
}

N.B. Do not make any changes in the format of that template. Page 4
void SetStudentName(string& name)
{
studentName = name;
}

float GetStudentCGPA()
{
return studentCGPA;
}

void SetStudentCGPA(float cgpa)

{
studentCGPA = cgpa;
}

bool operator==(studentInfo& other)

{
return studentID == other.studentID;
}

bool operator!=(studentInfo& other)

{
return !(*this == other);
}

private:
int studentID;
string studentName;
float studentCGPA;
};

int main()
{

N.B. Do not make any changes in the format of that template. Page 5
UnsortedType<studentInfo> studentList;

studentList.InsertItem(studentInfo(15234, "Jon", 2.6));

studentList.InsertItem(studentInfo(13732, "Tyrion", 3.9));
studentList.InsertItem(studentInfo(13569, "Sandor", 1.2));
studentList.InsertItem(studentInfo(15467, "Ramsey", 2.3));
studentList.InsertItem(studentInfo(16285, "Arya", 3.1));

studentInfo recordToDelete(15467, "", 0);

studentList.DeleteItem(recordToDelete);

studentInfo recordToRetrieve(13569, "", 0);

bool found = false;
studentList.RetrieveItem(recordToRetrieve, found);
cout << "Item is " << (found ? "found" : "not found") << endl;
if (found)
{
recordToRetrieve.PrintInfo();
}

studentInfo student;
studentList.ResetList();
while (studentList.LengthIs() > 0)
{
studentList.GetNextItem(student);
student.PrintInfo();
}

return 0;
}

N.B. Do not make any changes in the format of that template. Page 6
// Task-2 Codes

#ifndef SORTEDTYPE_H_INCLUDED
#define SORTEDTYPE_H_INCLUDED
const int MAX_ITEMS = 5;
template <class ItemType>
class SortedType
{
public :
SortedType();
void MakeEmpty();
bool IsFull();
int LengthIs();
void InsertItem(ItemType);
void DeleteItem(ItemType);
void RetrieveItem(ItemType&,
bool&);
void ResetList();
void GetNextItem(ItemType&);

N.B. Do not make any changes in the format of that template. Page 7
private:
int length;
ItemType info[MAX_ITEMS];
int currentPos;
};
#endif // SORTEDTYPE_H_INCLUDED

#include "sortedtype.h"
template <class ItemType>
SortedType<ItemType>::SortedType()
{
length = 0;
currentPos = - 1;
}
template <class ItemType>
void SortedType<ItemType>::MakeEmpty()
{
length = 0;
}
template <class ItemType>
bool SortedType<ItemType>::IsFull()
{
return (length == MAX_ITEMS);
}
template <class ItemType>
int SortedType<ItemType>::LengthIs()
{
return length;
}
template <class ItemType>
void SortedType<ItemType>::ResetList()
{
currentPos = - 1;
}

N.B. Do not make any changes in the format of that template. Page 8
template <class ItemType>
void SortedType<ItemType>::GetNextItem(ItemType& item)
{
currentPos++;
item = info [currentPos];
}
template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
int location = 0;
bool moreToSearch = (location < length);
while (moreToSearch)
{
if(item > info[location])
{
location++;
moreToSearch = (location < length);
}
else if(item < info[location])
moreToSearch = false;
}
for (int index = length; index > location;
index--)
info[index] = info[index - 1];
info[location] = item;
length++;
}
template <class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
{
int location = 0;
while (item != info[location])
location++;
for (int index = location + 1; index < length;

N.B. Do not make any changes in the format of that template. Page 9
index++)
info[index - 1] = info[index];
length--;
}
template <class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
int midPoint, first = 0, last = length - 1;
bool moreToSearch = (first <= last);
found = false;
while (moreToSearch && !found)
{
midPoint = (first + last) / 2;
if(item < info[midPoint])
{
last = midPoint - 1;
moreToSearch = (first <= last);
}
else if(item > info[midPoint])
{
first = midPoint + 1;
moreToSearch = (first <= last);
}
else
{
found = true;
item = info[midPoint];
}
}
}

#include <iostream>
#include "src/sortedtype.cpp"
using namespace std;

N.B. Do not make any changes in the format of that template. Page 10
class TimeStamp
{
public:
TimeStamp(int s = 0, int m = 0, int h = 0)
{
seconds=s;
minutes=m;
hours=h;
}

void PrintTime() const

{
cout << hours << ":" << minutes << ":" << seconds << endl;
}

int GetSeconds()
{
return seconds;
}

void SetSeconds(int s)
{
seconds = s;
}

int GetMinutes()
{
return minutes;
}

void SetMinutes(int m)
{
minutes = m;

N.B. Do not make any changes in the format of that template. Page 11
}

int GetHours()
{
return hours;
}

void SetHours(int h)
{
hours = h;
}

bool operator==( TimeStamp& other)

{
return (seconds == other.seconds && minutes == other.minutes && hours
== other.hours);
}

bool operator!=(TimeStamp& other)

{
return !(*this == other);
}

bool operator<(TimeStamp& other)

{
if (hours != other.hours)
return hours < other.hours;
if (minutes != other.minutes)
return minutes < other.minutes;
return seconds < other.seconds;
}

bool operator>(TimeStamp& other)

{

N.B. Do not make any changes in the format of that template. Page 12
return other < *this;
}

bool operator<=(TimeStamp& other)

{
return !(other < *this);
}

bool operator>=(TimeStamp& other)

{
return !(*this < other);
}

private:
int seconds;
int minutes;
int hours;
};

int main()
{
SortedType<TimeStamp> timeList;

TimeStamp time1(23, 34, 15);

TimeStamp time2(2, 13, 13);
TimeStamp time3(12, 45, 43);
TimeStamp time4(17, 36, 25);
TimeStamp time5(20, 2, 52);

timeList.InsertItem(time1);
timeList.InsertItem(time2);
timeList.InsertItem(time3);
timeList.InsertItem(time4);
timeList.InsertItem(time5);

N.B. Do not make any changes in the format of that template. Page 13
TimeStamp currentTime;
int length = timeList.LengthIs();

timeList.ResetList();
for (int i = 0; i < length; ++i)
{
timeList.GetNextItem(currentTime);
currentTime.PrintTime();
}

return 0;
}

// Task-3 Codes

#ifndef UNSORTEDTYPE_H_INCLUDED
#define UNSORTEDTYPE_H_INCLUDED
template <class ItemType>
class UnsortedType

N.B. Do not make any changes in the format of that template. Page 14
{
struct NodeType
{
ItemType info;
NodeType* next;
};
public:
UnsortedType();
~UnsortedType();
bool IsFull();
int LengthIs();
void MakeEmpty();
void RetrieveItem(ItemType&, bool&);
void InsertItem(ItemType);
void DeleteItem(ItemType);
void ResetList();
void GetNextItem(ItemType&);
private:
NodeType* listData;
int length;
NodeType* currentPos;
};
#endif // UNSORTEDTYPE_H_INCLUDED

#include "unsortedtype.h"
#include <iostream>
using namespace std;
template <class ItemType>
UnsortedType<ItemType>::UnsortedType()
{
length = 0;
listData = NULL;
currentPos = NULL;
}

N.B. Do not make any changes in the format of that template. Page 15
template <class ItemType>
int UnsortedType<ItemType>::LengthIs()
{
return length;
}
template<class ItemType>
bool UnsortedType<ItemType>::IsFull()
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc& exception)
{
return true;
}
}
template <class ItemType>
void UnsortedType<ItemType>::InsertItem(ItemType item)
{
NodeType* location;
location = new NodeType;
location->info = item;
location->next = listData;
listData = location;
length++;
}
template <class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item)
{
NodeType* location = listData;

N.B. Do not make any changes in the format of that template. Page 16
NodeType* tempLocation;
if (item == listData->info)
{
tempLocation = location;
listData = listData->next;
}
else
{
while (!(item==(location->next)->info))
location = location->next;
tempLocation = location->next;
location->next = (location->next)->next;
}
delete tempLocation;
length--;
}
template <class ItemType>
void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
NodeType* location = listData;
bool moreToSearch = (location != NULL);
found = false;
while (moreToSearch && !found)
{
if (item == location->info)
found = true;
else
{
location = location->next;
moreToSearch = (location != NULL);
}
}
}
template <class ItemType>

N.B. Do not make any changes in the format of that template. Page 17
void UnsortedType<ItemType>::MakeEmpty()
{
NodeType* tempPtr;
while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}
template <class ItemType>
UnsortedType<ItemType>::~UnsortedType()
{
MakeEmpty();
}
template <class ItemType>
void UnsortedType<ItemType>::ResetList()
{
currentPos = NULL;
}
template <class ItemType>
void UnsortedType<ItemType>::GetNextItem(ItemType& item)
{
if (currentPos == NULL)
currentPos = listData;
else
currentPos = currentPos->next;
item = currentPos->info;
}

#include <iostream>
#include "src\unsortedtype.cpp"
using namespace std;

N.B. Do not make any changes in the format of that template. Page 18
int main()
{

UnsortedType<int> list1, list2, merged;

int n, v;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> v;
list1.InsertItem(v);
}

cin >> n;
for (int i = 0; i < n; i++)
{
cin >> v;
list2.InsertItem(v);
}

int value1, value2;

int index1 = list1.LengthIs();
int index2 = list2.LengthIs();
list1.GetNextItem(value1);
list2.GetNextItem(value2);

while (index1 > 0 && index2 > 0)

{
if (value1 > value2)
{
merged.InsertItem(value1);
index1--;
if (index1 > 0)

N.B. Do not make any changes in the format of that template. Page 19
list1.GetNextItem(value1);
}
else if (value2 > value1)
{
merged.InsertItem(value2);
index2--;
if (index2 > 0)
list2.GetNextItem(value2);
}
else
{
merged.InsertItem(value1);
merged.InsertItem(value2);
index1--;
index2--;
if (index1 > 0)
list1.GetNextItem(value1);
if (index2 > 0)
list2.GetNextItem(value2);
}
}

while (index1 > 0)

{
merged.InsertItem(value1);
index1--;
if (index1 > 0)
list1.GetNextItem(value1);
}

while (index2 > 0)

{
merged.InsertItem(value2);
index2--;

N.B. Do not make any changes in the format of that template. Page 20
if (index2 > 0)
list2.GetNextItem(value2);
}

int value_merged;
int index_merged = merged.LengthIs() - 1;

while (index_merged >= 0)

{
merged.GetNextItem(value_merged);
cout << value_merged << ' ';
index_merged--;
}
cout << endl;

return 0;
}

// Task-4 Codes

N.B. Do not make any changes in the format of that template. Page 21
#ifndef STACKTYPE_H_INCLUDED
#define STACKTYPE_H_INCLUDED
const int MAX_ITEMS = 5;
class FullStack
{};
class EmptyStack
{};
template <class ItemType>
class StackType
{
public:
StackType();
bool IsFull();
bool IsEmpty();
void Push(ItemType);
void Pop();
ItemType Top();
private:
int top;
ItemType items[MAX_ITEMS];
};
#endif // STACKTYPE_H_INCLUDED

#include "StackType.h"
template <class ItemType>
StackType<ItemType>::StackType()
{
top = -1;
}
template <class ItemType>
bool StackType<ItemType>::IsEmpty()
{
return (top == -1);

N.B. Do not make any changes in the format of that template. Page 22
}
template <class ItemType>
bool StackType<ItemType>::IsFull()
{
return (top == MAX_ITEMS-1);
}
template <class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
if( IsFull() ) throw FullStack();
top++;
items[top] = newItem;
}
template <class ItemType>
void StackType<ItemType>::Pop()
{
if( IsEmpty() ) throw EmptyStack();
top--;
}
template <class ItemType>
ItemType StackType<ItemType>::Top()
{
if (IsEmpty()) throw EmptyStack();
return items[top];
}

#include <iostream>
#include "src\stackType.cpp"

using namespace std;

bool IsBalanced(const char* expression) {

StackType<char> stack;
char ch;

N.B. Do not make any changes in the format of that template. Page 23
bool isBalanced = true;

for (int i = 0; expression[i] != '\0'; i++) {

if (expression[i] == '(' || expression[i] == '{' || expression[i] ==
'[') {
stack.Push(expression[i]);
} else if (expression[i] == ')' || expression[i] == '}' ||
expression[i] == ']') {
if (stack.IsEmpty()) {
isBalanced = false;
break;
} else {
ch = stack.Top();
stack.Pop();

if ((ch == '(' && expression[i] != ')') || (ch == '{' &&

expression[i] != '}') || (ch == '[' && expression[i] != ']')) {
isBalanced = false;
break;
}
}
}
}

if (!stack.IsEmpty()) {
isBalanced = false;
}

return isBalanced;
}

int main() {
const int MAX_SIZE = 100;
char expression[MAX_SIZE];

N.B. Do not make any changes in the format of that template. Page 24
cout << "Enter a string of parentheses: ";
cin.getline(expression, MAX_SIZE);

if (IsBalanced(expression)) {
cout << "Balanced" << endl;
} else {
cout << "Not balanced" << endl;
}

return 0;
}

// Task-5 Codes

#ifndef QUETYPE_H_INCLUDED
#define QUETYPE_H_INCLUDED
class FullQueue
{};
class EmptyQueue

N.B. Do not make any changes in the format of that template. Page 25
{};
template<class ItemType>
class QueType
{
public:
QueType();
QueType(int max);
~QueType();
void MakeEmpty();
bool IsEmpty();
bool IsFull();
void Enqueue(ItemType);
void Dequeue(ItemType&);
private:
int front;
int rear;
ItemType* items;
int maxQue;
};
#endif // QUETYPE_H_INCLUDED

#include "quetype.h"
template<class ItemType>
QueType<ItemType>::QueType(int max)
{
maxQue = max + 1;
front = maxQue - 1;
rear = maxQue - 1;
items = new ItemType[maxQue];
}
template<class ItemType>
QueType<ItemType>::QueType()
{
maxQue = 501;

N.B. Do not make any changes in the format of that template. Page 26
front = maxQue - 1;
rear = maxQue - 1;
items = new ItemType[maxQue];
}
template<class ItemType>
QueType<ItemType>::~QueType()
{
delete [] items;
}
template<class ItemType>
void QueType<ItemType>::MakeEmpty()
{
front = maxQue - 1;
rear = maxQue - 1;
}
template<class ItemType>
bool QueType<ItemType>::IsEmpty()
{
return (rear == front);
}
template<class ItemType>
bool QueType<ItemType>::IsFull()
{
return ((rear+1)%maxQue == front);
}
template<class ItemType>
void QueType<ItemType>::Enqueue(ItemType newItem)
{
if (IsFull())
throw FullQueue();
else
{
rear = (rear +1) % maxQue;
items[rear] = newItem;

N.B. Do not make any changes in the format of that template. Page 27
}
}
template<class ItemType>
void QueType<ItemType>::Dequeue(ItemType& item)
{
if (IsEmpty())
throw EmptyQueue();
else
{
front = (front + 1) % maxQue;
item = items[front];
}
}

#include <iostream>
using namespace std;
#include "src\quetype.cpp"

void printBinaryNumbers(int n) {
for (int i = 1; i <= n; i++) {
int num = i;
int binary = 0;
int base = 1;

while (num > 0) {

binary += (num % 2) * base;
num /= 2;
base *= 10;
}

cout << binary << endl;

}
}

N.B. Do not make any changes in the format of that template. Page 28
int main() {
int n;
cout << "Enter a number (n): ";
cin >> n;

printBinaryNumbers(n);

return 0;
}

// Task-6 Codes
#ifndef STACKTYPE_H_INCLUDED
#define STACKTYPE_H_INCLUDED
class FullStack
{};
class EmptyStack
{};
template <class ItemType>

N.B. Do not make any changes in the format of that template. Page 29
class StackType
{
struct NodeType
{
ItemType info;
NodeType* next;
};
public:
StackType();
~StackType();
void Push(ItemType);
void Pop();
ItemType Top();
bool IsEmpty();
bool IsFull();
private:
NodeType* topPtr;
};
#endif // STACKTYPE_H_INCLUDED

#include <iostream>
#include "stacktype.h"
using namespace std;
template <class ItemType>
StackType<ItemType>::StackType()
{
topPtr = NULL;
}
template <class ItemType>
bool StackType<ItemType>::IsEmpty()
{
return (topPtr == NULL);
}
template <class ItemType>

N.B. Do not make any changes in the format of that template. Page 30
ItemType StackType<ItemType>::Top()
{
if (IsEmpty())
throw EmptyStack();
else
return topPtr->info;
}
template <class ItemType>
bool StackType<ItemType>::IsFull()
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc& exception)
{
return true;
}
}
template <class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
if (IsFull())
throw FullStack();
else
{
NodeType* location;
location = new NodeType;
location->info = newItem;
location->next = topPtr;
topPtr = location;

N.B. Do not make any changes in the format of that template. Page 31
}
}
template <class ItemType>
void StackType<ItemType>::Pop()
{
if (IsEmpty())
throw EmptyStack();
else
{
NodeType* tempPtr;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}
template <class ItemType>
StackType<ItemType>::~StackType()
{
NodeType* tempPtr;
while (topPtr != NULL)
{
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}
#include <iostream>
#include "src\stacktype.cpp"
using namespace std;

bool IsOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}

N.B. Do not make any changes in the format of that template. Page 32
int Precedence(char c) {
if (c == '+' || c == '-')
return 1;
else if (c == '*' || c == '/')
return 2;
return 0;
}

bool IsOperand(char c) {
return (c >= '0' && c <= '9');
}

double PerformOperation(char operation, double operand1, double operand2) {

double result;
switch (operation) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
return result;
}

double EvaluateExpression(const char* expression) {

StackType<double> operandStack;

N.B. Do not make any changes in the format of that template. Page 33
StackType<char> operatorStack;

while (*expression) {
if (*expression == ' ') {
expression++;
continue;
}

if (IsOperand(*expression)) {
double operand = 0;
while (IsOperand(*expression)) {
operand = operand * 10 + (*expression - '0');
expression++;
}
operandStack.Push(operand);
} else if (IsOperator(*expression)) {
while (!operatorStack.IsEmpty() && operatorStack.Top() != '(' &&
Precedence(*expression) <= Precedence(operatorStack.Top()))
{
double operand2 = operandStack.Top();
operandStack.Pop();
double operand1 = operandStack.Top();
operandStack.Pop();
char operation = operatorStack.Top();
operatorStack.Pop();
double result = PerformOperation(operation, operand1,
operand2);
operandStack.Push(result);
}
operatorStack.Push(*expression);
expression++;
} else if (*expression == '(') {
operatorStack.Push(*expression);
expression++;
} else if (*expression == ')') {

N.B. Do not make any changes in the format of that template. Page 34
while (!operatorStack.IsEmpty() && operatorStack.Top() != '(') {
double operand2 = operandStack.Top();
operandStack.Pop();
double operand1 = operandStack.Top();
operandStack.Pop();
char operation = operatorStack.Top();
operatorStack.Pop();
double result = PerformOperation(operation, operand1,
operand2);
operandStack.Push(result);
}
if (!operatorStack.IsEmpty() && operatorStack.Top() == '(')
operatorStack.Pop();
expression++;
} else {
throw EmptyStack();
}
}

while (!operatorStack.IsEmpty()) {
double operand2 = operandStack.Top();
operandStack.Pop();
double operand1 = operandStack.Top();
operandStack.Pop();
char operation = operatorStack.Top();
operatorStack.Pop();
double result = PerformOperation(operation, operand1, operand2);
operandStack.Push(result);
}

return operandStack.Top();
}

int main() {

N.B. Do not make any changes in the format of that template. Page 35
const int MAX_EXPRESSION_LENGTH = 100;
char infixExpression[MAX_EXPRESSION_LENGTH];

cout << "Enter an infix expression: ";

cin.getline(infixExpression, MAX_EXPRESSION_LENGTH);

try {
double result = EvaluateExpression(infixExpression);
cout << "Result: " << result << endl;
} catch (EmptyStack&) {
cout << "Invalid expression" << endl;
}

return 0;
}

// Task-7 Codes
#ifndef QUETYPE_H_INCLUDED
#define QUETYPE_H_INCLUDED

N.B. Do not make any changes in the format of that template. Page 36
class FullQueue
{};
class EmptyQueue
{};
template <class ItemType>
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
#include "quetype.h"
#include <iostream>
using namespace std;
template <class ItemType>
QueType<ItemType>::QueType()
{
front = NULL;
rear = NULL;
}
template <class ItemType>

N.B. Do not make any changes in the format of that template. Page 37
bool QueType<ItemType>::IsEmpty()
{
return (front == NULL);
}
template<class ItemType>
bool QueType<ItemType>::IsFull()
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc& exception)
{
return true;
}
}
template <class ItemType>
void QueType<ItemType>::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;

N.B. Do not make any changes in the format of that template. Page 38
rear = newNode;
}
}
template <class ItemType>
void QueType<ItemType>::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 <class ItemType>
void QueType<ItemType>::MakeEmpty()
{
NodeType* tempPtr;
while (front != NULL)
{
tempPtr = front;
front = front->next;
delete tempPtr;
}
rear = NULL;
}
template <class ItemType>
QueType<ItemType>::~QueType()
{

N.B. Do not make any changes in the format of that template. Page 39
MakeEmpty();
}
#include <iostream>
#include "src\quetype.cpp"
using namespace std;

int main()
{
QueType<int> queue, cost;
int size;
cout<<"Number of coin type:";
cin >> size;
int array[size];
cout<<"Coin values:";
for (int i = 0; i < size; i++)
{
cin >> array[i];
}
int target;
cout<<"Amount of money:";
cin >> target;
for (int i = 0; i < size; i++)
{
queue.Enqueue(array[i]);
cost.Enqueue(1);
}
int temp, count = 0;
cout<<"The minimum number of coins required:";
while (true)
{
queue.Dequeue(temp);
cost.Dequeue(count);
if (temp == target)
break;

N.B. Do not make any changes in the format of that template. Page 40
else
{
count++;
for (int i = 0; i < size; i++)
{
queue.Enqueue(temp + array[i]);
cost.Enqueue(count);
}
}
}
cout << count << endl;
return 0;
}

N.B. Do not make any changes in the format of that template. Page 41
N.B. Do not make any changes in the format of that template. Page 42