CS1101C Practical Exam

Session 5 (1100 - 1245 hours)

Queueing

The deadline for this lab is Wednesday 16 November 2005, 12:45 hours. Strictly no submissions will be accepted after the deadline.

Background

We make an unreasonable assumption: suppose that students, staff, and visitors to NUS are always gracious and considerate and never cut queue or jump queue. Here is an example of a queue for the famous western food stall at Business canteen. We have simplified the scenario to make things easier for you.

Example

Suppose the next student has arrival time of 10 (he arrives at time 10), and the serving time is 4. Again, there is no one in the queue because the previous student has just left. So the total time taken is 0 + 4 = 4.

More Complicated Example

20 5
20 6
23 4

This shows that the first student arrives at time 20 with a serving time of 5, the second student arrives also at time 20 (just behind the first student) with a serving time of 6, and another student arrives at time 23 with a serving time of 4. You may assume that students who arrive at the same time always get served in the same order that appears in the text file. No queue jumping, remember!

The first student will have queueing time of 0, serving time of 5, total time is 0 + 5 = 5.

The second student will need to queue behind the first student. He will be served only at time 25. So, his queueing time is 5, serving time is 6, total time is 5 + 6 = 11.

The third student arrives at time 23 and will need to queue behind both students. He will be served only at time 31. So, his queueing time is 8, serving time is 4, total time is 8 + 4 = 12.

Your Task

7 3
10 4
13 -1
14 -1
20 5
20 6
23 -1
23 4
23 -1
31 -1

Each line in the text file either records the arrival of a student or says that we want the queue status to be displayed. If both integers are positive, the first integer is the arrival time and the second integer is the serving time. If the second integer is negative, it means that a "display queue status" command has been encountered, and the first integer is the time at which we wish to display the queue status. The queue status should be displayed on the screen immediately.

Your program must read this data, and print out statistics whenever:

1. A student arrives in the queue.
2. A student leaves the queue (the store Uncle / Auntie has finished serving the student). A departure event is always shown before other events or commands that occur at the same time.
3. The "display queue status" command is read from the text file. The students in the queue are numbered with positions 1, 2, 3, etc. where position #1 is the front of the queue.

1. All time values in the text file are integers between 1 to 1000 inclusive.
2. No error checking is required.
3. The first integer for each line in the text file is strictly non-decreasing.
4. There are never more than 20 students in the queue at any instant.
5. There are an unknown number of lines in the text file (i.e. the stall can serve any number of students, possibly more than 20).

Sample Run

--- Student Arrived at Time 7 ---
Student arrival time: 7, serving time: 7, departure time: 10,
   queueing time: 0, serving time: 3, total time taken: 3

--- Student Departed at Time 10 ---
Student arrival time: 7, serving time: 7, departure time: 10,
   queueing time: 0, serving time: 3, total time taken: 3

--- Student Arrived at Time 10 ---
Student arrival time: 10, serving time: 10, departure time: 14,
   queueing time: 0, serving time: 4, total time taken: 4

--- Queue Status at Time 13 ---
Number of students in the queue: 1
Student at position #1 is currently being served.
Student arrival time: 10, serving time: 10, departure time: 14,
   queueing time: 0, serving time: 4, total time taken: 4

--- Student Departed at Time 14 ---
Student arrival time: 10, serving time: 10, departure time: 14,
   queueing time: 0, serving time: 4, total time taken: 4

--- Queue Status at Time 14 ---
Number of students in the queue: 0

--- Student Arrived at Time 20 ---
Student arrival time: 20, serving time: 20, departure time: 25,
   queueing time: 0, serving time: 5, total time taken: 5

--- Student Arrived at Time 20 ---
Student arrival time: 20, serving time: 25, departure time: 31,
   queueing time: 5, serving time: 6, total time taken: 11

--- Queue Status at Time 23 ---
Number of students in the queue: 2
Student at position #1 is currently being served.
Student arrival time: 20, serving time: 20, departure time: 25,
   queueing time: 0, serving time: 5, total time taken: 5
Student at position #2 is queueing patiently.
Student arrival time: 20, serving time: 25, departure time: 31,
   queueing time: 5, serving time: 6, total time taken: 11

--- Student Arrived at Time 23 ---
Student arrival time: 23, serving time: 31, departure time: 35,
   queueing time: 8, serving time: 4, total time taken: 12

--- Queue Status at Time 23 ---
Number of students in the queue: 3
Student at position #1 is currently being served.
Student arrival time: 20, serving time: 20, departure time: 25,
   queueing time: 0, serving time: 5, total time taken: 5
Student at position #2 is queueing patiently.
Student arrival time: 20, serving time: 25, departure time: 31,
   queueing time: 5, serving time: 6, total time taken: 11
Student at position #3 is queueing patiently.
Student arrival time: 23, serving time: 31, departure time: 35,
   queueing time: 8, serving time: 4, total time taken: 12

--- Student Departed at Time 25 ---
Student arrival time: 20, serving time: 20, departure time: 25,
   queueing time: 0, serving time: 5, total time taken: 5

--- Student Departed at Time 31 ---
Student arrival time: 20, serving time: 25, departure time: 31,
   queueing time: 5, serving time: 6, total time taken: 11

--- Queue Status at Time 31 ---
Number of students in the queue: 1
Student at position #1 is currently being served.
Student arrival time: 23, serving time: 31, departure time: 35,
   queueing time: 8, serving time: 4, total time taken: 12

--- Student Departed at Time 35 ---
Student arrival time: 23, serving time: 31, departure time: 35,
   queueing time: 8, serving time: 4, total time taken: 12

You are reminded to follow the sample output exactly; else marks will be deducted.

Remember to submit your program using the submit queue.c command, and check your submission using the check command.

All the best!

UNIX commands

1. “dir”: lists all the files in the directory.
2. “cp a.txt b.txt”: copies a.txt to b.txt.
3. “mv a.txt b.txt”: moves / renames a.txt to b.txt.
4. “cat a.txt”: shows the contents of a.txt.