I have this code and it wont work, basically I just have to arrange the two stac
ID: 3713447 • Letter: I
Question
I have this code and it wont work, basically I just have to arrange the two stacks so that they are in numerical order. this is what i have
import java.io.*;
import java.util.*;
/**
* StackSort is a program that will use two stacks to sort an array of integer values.
*
* @author Charles Hoot
* @version 4.0
*/
public class StackSort {
public static void main(String args[]) {
int data[] = null;
int result[] = null;
Scanner input;
input = new Scanner(System.in);
System.out.println("This program sorts an array of integer values.");
// Create an empty array of integers
data = createArray(0, 1, 1);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with one integer
data = createArray(1, 0, 9);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with two integers
data = createArray(2, 0, 9);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with 10 integers
data = createArray(10, 0, 9999);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with 20 integers
data = createArray(20, 0, 9);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
System.out.println("Please enter the number of values to sort");
int size = getInt(" It should be an integer value greater than or equal to 1.");
// Create an array of the given size
data = createArray(size, 0, 99);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
}
/**
* Use two stacks to sort the data in an array
*
* @param data An array of integer values to be sorted.
* @return An array of sorted integers.
*/
private static int[] doStackSort(int data[]) {
int result[] = new int[data.length];
int temp = 0;
// ADD CODE HERE TO SORT THE ARRAY USING TWO STACKS
VectorStack<Integer> lowerValues = new VectorStack<Integer>();
VectorStack<Integer> upperValues = new VectorStack<Integer>();
for(int i = 0 ; i < data.length ; i ++)
{
lowerValues.push(data[i]);
}
while(!lowerValues.isEmpty()){ //while the lower values are not empty
temp = lowerValues.pop();
while((upperValues.isEmpty() && temp < upperValues.peek())) //if the upper values are empty and is greater than temp
{
lowerValues.push(upperValues.pop()); //push the pop of the upper value
}
upperValues.push(temp);
}
while(!upperValues.isEmpty())
{
for(int b = 0 ; b < data.length ; b++)
{
result[b] = upperValues.pop();
System.out.println(result[b]);
}
}
return result;
}
/* for(int i = 0 ; i < data.length ; i ++)
{
upperValues.push(data[i]);
}
for(int x = 0 ; x < data.length ; x++){
result[x]= upperValues.pop();
} */
// return result;
/**
* Load an array with data values
*
* @param size The number of data values to generate and place in the array.
* @param min The minimum value to generate.
* @param max The maximum value to generate.
* @return An array of randomly generated integers.
*/
private static int[] createArray(int size, int min, int max) {
Random generator = new Random();
// If we get a negative size, just make the size 1
if (size < 0) {
size = 1;
}
// We need max > min for the random number generator to be happy
if (max <= min) {
max = min + 1;
}
int[] data = new int[size];
for (int i = 0; i < size; i++) {
data[i] = min + generator.nextInt(max - min);
}
return data;
}
/**
* Create a string with the data values from an array
*
* @param data An array of integer values.
* @return A string representation of the array.
*/
private static String representationOfArray(int data[]) {
String result = new String("< ");
for (int i = 0; i < data.length; i++) {
result += data[i] + " ";
}
result += ">";
return result;
}
/**
* Get an integer value
*
* @return An integer.
*/
private static int getInt(String rangePrompt) {
Scanner input;
int result = 10; //default value is 10
try {
input = new Scanner(System.in);
System.out.println(rangePrompt);
result = input.nextInt();
} catch (NumberFormatException e) {
System.out.println("Could not convert input to an integer");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
} catch (Exception e) {
System.out.println("There was an error with System.in");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
}
and these are the other classes :
import java.util.EmptyStackException;
import java.util.Vector;
/**
A class of stacks whose entries are stored in a vector.
@author Frank M. Carrano
* This code is from Chapter 6 of
* Data Structures and Abstractions with Java 4/e
* by Carrano
*
* toString method overridden to give a better display by Charles Hoot
* version 4.0
*/
public final class VectorStack<T> implements StackInterface<T> {
private Vector<T> stack; // Last element is the top entry in stack
private boolean initialized = false;
private static final int DEFAULT_INITIAL_CAPACITY = 50;
private static final int MAX_CAPACITY = 10000;
public VectorStack() {
this(DEFAULT_INITIAL_CAPACITY);
} // end default constructor
public VectorStack(int initialCapacity) {
checkCapacity(initialCapacity);
stack = new Vector<T>(initialCapacity);// Size doubles as needed
initialized = true;
} // end constructor
/** Throws an exception if this object is not initialized.
*
*/
private void checkInitialization()
{
if (!initialized)
throw new SecurityException("VectorStack object is not initialized " +
"properly.");
}
/** Determine if the asked for capacity is less than the maximum.
@param desiredCapacity The requested capacity for the stack
*/
private void checkCapacity(int desiredCapacity){
if (desiredCapacity > MAX_CAPACITY)
throw new IllegalStateException("Attempt to create a stack " +
"whose capacity exceeds " +
"allowed maximum.");
} // end checkCapacity
/** Adds a new entry to the top of this stack.
@param newEntry an object to be added to the stack */
public void push(T newEntry){
checkInitialization();
stack.add(newEntry);
}
/** Removes and returns this stack’s top entry.
@return The object at the top of the stack.
@throws EmptyStackException if the stack is empty before the operation. */
public T pop() {
checkInitialization();
if (isEmpty()) {
throw new EmptyStackException();
} else {
return stack.remove(stack.size() - 1);
}
} // end pop
/** Retrieves this stack’s top entry.
@return The object at the top of the stack or null if
@throws EmptyStackException if the stack is empty. */
public T peek(){
checkInitialization();
if(isEmpty())
throw new EmptyStackException();
else
return stack.lastElement();
} // end peek
/** Detects whether this stack is empty.
@return True if the stack is empty. */
public boolean isEmpty(){
return stack.isEmpty();
} // end isEmpty
/** Removes all entries from this stack */
public void clear(){
stack.clear();
} // end celar
/** Override the toString() method so that we get a more useful display of
* the contents in the stack.
* @return A string representation of the contents of the stack. */
public String toString() {
String result = "Stack[ ";
for (int index = 0; index < stack.size(); index++) {
result += stack.get(index) + " ";
} // end for
result += "]*Top*";
return result;
}
} // end VectorStack
import java.util.EmptyStackException;
/**
An interface that describes the operations of a stack of objects.
@author Frank M. Carrano
* This code is from Chapter 5 of
* Data Structures and Abstractions with Java 4/e
* by Carrano
*/
public interface StackInterface<T> {
/** Adds a new entry to the top of this stack.
@param newEntry An object to be added to the stack. */
public void push(T newEntry);
/** Removes and returns this stack’s top entry.
@return The object at the top of the stack.
@throws EmptyStackException if the stack is empty before the operation. */
public T pop();
/** Retrieves this stack’s top entry.
@return The object at the top of the stack or null if
@throws EmptyStackException if the stack is empty. */
public T peek();
/** Detects whether this stack is empty.
@return True if the stack is empty. */
public boolean isEmpty();
/** Removes all entries from this stack */
public void clear();
} // end StackInterface
I only have to edit the StackSort class
return result;
}
}
Explanation / Answer
I found your error. It was a small logical issue.
In the line below
while ((upperValues.isEmpty() && temp < upperValues.peek())) in doStackSort method, you are checking if upperValues vectorStack is empty, and if its empty you are trying to peek its first element. This is not valid. If the Vector stack is empty, it dont have any element so we cannot peek into its first element.
So we need to change this line to this
while ((!upperValues.isEmpty() && temp < upperValues.peek()))
i.e. We need to check if upperValues is not empty, then only we need to peek its element. else add it.
I have updated your StackSort class and its working fine. Below is your java code. Please let me know if you have any issues uderstanding this logical error.
Dont forget to rate this question positive if it helped.
/**
* StackSort is a program that will use two stacks to sort an array of integer
* values.
*
* @author Charles Hoot
* @version 4.0
*/
public class StackSort {
public static void main(String args[]) {
int data[] = null;
int result[] = null;
Scanner input;
input = new Scanner(System.in);
System.out.println("This program sorts an array of integer values.");
// Create an empty array of integers
data = createArray(0, 1, 1);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with one integer
data = createArray(1, 0, 9);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with two integers
data = createArray(2, 0, 9);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with 10 integers
data = createArray(10, 0, 9999);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
// Create an array with 20 integers
data = createArray(20, 0, 9);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
System.out.println("Please enter the number of values to sort");
int size = getInt(" It should be an integer value greater than or equal to 1.");
// Create an array of the given size
data = createArray(size, 0, 99);
System.out.println("Original array is: " + representationOfArray(data));
result = doStackSort(data);
System.out.println("Sorted array is: " + representationOfArray(result));
System.out.println();
}
/**
* Use two stacks to sort the data in an array
*
* @param data
* An array of integer values to be sorted.
* @return An array of sorted integers.
*/
private static int[] doStackSort(int data[]) {
int result[] = new int[data.length];
int temp = 0;
// ADD CODE HERE TO SORT THE ARRAY USING TWO STACKS
VectorStack<Integer> lowerValues = new VectorStack<Integer>();
VectorStack<Integer> upperValues = new VectorStack<Integer>();
for (int i = 0; i < data.length; i++)
{
lowerValues.push(data[i]);
}
while (!lowerValues.isEmpty()) { // while the lower values are not empty
temp = lowerValues.pop();
while ((!upperValues.isEmpty() && temp < upperValues.peek()))
{
lowerValues.push(upperValues.pop()); // push the pop of the
// upper value
}
upperValues.push(temp);
}
while (!upperValues.isEmpty()) {
for (int b = 0; b < data.length; b++) {
result[b] = upperValues.pop();
System.out.println(result[b]);
}
}
return result;
}
/*
* for(int i = 0 ; i < data.length ; i ++)
*
* {
*
*
*
*
*
*
*
* upperValues.push(data[i]); } for(int x = 0 ; x < data.length ; x++){
*
* result[x]= upperValues.pop(); }
*/
// return result;
/**
* Load an array with data values
*
* @param size
* The number of data values to generate and place in the array.
* @param min
* The minimum value to generate.
* @param max
* The maximum value to generate.
* @return An array of randomly generated integers.
*/
private static int[] createArray(int size, int min, int max) {
Random generator = new Random();
// If we get a negative size, just make the size 1
if (size < 0) {
size = 1;
}
// We need max > min for the random number generator to be happy
if (max <= min) {
max = min + 1;
}
int[] data = new int[size];
for (int i = 0; i < size; i++) {
data[i] = min + generator.nextInt(max - min);
}
return data;
}
/**
* Create a string with the data values from an array
*
* @param data
* An array of integer values.
* @return A string representation of the array.
*/
private static String representationOfArray(int data[]) {
String result = new String("< ");
for (int i = 0; i < data.length; i++) {
result += data[i] + " ";
}
result += ">";
return result;
}
/**
* Get an integer value
*
* @return An integer.
*/
private static int getInt(String rangePrompt) {
Scanner input;
int result = 10; // default value is 10
try {
input = new Scanner(System.in);
System.out.println(rangePrompt);
result = input.nextInt();
} catch (NumberFormatException e) {
System.out.println("Could not convert input to an integer");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
} catch (Exception e) {
System.out.println("There was an error with System.in");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
}
return result;
}
}
Output
This program sorts an array of integer values.
Original array is: < >
Sorted array is: < >
Original array is: < 1 >
1
Sorted array is: < 1 >
Original array is: < 4 8 >
8
4
Sorted array is: < 8 4 >
Original array is: < 4217 3401 1381 956 5441 4906 1959 3376 293 1510 >
5441
4906
4217
3401
3376
1959
1510
1381
956
293
Sorted array is: < 5441 4906 4217 3401 3376 1959 1510 1381 956 293 >
Original array is: < 0 2 8 7 7 3 2 3 0 5 7 2 4 5 7 4 1 7 0 2 >
8
7
7
7
7
7
5
5
4
4
3
3
2
2
2
2
1
0
0
0
Sorted array is: < 8 7 7 7 7 7 5 5 4 4 3 3 2 2 2 2 1 0 0 0 >
Please enter the number of values to sort
It should be an integer value greater than or equal to 1.
10
Original array is: < 96 44 75 62 55 70 57 21 14 26 >
96
75
70
62
57
55
44
26
21
14
Sorted array is: < 96 75 70 62 57 55 44 26 21 14 >