Queues. Help required in project

[niitian]

hello everyone.
i need a bit of help in this project of mine which is due in 2 weeks.. here's what needs to be done, but i have no idea about the logic:( if somebody can help me with the pseudocode or algorithm, i could write the code maself..

Write a program to simulate the working of a utility store. The utility store has three counters for the gents and one for the ladies. At any given time if all the counters are free, then the customer entering the utility store can go to any of the counters. If ladies counter is empty then the gents can use it and similarly if any of the gents counter is empty then the ladies can also use it provided the queues allocated for their gender is occupied). Lets say, the time required to serve any customer is t minutes. If a customer enters the store at time t1 then he should be out of the store at t+t1 provided that there are no queues in front of the counters. In case there are customers being served at all the counters then queues will be maintained in front of each counter and the new customer will go to the shortest queue. In the case of queues, a customer will be out of the store at “t+t1+the time he spent waiting in the queue”.
Our goal is to calculate the average time spent by each customer in the utility store.

Inputs
User should press m/f at any time for telling the program that a male or a female customer has entered in the store.
Outputs
Program should output following
• On each arrival the status of the queues should be updated and displayed
• Should mention the number of customers serviced and average time spent by the customers in the store

looking ahead to some help..regards
niitian

[Salem]

Perhaps begin with a simple program which reacts to single key presses.
Then write another program to implement the basic queue data type.

Then come back to us.

[n1337]

The key to these and all problems is to not get overwhelmed...break it down into steps, solve first one step, then continually add more functionality....

So first we need to think about how we can keep track of the customers, both male and female, and in what queue they are waiting...We also need to think about how we can keep track of the time they are in the store...

Let's think about the second question first. One (simple) way of doing this is to just use the function GetTickCount(), which I believe is in the <windows.h> header file...(if you have another/better way of doing this, use it). GetTickCount() simply returns the number of milliseconds that have ellapsed since the system (computer) started...

So you create a variable for each customer that stores "time_entered_store" as just returning GetTickCount() at the time they enter...make sense?

Now you need to think about implementing some sort of data structure to encapsulate the time, and the number of customers...I think it would be natural to create a queue data structure for this question (search google)...one for each queue...I would create something like a queue of customers, where each customer structure keeps track of the time they entered and gender, and then the queue itself points to the customers, and keeps track of the number in each queue....

once you have this sort of functionality, adding the extra logic (to determine which queue a customer enters) should not be too difficult...

Anyway, hopefully that helps a bit, gets the ideas flowing...

[niitian]

thankyou..i'm just gonna try it out this weekend, lets see :)

[niitian]

Alright, I tried making up the logic, couldn’t manage how to write the code though. Having trouble in it, but it’s what I thought could work. Hope to get some help in the issues I’m lacking in.

To manage the time, I came across this function clock( ) in the header file time.h. what it does is that takes the time and assigns it to a clock type variable say start. The when I’m done with the operations, I assign clock( ) to another clock type variable say end, and the difference between both the variables would give the time taken.

Now to maintain the queues, I would create a class queue having four objects. Each object serving as a counter. Three objects for male counters and one for female. Now when a key is pressed, a counter would be allotted.

To allot counters, first check whether the respective counter for each gender is free or not. To do this, a function is called which returns a value if the first node of that particular counter’s queue is null. If it is NULL, then the function to create a node is called. If not, then the remaining 3 queues are checked. If none is empty, then the function for createnode is called for the respective gender. In each node creation, a “count” variable which is a private data member of the class, is incremented, this helps to keep track of the number of people in the queue and helps to chose queues comparing their lengths when none of the queues are empty.

When a node is created, the timer starts, the pointer is moved forward till the node becomes the first node in the queue and then the timer is stopped. After time t = say 60secs, which is the time required to process each customer, the node is popped out of the queue. The total time for the customer is calculated and displayed at that very instant, also mentioning the position of the other customers. The total time is calculated by adding t to the difference of the times when the timer started and stopped.

