List & Queue help. I need help implementing the countOff() method in my QueueMai

Question

List & Queue help. I need help implementing the countOff() method in my QueueMain.cpp program.

Here is the problem to solve:

During the Civil War, a group of Confederate officers are in a clandestine meeting when they suddenly discover they are surrounded by an overwhelming Union force. There is absolutely no hope for victory without reinforcements, and Stonewall Jackson's horse, Little Sorrel, is the only horse available that can be used to escape and summon help. The officers agree to a pact to determine which of them is to go for help.

The officers form a queue and they pick a number from a hat. Beginning with the first officer in the queue, they begin to count. As each officer counts off, he moves to the end of the queue. When the count reaches the number that was picked, that officer is removed from the queue, and the count begins again with the next man. Once an officer is removed from the queue, he is no longer counted. The last officer that remains in the queue is the one that rides away on Little Sorrel to summon help.

The process continues in this way until only one officer remains in the queue. The last officer remaining in the queue is the one that goes for help.

In the QueueMain.cpp, the countOff() method displays the name of each officer removed from the queue, in the order in which they are removed, and displays the name of the officer that goes for help.

The countOff() method cannot create a data structure; it MUST use the LinkedQueue data structure named officers, which is passed as an argument. ONLY the countOff() method should be modified. No other modifications to the included files should be made. An assignment without using the LinkedQueue receives 0.

You will use the text file, officers.txt, in the Lab6Files folder to test your program. Your output should not be the same as the example shown above in the description because you use the full set of data from the text file in the folder and test the program with different cutoff numbers.

Your output (including the order of the officers leaving the queue) MUST be the same as of the following:

Officers in original queue:
Bate, William Brimage, Major General
Beauregard, Pierre Gustave Toutant, General
Bowen, John Stevens, Major General
Bragg, Braxton, General
Brown, John Calvin, Major General
Buckner, Simon Bolivar, Major General
Cheatham, Benjamin Franklin, Major General
Cleburne, Patrick Ronayne, Major General
Cooper, Samuel, General
Early, Jubal Anderson, Lieutenant General
Elzey, Arnold, Major General
Ewell, Richard Stoddert, Lieutenant General
Forney, John Horace, Major General
Forrest, Nathan Bedford, Lieutenant General
French, Samuel Gibbs, Major General
Gardner, Franklin, Major General
Gordon, John Brown, Major General
Hardee, William Joseph, Lieutenant General
Hays, Harry Thompson, Major General
Heth, Henry, Major General
Hill, Ambrose Powell, Lieutenant General, Corps Commander
Hindman, Thomas Carmichael, Major General
Hoke, Robert Frederick, Major General
Hood, John Bell, General
Huger, Benjamin, Major General
Jackson, Thomas Jonathan 'Stonewall', Major General
Johnson, Bushrod Rust, Major General
Johnson, Edward, Major General
Johnston, Albert Sidney, General
Johnston, Joseph Eggleston, General
Jones, Samuel, Major General
Kershaw, Joseph Brevard, Major General
Lee, Fitzhugh, Major General
Lee, George Washington Custis, Major General
Lee, Robert Edward, General
Lee, William Henry Fitzhugh, Major General
Longstreet, James, Lieutenant General
Loring, William Wing, Major General
Lovell, Mansfield, Major General
Magruder, John Bankhead, Major General
Mahone, William, Major General
Marie, Camille Armand Jules, Major General
Marmaduke, John Sappington, Major General
Maury, Dabney Herndon, Major General
McLaws, Lafayette, Major General
Pender, William Dorsey, Major General
Pike, Albert, Brigadier General
Polk, Leonidas, Major General
Price, Sterling, Major General
Rodes, Robert Emmett, Major General
Rosser, Thomas Lafayette, Major General
Smith, Edmund Kirby, General
Smith, Martin Luther, Major General
Stevenson, Carter Littlepage, Major General
Stuart, James Ewell Brown 'JEB', General
Taylor, Richard, Lieutenant General
Van Dorn, Earl, Major General
Walthall, Edward Cary, Major General
Wharton, John Austin, Major General
Wheeler, Joseph, Major General
Wilcox, Cadmus Marcellus, Major General
Withers, Jones Mitchell, Major General

