plase slove it.donot copy paste from net.

Question

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:

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

Input Values:3 2 3 5 11 Expected Output 3

3 5 20 30 40 Expected Output 2

Try the input 3 2 3 5 200. Explain your program’s outcome with this input.

Answer 1

// m is size of coins array (number of different coins)

int minCoins(int coins[], int m, int V)

{

// base case

if (V == 0) return 0;

// Initialize result

int res = INT_MAX;

// Try every coin that has smaller value than V

for (int i=0; i<m; i++)

{

if (coins[i] <= V)

{

int sub_res = minCoins(coins, m, V-coins[i]);

// Check for INT_MAX to avoid overflow and see if

// result can minimized

if (sub_res != INT_MAX && sub_res + 1 < res)

res = sub_res + 1;

}

}

return res;

}

// Driver program to test above function

int main()

{

QueType<int> q;

if (q.IsEmpty()) { cout<< "Queue is Empty"<<endl; } else { cout << "Queue is not empty"<<endl; }

if (q.IsFull()) { cout<< "Queue is Full"<<endl; } else { cout << "Queue is not full"<<endl; }

int iNums[]={5,7,4,2};

for (int iLoop=0; iLoop<4; iLoop++)

{

cout << "pushing " << iNums[iLoop] << endl;

q.Enqueue(iNums[iLoop]);

}

if (q.IsEmpty()) { cout<< "Queue is Empty"<<endl; } else { cout << "Queue is not empty"<<endl; }

if (q.IsFull()) { cout<< "Queue is Full"<<endl; } else { cout << "Queue is not full"<<endl; }

for (int iLoop=0; iLoop<4; iLoop++)

{

int iCurIntNum;

q.Dequeue(iCurIntNum);

cout << " popped "<<iCurIntNum << endl;

}

int numCoins=-1;

while (numCoins<1)

{

cout << "Please input # of coins :>";

cin>>numCoins;

}

int* coins = new int[numCoins];

for (int iLoop=0; iLoop<numCoins; iLoop++)

{

cout << "Please input coin value :>";

cin >> coins[iLoop];

}

int V = -1;

while (V<1)

{

cout <<"Please input the final amount :>";

cin >>V;

}

cout << "Minimum coins required is "

<< minCoins(coins, numCoins, V);

return 0;

}