Question: The driver program for the homework contains a recursive method called printPattern that uses recursion to print a pattern like this: *** ** * **
The driver program for the homework contains a recursive method called printPattern that uses recursion to print a pattern like this:
*** ** * ** ***
Write a complete method that prints the same pattern using a stack.
Notes:
You can invoke the private outputStars method from your method.
Use only the traditional stack methods of push, pop, peek, and isEmpty.
For full credit, do not use any other data structure.
You can use additional variables (e.g., boolean, int).
Driver:
import java.util.*; public class HomeworkM12Driver { public static void main(String[] args) { // Q16 print in add order StackInterface s = new LinkedStack<>(); System.out.println("**********Q16"); System.out.println("Should print cat, dog, hamster, zebra (one per line)"); s.push("cat"); s.push("dog"); s.push("hamster"); s.push("zebra"); printInAddOrder(s); System.out.println(); // Q17 display method- LinkedStack System.out.println("**********Q17"); LinkedStack displayLinkedStack = new LinkedStack<>(); System.out.println("Should give a message that the stack is empty."); displayLinkedStack.display(); displayLinkedStack.push("Alaska"); displayLinkedStack.push("Delaware"); displayLinkedStack.push("Iowa"); displayLinkedStack.push("New York"); System.out.println("Should print BOTTOM Alaska Delaware Iowa New York TOP"); displayLinkedStack.display(); // Q18 display method- v System.out.println("**********Q18"); ArrayStack displayArrayStack = new ArrayStack<>(); System.out.println("Should give a message that the stack is empty."); displayArrayStack.display(); displayArrayStack.push("California"); displayArrayStack.push("Florida"); displayArrayStack.push("Georgia"); displayArrayStack.push("Hawaii"); System.out.println("Should print BOTTOM California Florida Georgia Hawaii TOP"); displayArrayStack.display(); System.out.println(); // Q19 star pattern System.out.println("**********Q19"); System.out.println("Recursive pattern:"); printPattern(10); System.out.println("Stack pattern should be the same:"); printPatternUsingStack(10); // QEC1 peek2 in LinkedStack /* System.out.println("**********EC1"); LinkedStack peekStackLinked = new LinkedStack(); System.out.println("Should print null/throw exception: " + peekStackLinked.peek2()); peekStackLinked.push("hello"); System.out.println("Should print null/throw exception: " + peekStackLinked.peek2()); peekStackLinked.push("goodbye"); System.out.println("Should print hello: " + peekStackLinked.peek2()); peekStackLinked.push("and good night"); System.out.println("Should print goodbye: " + peekStackLinked.peek2()); System.out.println(); */ //QEC2 peek2 in ArrayStack /* System.out.println("**********QEC2"); ArrayStack peekStackArray = new ArrayStack(); System.out.println("Should print null/throw exception: " + peekStackArray.peek2()); peekStackArray.push("hello"); System.out.println("Should print null/throw exception: " + peekStackArray.peek2()); peekStackArray.push("goodbye"); System.out.println("Should print hello: " + peekStackArray.peek2()); peekStackArray.push("and good night"); System.out.println("Should print goodbye: " + peekStackArray.peek2()); System.out.println(); */ } public static void printInAddOrder(StackInterface stack) { // YOUR CODE HERE! } public static void printPattern(int n) { if(n>0) { outputStars(n); printPattern(n-1); outputStars(n); } } private static void outputStars(int n) { for(int i=0; i"*"); } System.out.println(); } public static void printPatternUsingStack(int n) { // YOUR CODE HERE } } import java.util.EmptyStackException;
/**
* A class of stacks whose entries are stored in a chain of nodes.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public final class LinkedStack
private Node topNode; // References the first node in the chain
public LinkedStack() {
topNode = null;
} // end default constructor
public void push(T newEntry) {
topNode = new Node(newEntry, topNode);
// Node newNode = new Node(newEntry, topNode);
// topNode = newNode;
} // end push
public T peek() {
if (isEmpty())
throw new EmptyStackException();
else
return topNode.getData();
} // end peek
public T pop() {
T top = peek(); // Might throw EmptyStackException
assert (topNode != null);
topNode = topNode.getNextNode();
return top;
} // end pop
/*
* // Question 1, Chapter 6: Does not call peek public T pop() { if
* (isEmpty()) throw new EmptyStackException(); else { assert (topNode !=
* null); top = topNode.getData(); topNode = topNode.getNextNode(); } // end
* if
*
* return top; } // end pop
*/
public boolean isEmpty() {
return topNode == null;
} // end isEmpty
public void clear() {
topNode = null; // Causes deallocation of nodes in the chain
} // end clear
public void display() {
// YOUR CODE HERE!
}
private class Node {
private T data; // Entry in stack
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node linkPortion) {
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData() {
return data;
} // end getData
private void setData(T newData) {
data = newData;
} // end setData
private Node getNextNode() {
return next;
} // end getNextNode
private void setNextNode(Node nextNode) {
next = nextNode;
} // end setNextNode
} // end Node
public void display(){
if(!isEmpty()){
System.out.print("Bottom");
helperReverseDisplay(topNode);
System.out.print("Top");
}else{
System.out.println("Stack empty.");
}
}
private void helperReverseDisplay(Node current){
if(current.next == null){
System.out.println("" + current.data + "");
} else{
helperReverseDisplay(current.next);
}
}
} // end LinkedStackd
/** An interface for the ADT stack. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ public interface StackInterface
import java.util.Arrays;
import java.util.EmptyStackException;
/**
* A class of stacks whose entries are stored in an array.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public final class ArrayStack
private T[] stack; // Array of stack entries
private int topIndex; // Index of top entry
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 50;
private static final int MAX_CAPACITY = 10000;
public ArrayStack() {
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayStack(int initialCapacity) {
checkCapacity(initialCapacity);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempStack = (T[]) new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
initialized = true;
} // end constructor
public void push(T newEntry) {
checkInitialization();
ensureCapacity();
stack[topIndex + 1] = newEntry;
topIndex++;
} // end push
public T peek() {
checkInitialization();
if (isEmpty())
throw new EmptyStackException();
else
return stack[topIndex];
} // end peek
public T pop() {
checkInitialization();
if (isEmpty())
throw new EmptyStackException();
else {
T top = stack[topIndex];
stack[topIndex] = null;
topIndex--;
return top;
} // end if
} // end pop
public boolean isEmpty() {
return topIndex < 0;
} // end isEmpty
public void clear() {
checkInitialization();
// Remove references to the objects in the stack,
// but do not deallocate the array
while (topIndex > -1) {
stack[topIndex] = null;
topIndex--;
} // end while
// Assertion: topIndex is -1
} // end clear
public void display() {
// YOUR CODE HERE!
}
// Throws an exception if this object is not initialized.
private void checkInitialization() {
if (!initialized)
throw new SecurityException(
"ArrayStack object is not initialized properly.");
} // end checkInitialization
// Throws an exception if the client requests a capacity that is too large.
private void checkCapacity(int capacity) {
if (capacity > MAX_CAPACITY)
throw new IllegalStateException("Attempt to create a stack "
+ "whose capacity exceeds " + "allowed maximum.");
} // end checkCapacity
// Doubles the size of the array stack if it is full
// Precondition: checkInitialization has been called.
private void ensureCapacity() {
if (topIndex >= stack.length - 1) // If array is full, double its size
{
int newLength = 2 * stack.length;
checkCapacity(newLength);
stack = Arrays.copyOf(stack, newLength);
} // end if
} // end ensureCapacity
public void printInAddOrder(StackInterface
if(!stack.isEmpty()) {
StackInterfac tempStack = new LinkedStack<>();
while(!stack.isEmpty()) {
tempStack.push(stack.pop());
}
while(!tempStack.isEmpty()) {
Object topEntry = tempStack.pop();
System.out.println(topEntry);
stack.push(topEntry);
}
}
}
public void display(){
if(!isEmpty()){
System.out.print("BOTTOM");
for(int i=0; i<= topIndex; i++){
System.out.print(stack[i] + "" + "TOP");
}
} else{
System.out.println("Stack empty.");
}
}
} // end ArrayStack
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help