I think that should do, however I have little idea how to code it. Thought I could do the coding part better, but seem to be struggling with it.

I don’t have too much idea of working with linked lists. I know how to create nodes and pop then out, but how to keep track of them.?? The coding thing seems a mess ryt now:( plz help!

[Salem]

When you add a node, I would suggest node.expire = clock() + t; Then for each clock tick, all you need to do is if ( clock() >= node.expire ) then remove that node from the list (it will be at the head, or tail) of the list depending on which order you add them.

Post your 'list' class if you're having problems with that aspect. Apart from that, your analysis looks OK so far.

[niitian]

ermm:$ what is expire? a data member of the structure node?

[Salem]

It's whatever you want to call the member of your struct/class which indicates when someone will leave the queue.

[niitian]

exams cameup n the deadline was delayed.now ive got about 6days to do it. just rote code, but have done it just for two counters yet..just want to make the time logic first, but stuck:( helpp plz...
also i dunno how to keep track of the number of each person.n then print it..count would only tell the number of ppl in queue:(

#include<iostream.h>
#include<time.h>


struct node
	{	
		node *next;
		int time_start,expire;
	};

class queue
{ private:
		node *head;
		node *tail;
		int t1;
		node n;
		
	
	public:
		int count;
		queue();
		void addnode();
		void print();
		void dequeue();
};


queue::queue()
{	head=NULL;
	tail=NULL;
	count=0;
	t1=5;
	
 }

void queue::addnode()
{			int T;
	
			node *loc=new node;
			
			clock_t t=clock();
			n.time_start=(t/CLK_TCK);
			
			loc->next=NULL;
       
			if(head==NULL)
			{head=loc;}
		
			 else
			 {tail->next=loc;
			 tail=loc;}
				
			 n.expire=n.time_start+t1;

				t=clock();
				T=(t/CLK_TCK);

				if (T==n.expire)
				{ dequeue();
				print();}

       count++;

}


void queue::print()
{ cout<<"STATUS OF QUEUES:"<<endl;


}
void queue::dequeue()
{        node *temp;
       temp=head;
       while(temp->next->next!=NULL)
               temp=temp->next;
       delete temp->next;
       count--;
       temp->next=NULL;
       tail=temp;
}

int main()
{	queue q1,q2;
	
	char gender;

	cout<<"ENTER YOUR GENDER: (M/F)"<<endl;
	cin>>gender;

	switch(gender)
	{ case 'M':
	
	{q1.addnode();

	break;}

	case 'F':
		{q2.addnode();
		break;
		}

	}


	return 0;

}

[niitian]

okay here's the code after ive sorted the thing about chosing a queue..

stuck with the time logic:(

#include<iostream.h>
#include<time.h>


struct node
	{	
		node *next;
		int time_start,expire;
	};

class queue
{ private:
		node *head;
		node *tail;
		int t1;
		node n;
		
	
	public:
		int count;
		queue();
		void addnode();
		void print();
		void dequeue();
	friend int choose_counter(queue&,queue&,queue&,queue&);
	friend int choose_counter1(queue&,queue&,queue&);
};


queue::queue()
{	head=NULL;
	tail=NULL;
	count=0;
	t1=5;
	
 }

void queue::addnode()
{			int T;
	
			node *loc=new node;
			
			clock_t t=clock();
			n.time_start=(t/CLK_TCK);
			
			loc->next=NULL;
       
			if(head==NULL)
			{head=loc;}
		
			 else
			 {tail->next=loc;
			 tail=loc;}
				
			 n.expire=n.time_start+t1;

				t=clock();
				T=(t/CLK_TCK);

				if (T==n.expire)
				{ dequeue();
				print();}

       count++;

}


void queue::print()
{ cout<<"STATUS OF QUEUES:"<<endl;


}
void queue::dequeue()
{        node *temp;
       temp=head;
       while(temp->next->next!=NULL)
               temp=temp->next;
       delete temp->next;
       count--;
       temp->next=NULL;
       tail=temp;
}


int main()
{	queue q1,q2,q3,q4;
	
	char gender;

	cout<<"ENTER YOUR GENDER: (M/F)"<<endl;
	cin>>gender;

	switch(gender)
	{ 
	case 'M':
		{int c=choose_counter(q1,q2,q3,q4);
			if(c==0)
			{q1.addnode();}
			else if(c==1)
			{q2.addnode();}
			else if(c==2)
			{q3.addnode();}
			else if(c==3)
			{q4.addnode();}
			else
			{ int d=choose_counter1(q1,q2,q3);
					if (d=1)
					{q1.addnode();}
					else if(d=2)
					{q2.addnode();}
					else
					{q3.addnode();}
			}


	break;}

	case 'F':
		{
			int c=choose_counter(q4,q2,q3,q1);
	if(c==0)
	{q4.addnode();}
	else if(c==1)
	{q2.addnode();}
	else if(c==2)
	{q3.addnode();}
	else if(c==3)
	{q1.addnode();}
	else
	{ q4.addnode();}
		break;
		}

	}


	return 0;

}


int choose_counter(queue& obj1,queue& obj2,queue& obj3,queue& obj4)
{ if(obj1.head==NULL)
return 0;
else if(obj2.head==NULL)
return 1;
else if(obj3.head==NULL)
return 2;
else if(obj4.head==NULL)
return 3;
else
return 5;
}


int choose_counter1(queue& obj1,queue& obj2,queue& obj3)
{if(obj1.count<obj2.count && obj2.count<obj3.count)
return 1;
else if(obj2.count<obj1.count && obj2.count<obj3.count)
return 2;
else
return 3;}

[Salem]

It's about time you read the intro threads and figured out how to use code tags.

[niitian]

oh..i'm sorry..i didnt know that:$ would take care in future

[niitian]

so any sugesstions about the logic please?

[Salem]

Well apart from the formatting being a mess, what else would you like us to suggest?

A couple of things:

1. Your 'counter' functions should not be friends. Instead, provide a member function like isEmpty(), so you can do things like if ( q1.isEmpty() )

2. Using clock() means you're measuring processor time, not time according to the clock on the wall. Because this is only a simulation, you don't need to synchronise with the real world time.
So you could just provide a member function like

queue::tick ( void ) {
  myInternalClock++;
  // anything else time related, like dropping an expired entry off the queue
}

You'd call this method from main(), just like any other member function.
If later, you do need to sync with the real world, then main() can do that and all your queue logic remains unaffected.

3. An array of queues (not q1, q2, q3) may be easier to manage.

[Cybulski]

Just one tip: you don't need clock(). You counting virtual time, so you can represent this as integer. It's easier to add and calculate average queue time that way.

Opps sorry Salem already wrote that.

[niitian]

i cannot use an integer..then i wont be able to automatically queue out a person after a particular time...maybe i shud try out the

time();

function..and yes the teacher also hinted about using the

rand();

to generate random time for each person to be queued out..i dunno how to work that.

[niitian]

#include<iostream>
#include<time>
#include<stdlib>
#include<stdio>

using namespace std;


struct node
	{	
		node *next;
		long time_start,time_total,time_compare;
	};

class queue
{ private:
		node *head;
		node *tail;
		node n;
		long time_global;
		
	
	public:
		int count;
		queue();
		void addnode();
		void print();
		void dequeue();
	friend int choose_counter(queue&,queue&,queue&,queue&);
	friend int choose_counter1(queue&,queue&,queue&);
};


queue::queue()
{	head=NULL;
	tail=NULL;
	count=0;
	time_global=time(NULL);
	
	
	
 }

void queue::addnode()
{			if(head==NULL && tail==NULL)
			{ 
				node *person=new node;
				tail->next=NULL;
				time_compare=time(NULL)+rand()%10;
				count++;
			}

			else
			{
				node *person=new node;
				tail->next=person;	
				tail=tail->next;
				tail->next=NULL:
				count++;
			}

			if (head->time_compare==time_global)
			{dequeue();}
}


void queue::print()
{ cout<<"STATUS OF QUEUES:"<<endl;


}


void queue::dequeue()
{        	node *temp;
         	temp=head;
		head=head->next;
		count--;
		
		if(count==0)
			{head=tail=NULL; }

		else
			{ 
				srand(time(NULL));
				head->time_compare=time(NULL)+rand()%10;
				head->time_total=time_compare-time_start;
			}
			
		
       
}


int main()
{	queue q1,q2,q3,q4;
	
	
	char choice;

	cout<<"PLEASE CHOSE FROM THE FOLLOWING MENU:"<<endl<<endl<<"1. To enter a male 

customer, press 'M'."<<endl<<"2. To enter a female customer, press 'F'."<<endl<<"3. To exit 

press 'X'."<<endl;

	cin>>choice;

	switch(choice)
	{ 
	case 'M':
		{int c=choose_counter(q1,q2,q3,q4);
			if(c==0)
			{q1.addnode();}
			else if(c==1)
			{q2.addnode();}
			else if(c==2)
			{q3.addnode();}
			else if(c==3)
			{q4.addnode();}
			else
			{ int d=choose_counter1(q1,q2,q3);
					if (d=1)
					{q1.addnode();}
					else if(d=2)
					{q2.addnode();}
					else
					{q3.addnode();}
			}


	break;}

	case 'F':
		{
			int c=choose_counter(q4,q2,q3,q1);
	if(c==0)
	{q4.addnode();}
	else if(c==1)
	{q2.addnode();}
	else if(c==2)
	{q3.addnode();}
	else if(c==3)
	{q1.addnode();}
	else
	{ q4.addnode();}
		break;
		}

	case 'X':
		{ exit(0);}

	}


	return 0;

}


int choose_counter(queue& obj1,queue& obj2,queue& obj3,queue& obj4)
{ if(obj1.head==NULL)
return 0;
else if(obj2.head==NULL)
return 1;
else if(obj3.head==NULL)
return 2;
else if(obj4.head==NULL)
return 3;
else
return 5;
}


int choose_counter1(queue& obj1,queue& obj2,queue& obj3)
{if(obj1.count<obj2.count && obj2.count<obj3.count)
return 1;
else if(obj2.count<obj1.count && obj2.count<obj3.count)
return 2;
else
return 3;}

what i want to do is take the current time using time() as the person enters. and if that person is first in the queue, i-e head==NULL, a standard set time should be added to that person's time and when it becomes equal to global time, the person dequeues. for any other person entering, i randomly generate time and then dequeue that person after comparing..i tried to put in the random function but i doubt the correctness..secondly i cnt code up this logic..stuck at it:(

another problem is that when the control is gone to the create node function, how do another person enter at that time? should i use the

while(!kbhit())

statement? when a key is pressed, the control will go bak to main..i dunno how to implement that in my class:( please help..im running almost outa tym

[Niiitian]

i Suggest that u visit one of my collegue,he can definetly help u is this regard ,infact he s PHD,,,Dr hammad,,,his office is in the faculty office..
best of luck

[niitian]

its the project he has given..he wont correct my code ofcoarse..and u r? please sumbody see this code n help me out

[Nick Evan]

Here's your own code properly indented :

//indented code


#include<iostream>
#include<time>
#include<stdlib>
#include<stdio>

using namespace std;

struct node
{	
    node *next;
    long time_start,time_total,time_compare;
};

class queue
{ 
private:
    node *head;
    node *tail;
    node n;
    long time_global;


public:
    int count;
    queue();
    void addnode();
    void print();
    void dequeue();
    friend int choose_counter(queue&,queue&,queue&,queue&);
    friend int choose_counter1(queue&,queue&,queue&);
};


queue::queue()
{	
    head=NULL;
    tail=NULL;
    count=0;
    time_global=time(NULL);
}

void queue::addnode()
{			
    if(head==NULL && tail==NULL)
    { 
        node *person=new node;
        tail->next=NULL;
        time_compare=time(NULL)+rand()%10;
        count++;
    }
    else
    {
        node *person=new node;
        tail->next=person;	
        tail=tail->next;
        tail->next=NULL:
        count++;
    }

    if (head->time_compare==time_global)
        dequeue();
}

void queue::print()
{ 
    cout<<"STATUS OF QUEUES:"<<endl;
}


void queue::dequeue()
{        	
    node *temp;
    temp=head;
    head=head->next;
    count--;

    if(count==0)
        head=tail=NULL; 


    else
    { 
        srand(time(NULL));
        head->time_compare=time(NULL)+rand()%10;
        head->time_total=time_compare-time_start;
    }


}

int main()
{	
    queue q1,q2,q3,q4;
    char choice;
    cout<<"PLEASE CHOSE FROM THE FOLLOWING MENU:"<<endl
        <<endl<<"1. To enter a male    customer, press 'M'."
        <<endl<<"2. To enter a female customer, press 'F'."
        <<endl<<"3. To exit     press 'X'."<<endl;

    cin>>choice;

    switch(choice)
    { 
    case 'M':
        {
            int c=choose_counter(q1,q2,q3,q4);
            if(c==0)
                q1.addnode();
            else if(c==1)
                q2.addnode();
            else if(c==2)
                q3.addnode();
            else if(c==3)
                q4.addnode();
            else
                int d=choose_counter1(q1,q2,q3);
            if (d=1)
                q1.addnode();
            else if(d=2)
                q2.addnode();
            else
                q3.addnode();
        }
        break;
    }

case 'F':
    {
        int c=choose_counter(q4,q2,q3,q1);
        if(c==0)
            q4.addnode();
        else if(c==1)
            q2.addnode();
        else if(c==2)
            q3.addnode();
        else if(c==3)
            q1.addnode();
        else
            q4.addnode();
        break;
    }

case 'X':
    { 
        exit(0);
    }

}


return 0;

}


int choose_counter(queue& obj1,queue& obj2,queue& obj3,queue& obj4)
{ 
    if(obj1.head==NULL)
        return 0;
    else if(obj2.head==NULL)
        return 1;
    else if(obj3.head==NULL)
        return 2;
    else if(obj4.head==NULL)
        return 3;
    else
        return 5;
}

int choose_counter1(queue& obj1,queue& obj2,queue& obj3)
{
    if(obj1.count<obj2.count && obj2.count<obj3.count)
        return 1;
    else if(obj2.count<obj1.count && obj2.count<obj3.count)
        return 2;
    else
        return 3;
}

There are quite a lot of things wrong with this code:

It's starts with your include files:

#include<iostream>
#include<time>
#include<stdlib>
#include<stdio>

Change it to:

#include<iostream>
#include<ctime>
#include<stdlib.h>
#include<stdio.h>

line 125-129, you have an extra bracket

else
                q3.addnode();
        } <--- delete this one
        break;
    }

line 121-123

if (d=1)
                q1.addnode();
            else if(d=2)

I guess you meant == instead of =? Remember: = != ==.
And where did the 'd' come from? It's never delcared?

Line 52: time_compare=time(NULL)+rand()%10; time_compare is never declared

line 60: tail->next=NULL: <-- change this : to a ; line 86-90:

{ 
        srand(time(NULL));
        head->time_compare=time(NULL)+rand()%10;
        head->time_total=time_compare-time_start;
    }

time_compare and time_start are never declared

etc. You should first get this to compile. Look careful at the compiler-errors and warning you get and try to fix it one problem at a time.

Good luck!