• Post Reply Bookmark Topic Watch Topic
  • New Topic

FIFO Queue: Waiting Line Simulation  RSS feed

 
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am having trouble deciding on how to setup a program that simulates the progression of a line over time. The program requirements are as follows:

The scenario involves a bank and 5 tellers. There is one line of customers that starts off with an initial length of 20. Every minute, 10 more customers are added to the line. As this is meant to be a FIFO queue the first 11 customers in the line will be distrusted among the 5 bank tellers as follows: Teller #1 will process 1 customer per minute, Teller #2 and #3 can each process 2 customers per minute, and Teller #4 and #5 can each process 3 customers per minute. Therefore, the first 11 customers in line will be processed within the first minute of the programs execution.

Unfortunately, I am not sure how to attack this thing. I am thinking that I need to setup a queue for the initial 20 customers and an array for the 10 customers that will be joining the line every minute. However, I am not sure how I can set this up to work automatically.

I feel hopelessly lost on this one. I'm going to try toy around with some things, but if anyone could provide some insight on where to begin solving this problem, I would greatly appreciate it.
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
is this supposed to run realtime? Do you need to add 10 customers at the top of every minute, add one customer every 6 seconds, or every second, have a 1 out of 6 chance of a new customer showing up?

My point is...before you start worrying about how you are going to do stuff in java (a queue for 20, an array for 10)...be sure you've thought through all the angles of what your program is supposed to do.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fred,

Thanks for the quick reply. I forgot to mention that the program is supposed to run for 10 minutes. Each minute all 10 customers are pushed on at once. So by the end of the first minute, 10 new customers should be in line straight away. Even knowing all that, I am still pulling my hair out trying to get started.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
start by thinking.

does it RUN for 10 minutes, or are you SIMULATING a run of 10 minutes? If you are simulating, you could loop from 0 to 600, and decide what to do each second: every multiple of 60, add 10 people to the line. Every 30 seconds, teller one pops off a customer, etc.

In fact, even if you don't want to finish with it this way, I'd consider starting this way. Once you have it working, you could consider writing something that fires off once a second.

Can you use the queues java provides, or are you trying to 'roll your own', as it were?

etc...
 
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:If you are simulating, you could loop from 0 to 600, and decide what to do each second

Or loop 10 times with each iteration representing a minute
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you supposed to have a actual queue data structure here? I ask because I can think of a way to program this without using an actual queue, just something that represents a queue. What do you have to do at the end of a simulation, say how many people have been served and how many are still in the queue?
 
Bartender
Posts: 1840
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
fred rosenberger wrote:If you are simulating, you could loop from 0 to 600, and decide what to do each second

Or loop 10 times with each iteration representing a minute


Think about that one though. Is a minute enough granularity to determine which person goes to which teller?
At time 0, all tellers would get a customer from the front of the queue
At time 20, Tellers 4 and 5 get a customer from the front of the queue
At time 30 Tellers 2 and 3 get a customer ...
At time 40 Tellers 4 and 5 ...
At time 60, 10 new customers are added to back of the queue, and all tellers get a new customer.
rinse and repeat.

