Quiz 4

Problem Statement:

Raphael was very happy last week until his boss suddenly called him yesterday, asking him to rewrite his code from Quiz 5 using C++ classes. Despite being terribly upset about it, he has finished up writing part of the code HERE. However, same as his predicament from last week, he doesn't understand how to complete the code to include functions for: a) searching for a person and b) deleting the person at the front. Please help him complete his .cpp file ABOVE by defining the two remaining functions.

He keeps the people in his queue inside a structure called node_t, which consists of the data part string name and the pointer part node* next. He is using a class named BookstoreQueue, which consists of three private data members: int size, node_t* head, node_t* tail. He has implemented the functions getSize(), printQueue(), and addToEnd() already. Please help him finish the methods positionOfPerson() and deleteFromFront().

Solution

This quiz asks you to basically implement linked lists using C++-type code.

The only difference from the problem in Quiz 5, is that since we are using classes, all the methods are public functions of the class BookstoreQueue, and therefore you do not need to pass the head as arguments. Also, you do not get a working copy of the list: whatever modifications the functions do to the list are final!

#include <iostream>
#include <string>
using namespace std;

typedef struct node
{
	string name;
	struct node* next;
}node_t;

class BookstoreQueue
{
	// Private data members:
	int size = 0;
	node_t* head = NULL;
	node_t* tail = NULL;
	
	public:
	// Public functions:
	// 1. Function to return the current size of the queue.
	int getSize()
	{
		return size;
	}
	// 2. Function to print the queue starting from the head.
	void printQueue()
	{
		if(size==0)
		{
			cout<<"EMPTY\n";
			return;
		}
		node_t* p = head;
		for(int i=0; i<size-1; i++)
		{
			cout<<"("<<p->name<<")->";
			p = p->next;
		}
		cout<<"("<<p->name<<").\n";
	}
	// 3. Function that takes as input a string searchPerson, searches whether that person is found in the queue, and returns his/her position from the front. The frontmost person is the 1st person, and so on.
	// If searchPerson is not found in the queue, this function should return -1.
	int positionOfPerson(string searchPerson)
	{
		node_t* p = head;
		int position = 1;
		while(p!=NULL)
		{
			if(p->name == searchPerson)
			{
				cout << "Person " << searchPerson << " found at position " << position << " in the queue!\n";
				return position;
			}
			position++;
			p = p->next;
		}
		// If we reach here, that means the while loop has ended without the function terminating. This means searchName was not found in the list.
		return -1;	
	}
	
	// 4. Function that adds a newPerson to the end of the queue.
	void addToEnd(string newPerson)
	{
		// Create a new Node
		node_t* newNode = new node_t;
		newNode->name = newPerson;
		newNode->next = NULL;
		if(size==0)		// If queue is empty:
		{
			head = newNode;
			tail = newNode;
			size = 1;
		}
		else 		// else queue had at least one element:
		{
			tail->next = newNode;
			tail = newNode;
			size++;
		}
	}

	// 5. Function that deletes a person from the front of the queue. It returns the name of the person who was at the front.
	string deleteFromFront()
	{
		if(head == NULL)
		{
			cout << "List is empty!" << endl;
			return "";	// Return the empty string as an exception
		}
		else
		{
			string retVal = head->name; 	//Copy the name of the person before deleting
			node_t* p = head;		// Keep a copy of head before deleting it!
			head = head->next;		// Change head node
			delete p;			// Delete the hanging node pointed to by p
			size--;				// Update size
			return retVal;
		}
	}
	

	//Constructor:
	void BookStoreQueue(int a)
	{
		size = a;
		head = NULL;
		tail = NULL;
	}
};

int main()
{
	BookstoreQueue queue;
	cout<<"Current queue size: "<<queue.getSize()<<". Current queue:\n";
	queue.printQueue();
	queue.addToEnd("Muimi");
	cout<<"Added Muimi to queue.\nCurrent queue size: "<<queue.getSize()<<". Current queue:\n";
	queue.printQueue();
	queue.addToEnd("Kyouka");
	cout<<"Added Kyouka to queue.\nCurrent queue size: "<<queue.getSize()<<". Current queue:\n";
	queue.printQueue();


	/*Tester code for positionOfPerson():*/
	cout<<"Searching for Kyouka.\n";
	cout<<"Found Kyouka in position "<< queue.positionOfPerson("Kyouka");
	cout<<"\nSearching for Christina.\n";
	cout<<"positionOfPerson() returned "<< queue.positionOfPerson("Christina")<<endl;
	

	/* Tester code for deleteFromFront():*/
	string deletedPerson = queue.deleteFromFront();
	cout<<"Deleting the following person from the front: "<<deletedPerson<<"\nCurrent queue: ";
	queue.printQueue();

	return 0;
}