Quiz 4

Problem Statement:

It was another fine morning at Kinokuniya (the bookstore where Raphael works part-time). Raphael's employer was very happy with the program that he submitted thanks to your help and promised him a bonus if he also is able to manage the long queues to the register. The employer wants to be able to:

1. Add new people to the back of the queue,
2. Print the name of the person in the front, and remove him/her from the front of the queue,
3. Search for a specific person in the queue,
4. Print the entire queue.

Being the diligent worker he is, Raphael has already started writing code for this. He has started implementing a linked list in C++, and has written functions for 1 and 4. Help him finish the implementation by writing functions for 2 and 3. His code is available here. Refer to the comments in the .cpp file for his outline on how he thinks you should implement functions 2 and 3.

Solution

This quiz asks you to basically implement linked lists using C-type code. I used it as a first-time introduction to linked lists.

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

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

/*-----
 * Function to take a name and add a new node to the list given by node_t* head. 
 * It returns back the updated list.
 * -----
 */
node_t* add_to_end(string name_to_add, node_t* head)
{
	node_t* newNode = new node_t;
	newNode->name = name_to_add;
	newNode->next = NULL;
	if(head == NULL) // If the list is empty
	{
		head = newNode;
	}
	else // If the list is already populated, traverse to the end of the list and add newNode there.
	{
		node_t* p = head;
		while(p->next!=NULL)
		{
			p = p->next;
		}
		p->next = newNode;
	}
	return head;
}

/*-----
 * Function to print the name of the person at front, and remove him/her from the list. 
 * This function should not do anything if the list is empty.
 * It should update head, and return back head.
 * -----
 */
node_t* remove_from_front(node_t* head)
{
	if(head == NULL)
	{
		cout << "List is empty!" << endl;
		return NULL;
	}
	else
	{
		cout << "Person at front: " << head->name << endl;
		node_t* p = head;	// Keep a copy of head before deleting it!
		head = head->next;	// Change head node
		delete p;
	}
	return head;
}
	

/*-----
 *  Function to search for a specific person in the list node_t* head.
 *  If said person is found, function should return the position of this person from the front.
 *  If said person is not found, function should return -1.
 *  -----
 */
int search_for_person(string searchName, node_t* head)
{
	node_t* p = head;
	int position = 1;
	while(p!=NULL)
	{
		if(p->name == searchName)
		{
			cout << "Person " << searchName << " found at position " << position << " in the queue!\n";
			return 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;	
}

// Function to print the entire contents of the queue
void print_queue(node_t* head)
{
	if(head == NULL)
	{
		cout << "List is empty!" << endl;
		return;
	}
	cout << "The current list is:\n";
	node_t* p = head;
	do
	{
		cout << p->name << endl;
		p = p->next;
	}while(p!=NULL);
}

int main()
{
	node_t* head = NULL;
	head = add_to_end("TestPerson1",head);
	head = add_to_end("TestPerson2",head);
	print_queue(head);

	cout << "Searching for TestPerson2:" << search_for_person("TestPerson2", head)<<endl;
	
	print_queue(head);
	cout << "Removing one person from the front!\n"; 
	head = remove_from_front(head);
	print_queue(head);
	
	return 0;
}