In this lab assignment, you will create a Java application that sorts a stack re
ID: 3597152 • Letter: I
Question
In this lab assignment, you will create a Java application that sorts a stack recursively.
Consider the following algorithm to sort the entries in a stack S1:
First create two empty stacks, S2 and S3. At any given time, stack S2 will hold the entries in sorted order, with the smallest at the top of the stack. (You are sorting in ascending order.)
Put the top entry of S1 into T (a variable that can hold stack elements)
Pop and consider the top entry T of S1.
Pop entries of stack S2 and push them onto stack S3 until you reach the correct place to put T.
Then push T onto S2.
Next move entries from S3 to S2.
Repeat until S1 is empty and S2 contains the sorted stack.
Requirements:
Your application uses unbounded stacks from chapter 2 in your text.
Write a main method to create an unsorted stack and display the unsorted stack.
Send the stack to a method for sorting. Upon return from the method, display the now sorted stack.
Write a recursive method that accepts an unsorted Stack and returns a sorted Stack. The method should be generic and work for all types of stacks.
Test your recursive method to make sure it works for different types of stacks.
Hint: May want to use a public method that accepts the original stack and then creates the two additional stacks needed. This method then calls a private method that accepts all three stacks and does the recursive sort. Your methods should make sure all types of stacks passed contain comparable objects. Refer to the generic presentation in Shared Files.
unboundedstack.java
import java.util.ArrayList;
public class UnboundedStack <T>
{
protected ArrayList<T> element;
public UnboundedStack()
{
element = new ArrayList<T>();
}
public T peek() throws StackUnderflowException
{
T topofstack = null;
if(isEmpty())
{
throw new StackUnderflowException("Empty Stack");
}
else
topofstack = element.get(element.size() - 1);
return topofstack;
}
public void pop() throws StackUnderflowException
{
if(isEmpty())
{
throw new StackUnderflowException("empty stack");
}
else
element.remove(element.size() - 1);
}
public void push(T elements) throws StackOverFlowException
{
element.add(elements);
}
public boolean isEmpty()
{
return (element.size() == 0);
}
public boolean isFull()
{
return false;
}
}
Explanation / Answer
Hello.Here is the complete code for your program "unboundedstack.java" .
import java.util.ArrayList;
public class UnboundedStack <T>
{
protected ArrayList<T> element;
public UnboundedStack()
{
element = new ArrayList<T>();
}
public T peek() throws StackUnderflowException
{
T topofstack = null;
if(isEmpty())
{
throw new StackUnderflowException("Empty Stack");
}
else
topofstack = element.get(element.size() - 1);
return topofstack;
}
public T pop() throws StackUnderflowException
{
if(isEmpty())
{
throw new StackUnderflowException("empty stack");
}
else
return element.get(element.size() - 1);
element.remove(element.size() - 1);
}
public void push(T elements) throws StackOverFlowException
{
element.add(elements);
}
public boolean isEmpty()
{
return (element.size() == 0);
}
public boolean isFull()
{
return false;
}
}
class SortedDemo
{
public static void main(String args[ ])
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("How many stacks to sort:");
int n=Integer.parseInt(br.readLine().trim());
for(i=1 ; i<=n ; i++)
{
accept();
}
public void accept( )
{
UnboundedStack S1=new UnboundedStack();
System.out.println("Enter values to stack:");
T x=br.readLine();
S1.push(x);
System.out.println("The unsorted stack is:");
while(!S1.isEmpty())
{
System.out.println("S1.peek()");
}
UnboundedStack S2=new UnboundedStack();
UnboundedStack S3=new UnboundedStack();
SortStacks(UnboundedStack S1,UnboundedStack S2,UnboundedStack S3);
}
private void SortStacks(UnboundedStack S1,UnboundedStack S2,UnboundedStack S3)
{
while(!S1.isEmpty())
{
T top=S1.peek();
S1.pop();
while(top > S2.pop())
{
T t1=S2.pop();
S3.push(t1);
}
S2.push(top);
T t2=S3.pop();
S2.push(t2); //S2 contains sorted stack
System.out.println("The sorted stack is:");
while(!S2.isEmpty())
{
System.out.println("S2.peek()");
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.