使用Queue解决Parcels算法问题。
Problem Description
Delivery company will collect parcel from n locations and rearrange them in the delivery center before delivery. Assume each location will only have 1 parcel to deliver and the destination is labeled as 1 to n. The collector van collects the parcel in unsorted destination sequence. For example, the destination sequence collected may be as follows:
[ 5 8 1 7 4 2 9 6 3 ] 9 parcels were collected in this example
destination no. - '3' is the first parcel collected and with destination '3'
To facilitate efficient delivery of the parcels, parcels will be rearranged in the delivery center so that they are in the order 1 to n. When the parcels are in this order, the delivery van can visit the destination according to the pre-set sequence n to 1. The delivery sequence for the above example will be as follows:
[9 8 7 6 5 4 3 2 1 ]
delivery sequence - for destination '1' will be delivered FIRST
Rearrangement of the parcels in the delivery center will be made via some Holding Buffer Tracks (HBT). The number of HBT varies from 1 to n depending of their availability in the delivery center. Figure 1 below shows the parcels collection sequence (unsorted) with 3 HBTs (H1, H2 and H3).
The n parcels are to end up in the delivery sequence (sorted) in the order 1 through n. According to the above example, figure 2 shows the 9 parcels in the desired sequence.
Solution Strategy: Using Queues
To rearrange the parcels, destinations of the parcels on the input buffer are examined. If the parcel being examined is the next one in the output arrangement, we move it directly to the output buffer. If not, we move it to a HBT and leave it there until it is time to place it in the output buffer. The HBTs operate in a First-In-First-Out (FIFO) manner - regarded as Queues. Parcels enter these HBTs from the top and leave from the bottom. When rearranging parcels, only the following moves are permitted:
- A parcel may be moved from the front of the input buffer to the REAR of one of the HBTs or the output buffer.
- A parcel may be moved from the FRONT of a HBT to the output buffer.
Consider the input arrangement of Figure 1:
- Parcel 3 is the front of the input buffer and cannot be output yet, as it is to be preceded by parcels 1 and 2. So parcel 3 is detached and moved to the H1.
- The next parcel, parcel 6, is also to be moved to a HBT. It can be moved to H2 or H3, but it is more appropriate to push it H1 because parcel 6 is higher than parcel 3 and it gives a better chance for the next parcel from the input buffer to enter H2 or H3.
- The next parcel, parcel 9, is also put into H1.
- Parcel 2 can be moved to H2, because the number of parcel 2 is smaller than that of parcel 9, so parcel 2 cannot put into H1.
- Based on the previously mentioned rules and logic, the first 6 parcels will be moved to the 3 HBTs accordingly as shown in Figure 3.
- The next parcel, parcel 1 (i.e. the 7th parcel in the input buffer), can be moved to the output buffer directly.
- Then, it is now the time to move parcel 2 from H2 to the output buffer. It is followed by moving parcel 3 from H1 to output buffer and parcel 4 from H2 to output buffer. No other parcel can be moved to the output buffer at this time.
- The next step is to move parcel 8 from input buffer to H2. Then parcel 5 is moved from the input buffer to the output buffer directly. Following this move, parcels 6, 7, 8 and 9 can be moved from the corresponding HBTs to the output buffer accordingly and the rearrangement is completed.
The followings are the steps to be followed for the above rearrangement:-
Move parcel 3 from input buffer to holding buffer track H1
Move parcel 6 from input buffer to holding buffer track H1
Move parcel 9 from input buffer to holding buffer track H1
Move parcel 2 from input buffer to holding buffer track H2
Move parcel 4 from input buffer to holding buffer track H2
Move parcel 7 from input buffer to holding buffer track H2
Move parcel 1 from input buffer to output buffer directly
Move parcel 2 from holding buffer track H2 to output buffer
Move parcel 3 from holding buffer track H1 to output buffer
Move parcel 4 from holding buffer track H2 to output buffer
Move parcel 8 from input buffer to holding buffer track H2
Move parcel 5 from input buffer to output buffer directly
Move parcel 6 from holding buffer track H1 to output buffer
Move parcel 7 from holding buffer track H2 to output buffer
Move parcel 8 from holding buffer track H2 to output buffer
Move parcel 9 from holding buffer track H1 to output buffer
You are asked to develop a java application ParcelQueues.java which reads parcel destination numbers can vary from 1 to 100 and they are input one by one using Scanner class until the number input is less and equals than 0. The application then shows the given data in the file and the steps of rearrangement using the standard output (System.out). In order to make the case simple, set the number of holding buffer track to 3.
The input part of the program should be executed as below.
The following is the expected output screen of the program with the above sample data file.
In case if it is not possible to rearrange the parcels successfully because there are not enough HBTs for the given sequence of parcels in the input buffer, an appropriate message should be shown. The following output screen is expected for the unsuccessful scenario:
Instructions to Students
- Assumption of the application:
- a. The number of holding buffer track is set to 3.
- b. The parcel number is input one by one until 0 or -ve value is entered.
- c. The parcel number MUST be from 1 to n without missing number and no checking is required.
- d. All parcel numbers are positive number and no duplication. Some examples are listed below:
- i. [2 4 3 1 5] valid
- ii. [6 A 3 1 2 4 5 ] should cause InputMismatchException
- This assignment is an individual assignment and each student has to submit his/her own work. Plagiarism is a serious offence and any assignments that involve any plagiarism will be given ZERO marks. The award of Zero marks will apply to all parties, regardless of whether or not a student is the original author or the plagiarist. Further disciplinary action will follow.
- You must use J2SDK 1.6.0 or above to develop the programs.
- You are NOT ALLOWED to use data structure classes provided by Java API. You must use the LinkedList, Stack (and/or other data structures developed in the labs) but you may add new methods to the classes if necessary.
- Your programs must follow the coding standard stated in Java coding standard published by Sun Microsystems (http://www.oracle.com/technetwork/java/codeconvtoc-136057.html). be deducted if the coding standard is not followed.
- All work is to be submitted to Moodle on/before 10th April 2020 11:55pm. Late submission without valid reasons will be given ZERO mark.
- You are required to hand in
- (a) All classes (programs) written by you for this assignment.
- (b) The evidence of testing - You should submit at least 4 dump screens to show the run results with your own input files (that means you should design your own test cases).
- The weighting of this assignment is 40% of End-Of-Module Assessment (EA).