Question

Suppose that a minus sign in the input indicates dequeue the queue and write the return value to standard output, and any other string indicates enqueue the string onto the queue. Further suppose that following input is processed:

it was - the - best - of times - - it was - the - - worst - of times -

a) What is written to standard output?

b) What are the contents (head to tail) left on the queue?

Answer 1

Program implemented in Cpp. Answers to a) and b) are mentioned as per the implementation.

#include <iostream.h>

#include<string>

using namespace std;

#define N 200

int main()
{
   string S;
   count<<"Enter the required String: ";
   cin>>S;

   int len= S.length();
   char Q[len]; //maximum length of the queue is the length of the given string.
   int front=-1, rear=-1;
   for(int i=0; i<len; i++)
   {
       if(S[i]=='-')
       {
           if(front==-1 || rear==-1)
           {
               cout<<"\nUnderflow";
               exit(0);
           }

           Q[front]=0;

           if(front==rear)
           front=rear=-1;
           else
           front= (front+1)%len;
       }
       else
       {
           if((rear+1)%len==front)
           {
               cout<<"\nOverflow";
               exit(1);
           }

           Q[rear]=S[i];

            if(front==rear && rear==-1)
               front=rear=0;

              else
           rear=(rear+1)%len;
       }
   }

   for(int i=front; i<=rear; i=(i+1)%len)
   {
       count<<Q[i];
   }

return 0;
}   

a) Overhere, we consider the spaces in between two words. So the given input is translated as:

it_was_-_the_-_best_-_of_times_-_-_it_was_-_the_-_-_worst_-_of_times_-

, where underscore represents the spaces in the string.

Length of the queue is the max length of the string, which here is 70, front and rear are inititally set to -1 indicating an empty queue. On the insertion of the very first element, front and rear are set to 0.

So, the contents of the queue displayed onto the console as the given code is,

e__best__of_times___it_was__the___worst__of_times_

b) Content of the queue is as follows:

        e__best__of_times___it_was__the___worst__of_times_
   front                                                                              rear

,where Q[front]='e'

Q[rear]='_'