Question

1. Raphael was very happy last week until his boss suddenly called him yesterday, asking him to rewrite his code. Despite being terribly upset about it, he has finished up writing part of the code below. 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().

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

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

class BookstoreQueue
{
        // Private data members:
        int size;
        node_t* head;
        node_t* tail;
        
        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);
        
        // 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();
        

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

int main()
{
        BookstoreQueue queue;
        cout<<"Current queue: ";
        queue.printQueue();
        queue.addToEnd("Muimi");
        cout<<"Added Muimi to queue.\nCurrent queue: ";
        queue.printQueue();
        queue.addToEnd("Kyouka");
        cout<<"Added Kyouka to queue.\nCurrent queue: ";
        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");
        */

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

        return 0;
}

Answer 1

Function for searching the position of the person : -

int positionOfPerson(string searchPerson)
   {
       node_t* temp=head; // Creating a temporary node to which is pointing to head of the queue.
       int pos=1; // Initialising the pos variable to 1 as the person at the head will be positioned as 1
       while(temp) // This loop will continue till the temp becomes NULL.
       {
           if(temp->name == searchPerson) // If the person is found then its position will be returned.
               return pos;
               temp=temp->next; // Otherwise we will move to the next person.
           pos++; // Position will be increased while moving to the next person.
       }
       return -1; // If person not found then -1 is returned.
   }

Function for deleting a person from the front of the queue :-

string deleteFromFront()
   {
       if(size==0)
           return "EMPTY"; // If no one is in the queue then return EMPTY.
       string first = head->name; // Sting variable first is initialised with the name of the person at front.
       node_t* temp = head; // Temporary node pointing to the head of the queue.This will help in deleting the //unused memory.
       head=head->next; // New head will be the next person to the head.
       delete(temp); // Deleting the unused memory.
       size--; // Now the size of the queue is reduced by one.
       return first; // The name of the person deleted from the queue is returned.
   }

Output :-

Function for searching the position of the person : -

int positionOfPerson(string searchPerson)
        {
            node_t* temp=head;              // Creating a temporary node to which is pointing to head of the queue.
            int pos=1;                               // Initialising the pos variable to 1 as the person at the head will be positioned as 1
            while(temp)                            // This loop will continue till the temp becomes NULL.
            {
                if(temp->name == searchPerson)      // If the person is found then its position will be returned.
                return pos;
                temp=temp->next;                              // Otherwise we will move to the next person.
                pos++;                                                // Position will be increased while moving to the next person.
            }
            return -1;                                                // If person not found then -1 is returned.
        }

Function for deleting a person from the front of the queue :-

string deleteFromFront()
        {
            if(size==0)
                return "EMPTY";                     // If no one is in the queue then return EMPTY.
            string first = head->name;          // Sting variable first is initialised with the name of the person at front.
            node_t* temp = head;                // Temporary node pointing to the head of the queue.This will help in deleting the                                                                         //unused memory.
            head=head->next;                     // New head will be the next person to the head.
            delete(temp);                             // Deleting the unused memory.
            size--;                                        // Now the size of the queue is reduced by one.
            return first;                                // The name of the person deleted from the queue is returned.
        }

Output :-

Note:-

The constructor should not have any return type.