Count is: 5
The officers leaving the queue are:
Brown, John Calvin, Major General
Early, Jubal Anderson, Lieutenant General
French, Samuel Gibbs, Major General
Heth, Henry, Major General
Huger, Benjamin, Major General
Johnston, Joseph Eggleston, General
Lee, Robert Edward, General
Magruder, John Bankhead, Major General
McLaws, Lafayette, Major General
Rodes, Robert Emmett, Major General
Stuart, James Ewell Brown 'JEB', General
Wheeler, Joseph, Major General
Bowen, John Stevens, Major General
Cooper, Samuel, General
Gardner, Franklin, Major General
Hindman, Thomas Carmichael, Major General
Johnson, Edward, Major General
Lee, George Washington Custis, Major General
Mahone, William, Major General
Pike, Albert, Brigadier General
Smith, Martin Luther, Major General
Wharton, John Austin, Major General
Bragg, Braxton, General
Ewell, Richard Stoddert, Lieutenant General
Hays, Harry Thompson, Major General
Johnson, Bushrod Rust, Major General
Lee, William Henry Fitzhugh, Major General
Marmaduke, John Sappington, Major General
Rosser, Thomas Lafayette, Major General
Walthall, Edward Cary, Major General
Buckner, Simon Bolivar, Major General
Forrest, Nathan Bedford, Lieutenant General
Hood, John Bell, General
Lee, Fitzhugh, Major General
Maury, Dabney Herndon, Major General
Stevenson, Carter Littlepage, Major General
Bate, William Brimage, Major General
Forney, John Horace, Major General
Jackson, Thomas Jonathan 'Stonewall', Major General
Loring, William Wing, Major General
Price, Sterling, Major General
Withers, Jones Mitchell, Major General
Gordon, John Brown, Major General
Jones, Samuel, Major General
Pender, William Dorsey, Major General
Wilcox, Cadmus Marcellus, Major General
Hardee, William Joseph, Lieutenant General
Longstreet, James, Lieutenant General
Taylor, Richard, Lieutenant General
Elzey, Arnold, Major General
Lovell, Mansfield, Major General
Beauregard, Pierre Gustave Toutant, General
MM§MJohnston, Albert Sidney, General
Van Dorn, Earl, Major General
Kershaw, Joseph Brevard, Major General
Cleburne, Patrick Ronayne, Major General
Smith, Edmund Kirby, General
Polk, Leonidas, Major General
Cheatham, Benjamin Franklin, Major General
Hoke, Robert Frederick, Major General
Marie, Camille Armand Jules, Major General

The officer going for help is:
Hill, Ambrose Powell, Lieutenant General, Corps Commander


Count is: 8
The officers leaving the queue are:
Cleburne, Patrick Ronayne, Major General
Gardner, Franklin, Major General
Hood, John Bell, General
Kershaw, Joseph Brevard, Major General
Magruder, John Bankhead, Major General
Polk, Leonidas, Major General
Taylor, Richard, Lieutenant General
Beauregard, Pierre Gustave Toutant, General
Elzey, Arnold, Major General
Heth, Henry, Major General
Johnston, Albert Sidney, General
Loring, William Wing, Major General
Pike, Albert, Brigadier General
Van Dorn, Earl, Major General
Bragg, Braxton, General
Forrest, Nathan Bedford, Lieutenant General
Huger, Benjamin, Major General
Lee, Robert Edward, General
McLaws, Lafayette, Major General
Stuart, James Ewell Brown 'JEB', General
Brown, John Calvin, Major General
Gordon, John Brown, Major General
Johnson, Edward, Major General
Mahone, William, Major General
Smith, Edmund Kirby, General
Bate, William Brimage, Major General
French, Samuel Gibbs, Major General
Johnston, Joseph Eggleston, General
Marmaduke, John Sappington, Major General
Walthall, Edward Cary, Major General
Cooper, Samuel, General
Hoke, Robert Frederick, Major General
Lovell, Mansfield, Major General
Stevenson, Carter Littlepage, Major General
Early, Jubal Anderson, Lieutenant General
Johnson, Bushrod Rust, Major General
Pender, William Dorsey, Major General
Withers, Jones Mitchell, Major General
Hill, Ambrose Powell, Lieutenant General, Corps Commander
Marie, Camille Armand Jules, Major General
Wilcox, Cadmus Marcellus, Major General
Hindman, Thomas Carmichael, Major General
Price, Sterling, Major General
Cheatham, Benjamin Franklin, Major General
Lee, George Washington Custis, Major General
Wheeler, Joseph, Major General
Jones, Samuel, Major General
Wharton, John Austin, Major General
Lee, Fitzhugh, Major General
Buckner, Simon Bolivar, Major General
Maury, Dabney Herndon, Major General
Hays, Harry Thompson, Major General
Ewell, Richard Stoddert, Lieutenant General
Smith, Martin Luther, Major General
Rosser, Thomas Lafayette, Major General
Bowen, John Stevens, Major General
Hardee, William Joseph, Lieutenant General
Longstreet, James, Lieutenant General
Lee, William Henry Fitzhugh, Major General
Forney, John Horace, Major General
Rodes, Robert Emmett, Major General