I would actually start with creating a Teller object with a property indicating either how long it takes to serve a customer, or how many per minute they can handle. (I like the time to serve option as it provides a bit more flexibility in some respects, but it doesn't exactly match your spec)
You could then represent this scenario as an array of Tellers, and a Queue of customers.




 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stefan Evans wrote:
Think about that one though. Is a minute enough granularity to determine which person goes to which teller?

I think you guys might be complicating things too much. Does it matter which teller a person goes to? I'm pretty sure I've seen this problem before and all you really want to see is how fast the queue grows and shrinks -- which teller gets which person is irrelevant. But let's let the OP tell us what the goal is rather than speculate.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oh my goodness! Thanks guys for all the responses! I'm so glad I've found such an active JAVA community!

Junilu Lacar wrote:Are you supposed to have a actual queue data structure here?


Yes, the customers have to go into a queue and be labeled customer1, customer2, etc.

fred rosenberger wrote:does it RUN for 10 minutes, or are you SIMULATING a run of 10 minutes?

The program is only simulating the passage of 10 minutes.

Stefan Evans wrote:I would actually start with creating a Teller object with a property indicating either how long it takes to serve a customer, or how many per minute they can handle. (I like the time to serve option as it provides a bit more flexibility in some respects, but it doesn't exactly match your spec)
You could then represent this scenario as an array of Tellers, and a Queue of customers.


Thank you, Stefan. That is a great idea. However, I don't know if I need to actually show which customer is going to which teller. I'm pretty sure the Prof. just wants to see the first 11 customers removed from the line every one minute and another 10 customers added to the line every minute. Of course, I could be wrong. I will have him specify exactly before I make more assumptions.

Right now I am just trying to piece this thing together using some things I've learned about queues, arrays, and linkedlists on the internet. My textbook and course material isn't very helpful so I'm basically feeling around in the dark and hoping to get it right. I will post some of what I have so far tomorrow. I know it isn't going to be perfect, but it will be a start.

Again, thank you so much for taking your time to give suggestions, pointers, and guidance. It is such a blessing!


Junilu Lacar wrote:
I think you guys might be complicating things too much. Does it matter which teller a person goes to? I'm pretty sure I've seen this problem before and all you really want to see is how fast the queue grows and shrinks -- which teller gets which person is irrelevant. But let's let the OP tell us what the goal is rather than speculate.


Yes, the only thing I need this program to do is pop the first 11 customers off every minute, then display the contents of the queue.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Stein wrote:I don't know if I need to actually show which customer is going to which teller. I'm pretty sure the Prof. just wants to see the first 11 customers removed from the line every one minute and another 10 customers added to the line every minute. Of course, I could be wrong. I will have him specify exactly before I make more assumptions.

If that's the case, I would not even bother with a Teller object. Seems like this exercise is all about a Queue and a 10-iteration loop. Inside the loop, you'd just have to call the queue operations that would simulate the next person at the front of the queue going to the next available teller. One approach I suggest is to describe the scenario in plain English then start translating it into code:

If you've learned about methods already, lines 1, 4, 5, and 7 would end up being method calls and each method does its own little job. If you haven't learned about methods yet, then you simply translate each of those into proper code. I assume you have learned how to use a loop to perform repetitive tasks. That is, adding 20 people to a queue can be reduced to the task of adding one person to the queue repeated 20 times. Same idea for showing who all is still in the queue and all the other things you have to do for this exercise.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:If that's the case, I would not even bother with a Teller object...

Not sure I agree with you there. The problem description clearly states a "bank", 5 "tellers", and a "line" (presumably the queue) of "customers", so I'd expect to see, at the very least, those classes declared. If you start trying to extrapolate what you think the intent of the exercise is, you could tie yourself in lots of knots.

@Mike: This is a slightly "philosophical" point, but I would say this: Beginners tend not to create enough classes, so don't be afraid of creating a new one if you think you need it. Testing (and practise) will soon tell you when you've created too many; but it isn't usually the case when you're starting out.

HIH

Winston
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OP wrote:the only thing I need this program to do is pop the first 11 customers off every minute, then display the contents of the queue

Taking this at face value, what role would the Teller and Bank object(s) have? I suppose you could have a Teller take a Queue reference and call the pop or remove method on it but what's the point? I can't think of anything useful that a Bank object would do to achieve the stated goal. One pitfall of object oriented programming is trying to model too much of the real world in your program; OOP is really about assigning responsibilities to appropriate abstractions, not about modeling the real world.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:Taking this at face value, what role would the Teller and Bank object(s) have? I suppose you could have a Teller take a Queue reference and call the pop or remove method on it but what's the point? I can't think of anything useful that a Bank object would do to achieve the stated goal. One pitfall of object oriented programming is trying to model too much of the real world in your program; OOP is really about assigning responsibilities to appropriate abstractions, not about modeling the real world.

Again, I can't agree. The Bank is a container for the Tellers and the Customer queue (or Line), and may also contain the "mill" that drives the simulation. If you have a Teller object, you could also assign it (or him/her) a "processing time" at construction to fit in with the problem description.

About the only thing I see that doesn't really have much to do is a Customer, because it's the "thing being processed"; but you could certainly give each one a name (or a number) so you can see what's going on. Same with your Tellers. And do you really care whether your "line" is a Queue<Object> or a Queue<Customer>?

I would also say that you're absolutely right: the Teller should be the driving force to the simulation, since they are the "active" participant. If you drive the process from the queue, you're likely to have a lot of "busy waiting", but if each Teller simply "calls" the next Customer when they're ready (which is basically what happens in real life), the code is likely to be much simpler. Indeed, if you made each Teller a Thread, you'd probably be pretty darn close to what actually happens in a bank.

But @Mike: I wouldn't worry too much about that just yet. You can easily write a basic mill that simply cycles through your Tellers once a "second" (or once every 10 seconds) for 10 minutes, and adds customers to the Line as appropriate.

The only thing I'd say that needs clarification is whether "adding 10 customers to the line every minute" means adding 1 every 6 seconds, or adding 10 at the end of each minute. If the first, then your mill would probably need to cycle every 2 seconds rather than every 10.

My 2¢.

Winston
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
We could go back and forth on this but I think I'll hold off until the OP has resolved his questions and shown what he's done to make the grade. Then I can post how I would solve it and put it up for discussion.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:We could go back and forth on this but I think I'll hold off until the OP has resolved his questions and shown what he's done to make the grade.

Agreed.

And @Mike: there's no "right" or "wrong" about this; Junilu and I just disagree (or seem to) about the approach. And that's what makes programming fun.

Winston
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
All, I can't begin to express my gratitude for all of your contributions to this post. Just in case I get accused of academic dishonesty or some other bogus charge, I will be posting my code on Monday as the project is due on Sunday. What I have so far works, but it needs A LOT of improvement. I can't wait to see your feedback and suggestions after I post the code! Have a great weekend guys and thanks again.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Stein wrote:All, I can't begin to express my gratitude for all of your contributions to this post.

You're most welcome. And don't worry about our disagreement - it's what we "oldies" live for - and the fact is that for any even moderately complex problem, there is almost never only one solution.

I will be posting my code on Monday as the project is due on Sunday. What I have so far works, but it needs A LOT of improvement. I can't wait to see your feedback and suggestions after I post the code!

That'll be great. Unfortunately, I'm moving back to the UK on Monday after 11 years in Belgium, and I won't have an Internet connection until the 11th of Feb; but I'll be sure to look back once I'm "live" again.

Winston
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, the code that follows is what I ended up going with. It mostly did what it was supposed to do, but I ran into some issues trying to get some more functionality out of it. For example, I wanted to specifically show which customers where served by a particular Telller. That is, Teller One served customer 1, Teller 2 served customers 2 and 3, and so on.
Also, I was unable to work out how to continue the naming convention when the 10 new customers were added each minute. I wanted the names (Customer 1, Customer 2, Customer 3, etc.) to pick up where the startOfLine method left off so that every time the 10 new customers were added, via the addMoreCustomers method, they would continue the numbering system. Overall, I think I did rather poorly on this assignment. I obviously have quite a bit to learn.

I really look forward to reading any feedback you guys can provide. I'm sure there is a much cleaner and more efficient way to make this program work.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's not as bad as you might think. I've seen worse from people who are paid to write programs.

Good things I see: you're paying attention to how you're naming things and making attempts to use good names and you're using methods to break your program into small tasks.

Based on this new information about what you want the program to do, I would agree with the idea to have a Teller class.

I would lay out a plan like this:

I'd probably waffle between the names BankLine and BankLineSimulator. Seems like I could be convinced to stay with BankLine though. I definitely see the methods tellerOne, tellerOneAndThree, and tellerFourAndFive as "code smells" because they are too specific to a particular scenario. What happens when you want to simulate for tellers with different rates than what you've been initially given? Writing more methods for these tellers is not the ideal way to extend the simulation. A better way would be to create new Teller objects that know what their rates of service are.

As for your loop starting at line 116, I don't see a need to go with 599 as the upper bound and 60 as the increment. Seems like it's pointless since you're not doing anything in the loop that uses the index anyway. I think you're on the right track with the method calls inside the loop though.

I'll post the code I envisioned before you said anything about additional requirements.
 
Stefan Evans
Bartender
Posts: 1840
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The other thing I would look at is allowing 'tweaks' to your solution.

Part of a good design is working out what are the parameters that are likely to change, and make them easily configurable.
Being able to design your app so you can easily change things like
- number of tellers
- how fast the tellers work
- how many customers per minute come in.

For instance your "addMoreCustomers" method always adds 10 customers no matter what.
It would be more flexible if you could write addMoreCustomers(10) - because then you can easily change it to addMoreCustomers(5), or addMoreCustomers(13) - you just change the call to it, and not the method.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's an approach that basically starts with the code you'd like to write, then write the code behind it that enables you to do so. For example, it would be neat if I could write code like this for the simulation that you originally wanted:

Then I could write something similar for other scenarios. That is, I'd still have a "builder" that I can use to define the scenario, then let it initialize a simulation object for me that I can then run but I'd call withTeller() and other methods a different number of times and with different parameters to create a different scenario. This way, the main simulation logic can stay the same and only the configuration of each scenario will differ.

But this is still waaay down the road from where I had actually thought of starting. Just want to plant that seed of thought first so you know where I'd eventually head towards. The above code is an example of the Builder pattern, BTW, but don't worry about it for now.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Using the same "write the code that you want" approach and going back to my original suggestion:

I would translate this to a series of method calls:

From there, I would drill down to each of these methods and implement what they would do. But before that, I could just stub everything out:

When I run this code, it will give me an idea of how everything would flow and I can see if I'm on the right track. Notice that I shuffled around some of the code that I had before. I'll do that a lot as I develop and refine the code.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike, consider the two lines of code:

If we were to take the best from these two versions, I would say that the best way to do it would be something like this:

I like this merged version better because it's more conversational when you read it back and the name fits the intent/purpose of the method quite well, IMO. The name initializeWith seems a little bit too clinical by comparison and the name startOfLine doesn't grammatically align with the intent quite as well. By passing a parameter to the method instead of defining the starting value in the method itself, you make the method code more generic and the simulation class more configurable. Also, the name simulation is more descriptive and reveals intent better than the name b. I alluded to this earlier but choosing good names for classes, methods, and variables is an important aspect of writing good programs. Good names make the code easier to follow, understand, maintain, and debug. Poorly chosen names can mislead and confuse the reader of the code, including the person who wrote it.

Also, to an earlier point I made, object-oriented programming is largely about assigning responsibilities properly and keeping dependencies loose. In the more configurable version, we took the responsibility of determining the starting number of customers in the queue away from the method and gave it to the client of the simulation class, whoever that may be. In this case, that responsibility is now given to the main method. In other cases, we might decide to externalize that responsibility further out, say to a Dependency Injection framework like Spring, for example. Anyway, don't worry about that for now, just note that this approach makes the code more flexible.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One more thing to note: at this point, I don't even have any implementation details. I just have a rough framework for the program to organize the responsibilities and flow of execution. This is the "top-down" approach where you start with high-level concepts and work your way down to the "bottom" where you deal with implementation details. By focusing on the high-level ideas first, you keep your options about implementation details open. When you do that, your programs tend to be better organized, easier to understand, and more flexible.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Continuing to implement the stubbed out methods, I would do this next:

And upon seeing that, I would ask, "Well, do we even need initializeWith(n) then?"

To implement the other methods, I need to decide on what data structure to use to represent the queue. Since you decided to use Queue<Object> and LinkedList, I'll try that out as well and see how it goes, except I want to be a little more specific about what's going into the queue.

The differences from what you did:
1. Elements are String instead of Object
2. naming this customers instead of bline so that our intent is clearer.
3. Declared as private instead of public - try to limit scope to the minimum possible and increase only as you find it necessary to do so for new code
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Next, implement addCustomers(int n):

Things to note about the implementation of addCustomer:
1. The loop is fairly straightforward: add a new customer to the queue n times
2. Make a call to a new private method nextCustomerNumber to keep a running count of customers added to the queue so far
3. Store the running count of the customers in a private field, customerCount
4. Each new simulation that is instantiated will have its own count of customers to track.
5. On instantiation of a new simulation, customerCount field is initialized to 0 by default.

In the early part of this thread, I hinted at perhaps not needing a Teller class at all. This would result in a "quick and dirty" implementation of serviceCustomers method. If you decided to go with using a Teller class and maybe making the service rates more configurable, then the implementation would be a little bit more involved.

I'll leave the implementation of serviceCustomers and showQueueCustomers for you to think about and try or discuss, as you prefer.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu and Stefan,

Thanks so much for your insight! Once my schedule permits, I plan to revisit my queue assignment. I will no doubt try to implement all of the outstanding suggestions and tips you guys have provided. Again, thank you very much for your time and for lending me your expertise.

 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!