C++: Write a program that attempts to make the Radix Sort more practical: make it sort strings of a maximum length of 15. Have an array of strings. Then in the Radix Sort, create an array of LinkedQueue with 95 queues (95 are the printable characters starting with space). Those queues will be used to separate the data then combine them (i.e. bins). Randomly generate 10,000 strings with lengths from 1 to 15 (during the sort and with strings less than 15, treat all positions at the end that are not there as space). When generating random characters, have only 10% be digits, 10% special characters, and the rest, 80%, alphabetic characters, upper and lowercase. Before the sort, print out the first 10 strings, print out the middle 10 strings, and print last 10 strings. Then do the radix sort then print out the first 10 strings, print out the middle 10 strings, and print last 10 strings

@file LinkedQueue.h */

#ifndef LINKED_QUEUE_

#define LINKED_QUEUE_

#include

#include

#include "QueueInterface.h"

#include "Node.h"

#include "PrecondViolatedExcep.h"

template

class LinkedQueue : public QueueInterface

{

private:

// The queue is implemented as a chain of linked nodes that has

// two external pointers, a head pointer for front of the queue and

// a tail pointer for the back of the queue.

std::shared_ptr> backPtr;

std::shared_ptr> frontPtr;

public:

LinkedQueue();

LinkedQueue (const LinkedQueue& aQueue);

~LinkedQueue();

bool isEmpty() const;

bool enqueue(const ItemType& newEntry);

bool dequeue();

/** @throw PrecondViolatedExcep if the queue is empty */

ItemType peekFront() const throw(PrecondViolatedExcep);

void LastFirst();

int LineRemove(char letter);

}; // end LinkedQueue

#include "LinkedQueue.cpp"

#endif

/** @file LinkedQueue.cpp */

#ifndef LINKED_QUEUE_CPP

#define LINKED_QUEUE_CPP

#include "LinkedQueue.h"

#include

#include

template

LinkedQueue::LinkedQueue()

{ } // end default constructor

template

LinkedQueue::LinkedQueue(const LinkedQueue& aQueue)

{ // Implementation left as an exercise (Exercise 1).

auto origChainPtr = aQueue.frontPtr; // Points to nodes in original chain

// Using shared pointers initializes frontPtr/backPtr to nullPtr

if (origChainPtr != nullptr)

{

// Copy first node

frontPtr = std::make_shared>();

frontPtr->setItem(origChainPtr->getItem());

// Advance original-chain pointer

origChainPtr = origChainPtr->getNext();

// Copy remaining nodes

auto newChainTailPtr = frontPtr; // Points to last node in new chain

while (origChainPtr != nullptr)

{

// Get next item from original chain

ItemType nextItem = origChainPtr->getItem();

// Create a new node containing the next item

auto newNodePtr = std::make_shared>(nextItem);

// Link new node to end of new chain

newChainTailPtr->setNext(newNodePtr);

// Advance pointers

newChainTailPtr = newChainTailPtr->getNext();

origChainPtr = origChainPtr->getNext();

} // end while

newChainTailPtr->setNext(nullptr); // Flag end of chain

backPtr = newChainTailPtr;

} // end if

} // end copy constructor

template

LinkedQueue::~LinkedQueue()

{

//smart pointers will clean-up

backPtr == nullptr;

frontPtr == nullptr;

} // end destructor

template

bool LinkedQueue::isEmpty() const

{

return backPtr == nullptr;

} // end isEmpty

template

bool LinkedQueue::enqueue(const ItemType& newEntry)

{

auto newNodePtr = std::make_shared>(newEntry);

// Insert the new node

if (isEmpty())

frontPtr = newNodePtr; // Insertion into empty queue

else

backPtr->setNext(newNodePtr); // Insertion into nonempty queue

backPtr = newNodePtr; // New node is at back

return true;

} // end enqueue

template

bool LinkedQueue::dequeue()

{

bool result = false;

if (!isEmpty())

{

// Queue is not empty; delete front

auto nodeToDeletePtr = frontPtr;

if (frontPtr == backPtr)

{ // Special case: one node in queue

backPtr = nullptr;

frontPtr = nullptr;

}

else

{

frontPtr = frontPtr->getNext();

}

result = true;

} // end if

return result;

} // end dequeue

template

ItemType LinkedQueue::peekFront() const throw(PrecondViolatedExcep)

{

if (isEmpty())

throw PrecondViolatedExcep("getFront() called with empty queue.");

// Queue is not empty; return front

return frontPtr->getItem();

} // end peekFront

template

void LinkedQueue::LastFirst()

{

string name;

int length, x;

auto curPtr = frontPtr;

while (curPtr != nullptr)

{

while (curPtr != nullptr)

{

name = curPtr->getItem();

x = name.find(' ');

length = name.length();

if (x > 0)

{

name = name.substr(x+1, length) + ", " + name.substr(0, x);

curPtr->setItem(name);

}

curPtr = curPtr->getNext();

}

}

}

// End of implementation file.