Question

Implement a non-recursive reverse print of linked list using stack and the main function to test: You will need to finish the printReversed_nonrecursive method in ch04.LinkedStack2 class, and the ch04.UseStack2 is the main function to test.

public class LinkedStack2<T> extends LinkedStack<T> {

    private void revPrint(LLNode<T> listRef) {
        if (listRef != null) {

            revPrint(listRef.getLink());
            System.out.println(" " + listRef.getInfo());
        }
    }

    public void printReversed() {

        revPrint(top);
    }

    /* use stack to implement non-recursive reverse print */
    public void printReversed_nonrecursive() {

    }

public class UseStack2 {

    public static void main(String[] args) {

        LinkedStack2<String> myStack2 = new LinkedStack2<String>();
        myStack2.push("first");
        myStack2.push("second");
        myStack2.push("third");
        myStack2.push("fourth");
        myStack2.printReversed();
        myStack2.printReversed_nonrecursive();
    }
}

Answer 1

public class LinkedStack2<T> extends LinkedStack<T> {

private void revPrint(LLNode<T> listRef) {
if (listRef != null) {

revPrint(listRef.getLink());
System.out.println(" " + listRef.getInfo());
}
}

public void printReversed() {
  
revPrint(top);
}

/* use stack to implement non-recursive reverse print */
public void printReversed_nonrecursive() {
   LinkedStack2<String> revStack = new LinkedStack2<String>(); 'reverse stack
   LLNode<T> listRef=top;
   while(listRef!=null){
       revStack.push(listRef.getInfo());
       listRef=listRef.getLink();
   }
   while(revStack.top!=null){
       listRef=revStack.pop();
   System.out.println(" " + listRef.getInfo());
   }      
}

public class UseStack2 {

public static void main(String[] args) {

LinkedStack2<String> myStack2 = new LinkedStack2<String>();
myStack2.push("first");
myStack2.push("second");
myStack2.push("third");
myStack2.push("fourth");
myStack2.printReversed();
myStack2.printReversed_nonrecursive();
}
}

// Base codes are missing in this class LinkedStack<T> however I have added the line of codes based on stack.

// The idea is loop through the linked list one by one and push it to stack, once completed start another loop of stack and pop it out one by one to print in reverse order.