The driver program for the homework contains a recursive method called printPatt

Question

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.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<T> implements StackInterface<T> {

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<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.
@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

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<T> implements StackInterface<T> {

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<T> stack) {

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

Explanation / Answer

*******************************************************************************************************
//LinkedStack class
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<T> implements StackInterface<T> {
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 display1() {
// 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
**********************************************************************************************************
//A stack interface
/**
* An interface for the ADT stack.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
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.
* @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
**************************************************************************************************
//ArrayStack class
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<T> implements StackInterface<T> {
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 displayUsingStack() {
// YOUR CODE HERE!
if (!isEmpty()) {
for (int i = 0; i <= topIndex; i++) {
System.out.print(stack[i]);
}
} else {
System.out.println("Stack empty.");
}
}
// 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<T> stack) {
if (!stack.isEmpty()) {
StackInterface tempStack = new LinkedStack<>();
while (!stack.isEmpty()) {
tempStack.push(stack.pop());
}
while (!tempStack.isEmpty()) {
Object topEntry = tempStack.pop();
System.out.println(topEntry);
stack.push((T)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
*************************************************************************************************
//Driver class to print pattern using stack
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:");
ArrayStack displayPattern = new ArrayStack<>();
printPatternUsingStack(displayPattern,10);
displayPattern.displayUsingStack();


// 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 printPattern(int n) {
if(n>0) {
outputStars(n);
printPattern(n-1);
outputStars(n);
}
}
  
private static void outputStars(int n) {
for(int i=0; i<n;i++){
System.out.print("*");
}
System.out.println();
}
//push the values to stack for store
private static void outputStarsForPush(ArrayStack displayPattern,int n) {
for(int i=0; i<n;i++){
displayPattern.push("*");
}
displayPattern.push(" ");
}
  
public static void printPatternUsingStack(ArrayStack displayPattern,int n) {
// YOUR CODE HERE
if(n>0) {
outputStarsForPush(displayPattern,n);
printPatternUsingStack(displayPattern,n-1);
outputStarsForPush(displayPattern,n);
}
}
  
}
************************************************************************************************

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.