Assignment11 -cse 205 | Computer Science homework help
You are required, but not limited, to turn in the following source files:
Assignment11.java (You do not need to modify this file.)
StackRearranger.java — complete this file.
Requirements to get full credits in Documentation
- The assignment number, your name, StudentID, Lecture number, and a description of each class/file need to be included at the top of each file/class (in this assignment, you might have only one file/class, but in future there will be more than one file.)
- A description of each method is also needed.
- Some additional comments inside of methods (especially for a “main” method) to explain code that are hard to follow should be written. You can look at Java programs in the text book to see how comments are added to programs.
New Skills to be Applied
In addition to what has been covered in previous assignments, the use of the following items, discussed in class, will probably be needed:
Stacks
Program Description
Class Diagram:
Assignment #11 will be the construction of a program that rearranges the content of a stack into a sorted order using other stacks.
Your program needs to read in numbers and push them into the stack called initialStack.
A user will specify how many number will be entered, and the numbers will be distinct numbers from 1 to some positive number.
For instance, if a user specifies that 7 numbers will be entered, then the numbers to be inserted into the initial stack will be: 1, 2, 3, 4, 5, 6, 7 (i.e., 1 through 7), but they might not be in any sorted order, for instance, 3, 6, 4, 7, 1, 2, 5.
Then your program should remove each element from the initialStack from its top one by one, and the objective is to insert all numbers into the stack called outputStack in the increasing order.
If the top number of the initial stack is 1, then you can push 1 into the output stack. However, it is some other larger number, then it needs to wait to be pushed into the output stack until all numbers that are smaller than that number are already pushed into the output stack.
Here, we will be using other stacks called holdingStacks. The number of such holding stacks will be specified by a user as well and it will be an array of Stack objects.
If there is a number larger than 1, then you need to push it onto one of the holding stacks, but here is the condition:
-Check each holding stack in its increasing index order, if one is empty or the number to be pushed is smaller than the top element of the holding stack, then you can push the number onto such holding stack. This holding stack is called bestStack for the number.
-If you cannot find such holding stack, then it means that you cannot complete this rearrangement task. It should stop and return false.
Once the number 1 is stored in the output stack, then you need to keep checking if the top number of the initial stack is 2, or the top of any holding stack is 2. If the top number of the initial stack is 2, then you can push it onto the output stack. If the top of any holding stack is 2, then pop it, and push it onto the output stack.
After this, you need to keep looking for the next number 3, and so on until the largest number is pushed onto the output stack.
Here is an example. Suppose that you are given the following sequence of numbers:
7 9 1 2 5 6 8 4 3
with three holding stacks #0, #1, and #2.
The top of the initial stack is 3, if you pushed all numbers from left to right onto the initial stack. Since it is not the smallest, you need to push 3 onto the holding stack, say, #0.
The next number of the initial stack is 4. It cannot be pushed onto the holding stack #0 because it is larger than the top of the holding stack #0, which is 3. So we can push 4 onto another holding stack, say #1.
Similarly, 8 will be pushed onto the holding stack #2.
Now, the next number 6 can be pushed only onto the holding stack #2 because that is the only stack whose top is larger than 6. Remember, the content of each holding stack needs to be increasing order.
After pushing 3, 4, 8, 6, 5, 2 onto holding stacks, the content of holding stacks will be:
Holding Stack 0: [3, 2]
Holding Stack 1: [4]
Holding Stack 2: [8, 6, 5]
The next number from the initial stack is 1, so this is pushed directly onto the output stack.
At this point, the next smallest number 2 is at the top of the holding stack #0. So we pop it and push it onto the output stack. Then we will do the same for the number 3. We continue to pop from the holding stacks as long as the next smallest number is at the top of one of the holding stacks.
After popping 2, 3, 4, 5, and 6, we have:
Holding Stack 0: []
Holding Stack 1: []
Holding Stack 2: [8]
The next smallest number 7 is not in the holding stacks, so we need to re-start popping numbers from the initial stack which still contains: [7, 9].
Instruction:
Assignment11 class
This class displays a menu for the Stack Rearranging. If a user enters “E”, then it asks to enter a size of the initial stack and also a number of holding stacks, then it will display a result for the problem. This class is given by the instructor.
StackRearranger class
The StackRearranger class contains a constructor to set up an initial configuration.
It also contains methods to print out stacks as well as to rearrange stack content.
You need to complete the following methods.
Please see the StackRearranger.java for more details.
There are 6 portions where you need to complete the code.
Please look for the line such as:
/****1. ADD Your Code Here ****/
since that is where you need to add more code.
public boolean rearrange()
You need to write the rearrange method that rearranges the initial stack and also determines if it is feasible. It should return true if a rearrangement is successful, false otherwise.
Please see the StackRearranger.java file for more details.
public void fromHoldingStackToOutputStack()
You need to write the fromHoldingStackToOutputStack method that moves the smallest element among all holding stacks into the output stack.
It also keeps track of the next smallest number and the holding stack that contains in it using the variable smallestNumber and stackWithNextSmallest.
Please see the StackRearranger.java file for more details.
public boolean putInHoldingStack(int number)
You need to write the putInHoldingStack method that tries to push the parameter number into the best stack, i.e., the one with the top element larger than the parameternumber and also with the top element smallest among such holding stacks.
If it cannot find such holding stack, it should return false. It should return true otherwise return true.
Please see the StackRearranger.java file for more details.
Requirements:
You need to implement this method using an object of the Stack class in java.util package.
Input
The following files are the test cases that will be used as input for your program (Right-click and use “Save As”):
Test Case #1
Test Case #2
Test Case #3
Test Case #4
Output
The following files are the expected outputs of the corresponding input files from the previous section (Right-click and use “Save As”):
Test Case #1
Test Case #2
Test Case #3
Test Case #4
OR you can download all files at once:
Error Handling
Your program is expected to be robust enough to pass all test cases. You may use the Scanner class, but are not limited to it, to handle your user input.
