Minimal Submitted Files You are required, but not limited, to turn in the follow
ID: 3688602 • Letter: M
Question
Minimal Submitted Files
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
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.
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 parameter number 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.
Assignment11 class (does not need modified)
StackRearranger(needs to be modified)
Expected Input
Expected Output
Explanation / Answer
package stack.rearranger;
import java.util.Stack;
public class StackRearranger
{
private Stack<Integer> initialStack; //stack contains numbers in an order specified by a user
private Stack<Integer> outputStack; //stack to have numbers in sorted order after running this algorithm
private Stack<Integer>[] holdingStacks; //stacks to hold some numbers that are not in either initial or output stack
private int sizeOfInitialStack; //the initial stack size
private int numberOfHoldingStacks; //number of holding stacks, specified by a user
private int smallestNumber; //current smallest number that can be moved to the output stack
private int stackWithNextSmallest; //the index of holding stack that contains the next smallest number
//Constructor to initialize member variables
public StackRearranger(int sizeOfInitialStack, int numOfHoldingStacks)
{
initialStack = new Stack<Integer>();
outputStack = new Stack<Integer>();
this.sizeOfInitialStack = sizeOfInitialStack;
this.numberOfHoldingStacks = numOfHoldingStacks;
holdingStacks = new Stack[numberOfHoldingStacks];
for (int i=0; i< numberOfHoldingStacks; i++)
{
holdingStacks[i] = new Stack<Integer>();
}
smallestNumber = sizeOfInitialStack+1; //large number
stackWithNextSmallest = -1; //index of holding stack containing the next smallest is unknown
}
//The addNumberToStack adds the parameter number
//to the initial stack
public void addNumberToStack(int number)
{
initialStack.push(number);
}
//The printHoldingStacks prints out the content
//of the holding stacks
public void printHoldingStacks()
{
System.out.println("Holding Stack Contents: ");
for (int i = 0; i < numberOfHoldingStacks; i++)
{
System.out.println("Holding Stack " + i + ": " + holdingStacks[i].toString());
}
System.out.println();
}
//The rearrange method rearranges the numbers in the initial stack
//into a sorted order in the output stack
public boolean rearrange()
{
boolean success = true;
//the next number that should move to output stack is initially 1
int nextNumberToOutputStack = 1;
//Print out the initial stack content
System.out.println("Initial Stack Content: " + initialStack.toString());
while(initialStack.empty() == false)
{
int nextNumber = 0;
//get(pop) the next number to move from the initial stack
//and assign it to "nextNumber"
nextNumber = initialStack.pop();
if (nextNumber == nextNumberToOutputStack)
{
//if it is the next smallest number,
//then push it onto the output stack
outputStack.push(nextNumber);
System.out.println("Move number " + nextNumber
+ " from input stack to output stack");
//nextNumberToOutputStack should be incremented now
//to loop for the next smallest number.
nextNumberToOutputStack++;
//As long as the smallest number among all holding stacks
//is same as the next number to move to output stack,
//process the following:
while (smallestNumber == nextNumberToOutputStack)
{
//look for the next smallest number among holding stacks
//This will compute the smallest number
//and which holding stack it belongs to
fromHoldingStackToOutputStack();
nextNumberToOutputStack++;
}
}
else
{
//put the next number into one of the holding stack
if (putInHoldingStack(nextNumber) == false)
{
success = false;
return success;
}
}
}
System.out.println("Output Stack Content: " + outputStack.toString());
return success;
}
//The fromHoldingStackToOutputStack method 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.
public void fromHoldingStackToOutputStack()
{
if (stackWithNextSmallest >= 0
&& holdingStacks[stackWithNextSmallest].isEmpty() == false)
{
//remove(pop) the smallest number from its stack to move to the output stack
//and move(pop) it to output stack
outputStack.push(holdingStacks[stackWithNextSmallest].pop());
System.out.println("Move number " + smallestNumber + " from holding stack#"
+ stackWithNextSmallest + " to output stack");
printHoldingStacks();
}
//Find the next smallest number and the holding stack that contains it
//by checking the top of all holding stacks
smallestNumber = sizeOfInitialStack + 1;
for (int i = 0; i < numberOfHoldingStacks; i++)
{
if (holdingStacks[i].isEmpty() == false
&& ((Integer) holdingStacks[i].peek()).intValue() < smallestNumber)
{
smallestNumber = ((Integer) holdingStacks[i].peek()).intValue();
stackWithNextSmallest = i;
}
}
//After the above loop, the variable "stackWithNextSmallest" should have an index
//of the holding stack contains the next smallest Number
//AND the variable "smallestNumber" should have the next smallestNumber to move
//to the output stack.
}
//The putInHoldingStack tries to push the parameter number
//into the best stack, i.e., the one with the top element larger
//than the parameter number and also with the top element smallest among
//such holding stacks.
//If it cannot find such holding stack, it returns false.
public boolean putInHoldingStack(int number)
{
int bestStack = -1; //initialize to a stack index that does not exists
int bestTop = sizeOfInitialStack + 1; //initialize a larger number
for (int i = 0; i < numberOfHoldingStacks; i++)
{
//look for non-empty stack that contains a top item which is larger than
//the parameter "number" to push into.
//The one with smallest top is the best choice
if (!holdingStacks[i].isEmpty()) {
if (holdingStacks[i].peek() > number) {
bestStack = i;
break;
}
}
else {
bestStack = i;
break;
}
}
//The process cannot be completed
//since all holding stacks have its top number being smaller than
//the number to be inserted.
if (bestStack == -1)
return false;
//The process can continue, by pushing the parameter "number"
//into the holding stack of the best choice
holdingStacks[bestStack].push(number);
System.out.println("Move the number " + number + " from input stack "
+ "to holding stack#" + bestStack);
printHoldingStacks();
//update the variable "smallestNumber" to push into the output stack
//and the variable "stackWithNextSmallest" if needed
if (smallestNumber > number) {
smallestNumber = number;
stackWithNextSmallest = bestStack;
}
return true;
}
}