CSE225L-Lab 9 Queue (Linked List) Solved

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 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 quetype.cpp

 

#include "quetype.h"

#include <iostream using namespace std;

 template <class ItemType QueType<ItemType::QueType()

{

    front = NULL;     rear = NULL;

}

template <class ItemType

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;         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()

{

    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.