The officer going for help is:
Jackson, Thomas Jonathan 'Stonewall', Major General

QueueInterface.h

#ifndef _QUEUE_INTERFACE
#define _QUEUE_INTERFACE

template<class ItemType>
class QueueInterface

{
public:
/** Sees whether this queue is empty.
@return True if the queue is empty, or false if not. */
virtual bool isEmpty() const = 0;

/** Adds a new entry to the back of this queue.
@post If the operation was successful, newEntry is at the
back of the queue.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful or false if not. */
virtual bool enqueue(const ItemType& newEntry) = 0;

/** Removes the front of this queue.
@post If the operation was successful, the front of the queue
has been removed.
@return True if the removal is successful or false if not. */
virtual bool dequeue() = 0;

/** Returns the front of this queue.
@pre The queue is not empty.
@post The front of the queue has been returned, and the
queue is unchanged.
@return The front of the queue. */
virtual ItemType peekFront() const = 0;
}; // end QueueInterface
#endif

Node.h

#ifndef _NODE
#define _NODE

template<class ItemType>
class Node
{
private:
ItemType item; // A data item
Node<ItemType>* next; // Pointer to next node

public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node<ItemType>* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node<ItemType>* nextNodePtr);
ItemType getItem() const ;
Node<ItemType>* getNext() const ;
}; // end Node

#include "Node.cpp"
#endif

LinkedQueue.h

#ifndef _LINKED_QUEUE

#define _LINKED_QUEUE

#include "QueueInterface.h"

#include "Node.h"

#include "PrecondViolatedExcep.h"

template<class ItemType>

class LinkedQueue : public QueueInterface<ItemType>

{

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.

Node<ItemType>* backPtr;

Node<ItemType>* 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);

}; // end LinkedQueue

#include "LinkedQueue.cpp"

#endif

PrecondViolatedExcep.h

#ifndef _PRECOND_VIOLATED_EXCEP
#define _PRECOND_VIOLATED_EXCEP

#include <stdexcept>
#include <string>

using namespace std;

class PrecondViolatedExcep : public logic_error
{
public:
PrecondViolatedExcep(const string& message = "");
}; // end PrecondViolatedExcep
#endif

Node.cpp

#include "Node.h"
#include <cstddef>

template<class ItemType>
Node<ItemType>::Node() : next(nullptr)
{
} // end default constructor

template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor

template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem, Node<ItemType>* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor

template<class ItemType>
void Node<ItemType>::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem

template<class ItemType>
void Node<ItemType>::setNext(Node<ItemType>* nextNodePtr)
{
next = nextNodePtr;
} // end setNext

template<class ItemType>
ItemType Node<ItemType>::getItem() const
{
return item;
} // end getItem

template<class ItemType>
Node<ItemType>* Node<ItemType>::getNext() const
{
return next;
} // end getNext

LinkedQueue.cpp

#include "LinkedQueue.h"  

#include <cassert>

template<class ItemType>

LinkedQueue<ItemType>::LinkedQueue()

{

backPtr = nullptr;

frontPtr = nullptr;

} // end default constructor

template<class ItemType>

LinkedQueue<ItemType>::LinkedQueue(const LinkedQueue& aQueue)

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

Node<ItemType>* origChainPtr = aQueue.frontPtr; // Points to nodes in original chain

if (origChainPtr == nullptr)

{

frontPtr = nullptr; // Original queue is empty

backPtr = nullptr;

}

else

{

// Copy first node

frontPtr = new Node<ItemType>();

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

  

// Advance original-chain pointer

origChainPtr = origChainPtr->getNext();

// Copy remaining nodes

Node<ItemType>* newChainPtr = 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

Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem);  

// Link new node to end of new chain

newChainPtr->setNext(newNodePtr);

// Advance pointers

newChainPtr = newChainPtr->getNext();

origChainPtr = origChainPtr->getNext();

} // end while

  

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

backPtr = newChainPtr;

} // end if

} // end copy constructor

template<class ItemType>

LinkedQueue<ItemType>::~LinkedQueue()

