Question

DO THIS IN C++:

Question: Write a function “reverse” in your queue class (Codes are given below. Use and modify them) that reverses the whole queue.

In your driver file (main.cpp), create an integer queue, push some values in it, call the reverse function to reverse the queue and then print the queue.

NOTE: A humble request, please don't just copy and paste the answer from chegg. I need more specific answer. Also I don't have much question remaining to ask. So please don't waste my question from copying the answer from another question of chegg since I have already seen the answers and I am looking for the more specific one which is done in C++ as well.. Thanks in Advance.

CODE:

QueueType.h

#ifndef QueueTYPE_H_INCLUDED

#define QueueTYPE_H_INCLUDED

class FullQueue

{};

class EmptyQueue

{};

template

class QueueType

{

    struct NodeType

    {

        ItemType info;

        NodeType* next;

    };

public:

    QueueType();

    ~QueueType();

    void MakeEmpty();

    void EnQueue(ItemType);

    void DeQueue(ItemType&);

    bool IsEmpty();

    bool IsFull();

private:

    NodeType *front, *rear;

};

#include "QueueType.tpp"

#endif // QueueTYPE_H_INCLUDED

QueueType.tpp

#include "QueueType.h"

#include

using namespace std;

template

QueueType::QueueType()

{

    front = NULL;

    rear = NULL;

}

template

bool QueueType::IsEmpty()

{

    return (front == NULL);

}

template

bool QueueType::IsFull()

{

    NodeType* location;

    try

    {

        location = new NodeType;

        delete location;

        return false;

    }

    catch(bad_alloc& exception)

    {

        return true;

    }

}

template

void QueueType::EnQueue(ItemType newItem)

{

    if (IsFull())

        throw FullQueue();

    else

    {

        NodeType* newNode;

        newNode = new NodeType;

        newNode->info = newItem;

        newNode->next = NULL;

        if (IsEmpty()) // (front == NULL)

            front = newNode;

        else

            rear->next = newNode;

        rear = newNode;

    }

}

template

void QueueType::DeQueue(ItemType& item)

{

    if (IsEmpty())

        throw EmptyQueue();

    else

    {

        item = front->info;

        NodeType* tempPtr;

        tempPtr = front;

        front = front->next;

        if (front == NULL)

            rear = NULL;

        delete tempPtr;

    }

}

template

void QueueType::MakeEmpty()

{

    NodeType* tempPtr;

    while (front != NULL)

    {

        tempPtr = front;

        front = front->next;

        delete tempPtr;

    }

    rear = NULL;

//        ItemType a = 0;

//        while(front!=NULL){

//            DeQueue(a);

//        }

}

template

QueueType::~QueueType()

{

    MakeEmpty();

}

Answer 1

Reversing a queue is very simple. Consider the following logic:

Consider a queue: 2 4 5 6  8 9 10

FRONT REAR

2

4

6

8

9

10

In this queue, front points at the first element 2 and rear points at the last element 10. In order to reverse the queue, we can swap these node pointers. Swap front and rear, so rear will point to 2 and front will point to 10. So now, 10 will be the first element as front points to 10 and 2 will be the last element as rear points to 2.

After swapping front and rear, the queue will look like this : 10 9 8 6 4 2

REAR FRONT

2

4

6

8

9

10

We can swap front and rear by the following logic :

Declare a temporary pointer temp.

1) Let temp point to the first element in the queue temp = front ( now both temp and front point to the first element 2 )

FRONT, temp REAR

2

4

6

8

9

10

2) Make front pointer point to the last element in the queue front = rear ( now both rear and front point to the last element 10)

temp REAR, FRONT

2

4

6

8

9

10

3) Make rear pointer point to the first element in the queue rear=temp ( now rear and temp both point to the first element 2 )

REAR, temp    FRONT

2

4

6

8

9

10

4) Delete the temp pointer as we no longer need it. delete temp ( now rear points to 2 and front points to 10 )

REAR FRONT

2

4

6

8

9

10

This is how the pointers front and rear are swapped and the queue is reversed.

I have added the reverseQ function in your code as follows:( The function is at the end )

#ifndef QueueTYPE_H_INCLUDED

#define QueueTYPE_H_INCLUDED

class FullQueue

{};

class EmptyQueue

{};

template

class QueueType

{

    struct NodeType

    {

        ItemType info;

        NodeType* next;

    };

public:

    QueueType();

    ~QueueType();

    void MakeEmpty();

    void EnQueue(ItemType);

    void DeQueue(ItemType&);

    bool IsEmpty();

    bool IsFull();

void reverseQ();

private:

    NodeType *front, *rear;

};

#include "QueueType.tpp"

#endif // QueueTYPE_H_INCLUDED

QueueType.tpp

#include "QueueType.h"

#include

using namespace std;

template

QueueType::QueueType()

{

    front = NULL;

    rear = NULL;

}

template

bool QueueType::IsEmpty()

{

    return (front == NULL);

}

template

bool QueueType::IsFull()

{

    NodeType* location;

    try

    {

        location = new NodeType;

        delete location;

        return false;

    }

    catch(bad_alloc& exception)

    {

        return true;

    }

}

template

void QueueType::EnQueue(ItemType newItem)

{

    if (IsFull())

        throw FullQueue();

    else

    {

        NodeType* newNode;

        newNode = new NodeType;

        newNode->info = newItem;

        newNode->next = NULL;

        if (IsEmpty()) // (front == NULL)

            front = newNode;

        else

            rear->next = newNode;

        rear = newNode;

    }

}

template

void QueueType::DeQueue(ItemType& item)

{

    if (IsEmpty())

        throw EmptyQueue();

    else

    {

        item = front->info;

        NodeType* tempPtr;

        tempPtr = front;

        front = front->next;

        if (front == NULL)

            rear = NULL;

        delete tempPtr;

    }

}

template

void QueueType::MakeEmpty()

{

    NodeType* tempPtr;

    while (front != NULL)

    {

        tempPtr = front;

        front = front->next;

        delete tempPtr;

    }

    rear = NULL;

//        ItemType a = 0;

//        while(front!=NULL){

//            DeQueue(a);

//        }

}

template

QueueType::~QueueType()

{

    MakeEmpty();

}

void QueueType::reverseQ()

{

  NodeType* tempPtr; // create a temporary pointer

tempPtr=front; //store front pointer in tempPtr , now tempPtr will also point to the first element in the queue

front=rear; // now front will point to the last element of the queue

rear=tempPtr; // rear will now point to the first element of queue as tempPtr points to the first element

// we have swapped front and rear pointers, so,now the queue is reversed

delete tempPtr; // we delete it as we no longer need tempPtr

}