{

while (!isEmpty())

dequeue();

assert ( (backPtr == nullptr) && (frontPtr == nullptr) );

} // end destructor

template<class ItemType>

bool LinkedQueue<ItemType>::isEmpty() const

{

return backPtr == nullptr;

} // end isEmpty

template<class ItemType>

bool LinkedQueue<ItemType>::enqueue(const ItemType& newEntry)

{

Node<ItemType>* newNodePtr = new Node<ItemType>(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<class ItemType>

bool LinkedQueue<ItemType>::dequeue()

{

bool result = false;

if (!isEmpty())

{

// Queue is not empty; delete front

Node<ItemType>* nodeToDeletePtr = frontPtr;

if (frontPtr == backPtr)

{ // Special case: one node in queue

frontPtr = nullptr;

backPtr = nullptr;

}

else

frontPtr = frontPtr->getNext();

// Return deleted node to system

nodeToDeletePtr->setNext(nullptr);

delete nodeToDeletePtr;

nodeToDeletePtr = nullptr;

  

result = true;

} // end if

return result;

} // end dequeue

template<class ItemType>

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

{

if (isEmpty())

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

// Queue is not empty; return front

return frontPtr->getItem();

} // end peekFront

// End of implementation file.

PrecondViolatedExcep.cpp

#include "PrecondViolatedExcep.h"  

PrecondViolatedExcep::PrecondViolatedExcep(const string& message): logic_error("Precondition Violated Exception: " + message)
{
} // end constructor

// End of implementation file.

QueueMain.cpp

#include <iostream>

#include <fstream>

#include <cstdlib>

#include <string>

#include <stdexcept>

#include <cassert>

#include "LinkedQueue.h"

using namespace std;

/**

* Name of input file containing officer names

*/

const char INPUT_FILE[] = "officers.txt";

/**

* Inputs data from a text file and places each officer's name into the

* queue passed as a parameter.

* @param officers - dynamic queue of Confederate officers in the Civil War

*/

void loadQueue(LinkedQueue<string> &officers);

/**

* Displays a list of officers removed from the queue and also displays

* the name of the officer going for help. Retrieves officers from the

* officers queue, one at a time, counting as each is retrieved. If the

* count is not equal to hatNumber, the officer is put back into the

* queue. When the count reaches hatNumber, that officer is removed from

* the queue permanently (i.e., not put back into the queue), and the

* officer's name is output to the screen. The last officer remaining in

* the queue is the one shown as going for help.

* @param officers - dynamic queue of Confederate officers in the Civil War

* @param hatNumber - the number drawn from the hat, used to count off

*/

void countOff (LinkedQueue<string> officers, int hatNumber);

int main (void)

{

ifstream inFile(INPUT_FILE); // declare and open the input file

int count; // number used for counting off

LinkedQueue<string> officers; // queue containing officer names

string officerName; // name of officer in front of queue

string firstName; // name of first officer in original queue

loadQueue(officers);

// Display list of officers in original queue

cout << "Officers in original queue: " << endl;

firstName = officers.peekFront();

cout << firstName << endl;

officers.dequeue();

officers.enqueue(firstName);

officerName = officers.peekFront();

while (firstName != officerName)

{

cout << officerName << endl;

officers.dequeue();

officers.enqueue(officerName);

officerName = officers.peekFront();

}

// Test countOff() method using various numbers drawn from the hat

count = 5;

cout << endl << endl<< "Count is: " << count << endl;

countOff (officers, count);

count = 8;

cout << endl << endl << "Count is: " << count << endl;

countOff (officers, count);

return EXIT_SUCCESS;

}

void loadQueue(LinkedQueue<string> &officers)

{

ifstream inFile(INPUT_FILE); // declare and open the input file

string officerName; // name of officer input from file

if (!inFile)

cout << "Error opening file for input: " << INPUT_FILE << endl;

else

{

getline (inFile, officerName);

while (!inFile.eof())

{

officers.enqueue(officerName);

getline (inFile, officerName);

}

inFile.close();

}

}

void countOff (LinkedQueue<string> officers, int count)

{

// This method must be implemented

}

officers

Bate, William Brimage, Major General
Beauregard, Pierre Gustave Toutant, General
Bowen, John Stevens, Major General
Bragg, Braxton, General
Brown, John Calvin, Major General
Buckner, Simon Bolivar, Major General
Cheatham, Benjamin Franklin, Major General
Cleburne, Patrick Ronayne, Major General
Cooper, Samuel, General
Early, Jubal Anderson, Lieutenant General
Elzey, Arnold, Major General
Ewell, Richard Stoddert, Lieutenant General
Forney, John Horace, Major General
Forrest, Nathan Bedford, Lieutenant General
French, Samuel Gibbs, Major General
Gardner, Franklin, Major General
Gordon, John Brown, Major General
Hardee, William Joseph, Lieutenant General
Hays, Harry Thompson, Major General
Heth, Henry, Major General
Hill, Ambrose Powell, Lieutenant General, Corps Commander
Hindman, Thomas Carmichael, Major General
Hoke, Robert Frederick, Major General
Hood, John Bell, General
Huger, Benjamin, Major General
Jackson, Thomas Jonathan 'Stonewall', Major General
Johnson, Bushrod Rust, Major General
Johnson, Edward, Major General
Johnston, Albert Sidney, General
Johnston, Joseph Eggleston, General
Jones, Samuel, Major General
Kershaw, Joseph Brevard, Major General
Lee, Fitzhugh, Major General
Lee, George Washington Custis, Major General
Lee, Robert Edward, General
Lee, William Henry Fitzhugh, Major General
Longstreet, James, Lieutenant General
Loring, William Wing, Major General
Lovell, Mansfield, Major General
Magruder, John Bankhead, Major General
Mahone, William, Major General
Marie, Camille Armand Jules, Major General
Marmaduke, John Sappington, Major General
Maury, Dabney Herndon, Major General
McLaws, Lafayette, Major General
Pender, William Dorsey, Major General
Pike, Albert, Brigadier General
Polk, Leonidas, Major General
Price, Sterling, Major General
Rodes, Robert Emmett, Major General
Rosser, Thomas Lafayette, Major General
Smith, Edmund Kirby, General
Smith, Martin Luther, Major General
Stevenson, Carter Littlepage, Major General
Stuart, James Ewell Brown 'JEB', General
Taylor, Richard, Lieutenant General
Van Dorn, Earl, Major General
Walthall, Edward Cary, Major General
Wharton, John Austin, Major General
Wheeler, Joseph, Major General
Wilcox, Cadmus Marcellus, Major General
Withers, Jones Mitchell, Major General

Explanation / Answer

//QueueMain.cpp

#include <iostream>

#include <fstream>

#include <cstdlib>

#include <string>

#include <stdexcept>

#include <cassert>

#include "LinkedQueue.h"

using namespace std;

const char INPUT_FILE[] = "officers.txt";

void loadQueue(LinkedQueue<string> &officers);

void countOff (LinkedQueue<string> officers, int hatNumber);

int main (void)

{

ifstream inFile(INPUT_FILE); // declare and open the input file

int count; // number used for counting off

LinkedQueue<string> officers; // queue containing officer names

string officerName; // name of officer in front of queue

string firstName; // name of first officer in original queue

loadQueue(officers);

// Display list of officers in original queue

cout << "Officers in original queue: " << endl;

firstName = officers.peekFront();

cout << firstName << endl;

officers.dequeue();

officers.enqueue(firstName);

officerName = officers.peekFront();

while (firstName != officerName)

{

cout << officerName << endl;

officers.dequeue();

officers.enqueue(officerName);

officerName = officers.peekFront();

}

// Test countOff() method using various numbers drawn from the hat

count = 5;

cout << endl << endl<< "Count is: " << count << endl;

countOff (officers, count);

count = 8;

cout << endl << endl << "Count is: " << count << endl;

countOff (officers, count);

return EXIT_SUCCESS;

}

void loadQueue(LinkedQueue<string> &officers)

{

ifstream inFile(INPUT_FILE); // declare and open the input file

string officerName; // name of officer input from file

if (!inFile)

cout << "Error opening file for input: " << INPUT_FILE << endl;

else

{

getline (inFile, officerName);

while (!inFile.eof())

{

officers.enqueue(officerName);

getline (inFile, officerName);

}

inFile.close();

}

}

void countOff (LinkedQueue<string> officers, int count)

{

int theCount = 1;

string officerName;

cout << "Officers leaving the queue are: " << endl;

while(!officers.isEmpty()){

officerName = officers.peekFront();

officers.dequeue();

if(theCount % count == 0){

if(!officers.isEmpty()){

cout << officerName << endl;

theCount = 0;

}

}

else {

officers.enqueue(officerName);

}

theCount++;

}

cout<<"The Officer going for help is: "<<officerName<<endl;

  

}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.