Skip to content

Instantly share code, notes, and snippets.

@channahnaiman channahnaiman/ Secret
Last active Jul 11, 2018

What would you like to do?

COMP 271 Lab 7

Individual project

Collaborate with your classmates on a conceptual level but do not share code. Submit individually.


An understanding of the following concepts and techniques:

  • recursion (C/A)
  • linear versus nonlinear recursion (C/A)
  • relationship between recursion and stacks
  • auxiliary methods with arguments (A)


First, start with your lab 5 solution. Then, make the following modifications:

  • TestLinkedStack:

    • add the following lines to the end of testAsListNonempty:

      final List<String> list2 = fixture.asList();
      assertEquals(2, list2.size());
    • add the following tests after testAsListNonempty:

      public void testAsFifoListEmpty() {
        assertEquals(0, fixture.asFifoList().size());
      public void testAsFifoListNonempty() {
        final String value1 = "hello";
        final String value2 = "world";
        final List<String> list = fixture.asFifoList();
        assertEquals(2, list.size());
        assertEquals(Arrays.asList(value1, value2), list);
        final List<String> list2 = fixture.asFifoList();
        assertEquals(2, list2.size());
  • IStack: add the following method at the end:

     * Returns a Java list containing the items currently in the stack.
     * The item at the bottom of the stack is the first item of the list (at index 0).
     * @post The stack remains unchanged.
     * @return The list containing the items in the stack
    List<E> asFifoList();
  • LinkedStack

    • change method asList as follows:

      public List<E> asList() {
        final ArrayList<E> result = new ArrayList<>(size);
        populateList(null, result); // TODO replace null with the right reference
        return result;
    • add the following methods at the end:

      private void populateList(final Node<E> curr, final List<E> result) {
        // TODO recursively populate the list in the desired order
      public List<E> asFifoList() {
        final ArrayList<E> result = new ArrayList<>(size);
        populateFifoList(null, result); // TODO replace null with the right reference
        return result;
      private void populateFifoList(final Node<E> curr, final List<E> result) {
        // TODO recursively populate the list in the desired order
  • ReverseLines:

    • change main as follows:

      public static void main(final String[] args) {
        final Scanner input = new Scanner(;
    • implement printReverse to recursively print the input lines in the order read and then again in reverse order:

      private static void printReverse(final Scanner input) {
        // TODO recursively read and print successive input lines until EOF, then print them out in reverse order

Finally, you are done when

  • your implementation is logically correct

  • all tests pass

  • the main method behaves as expected, e.g.,

    hello <- input line
    hello <- line echoed back by your program
    world <- input line
    world <- line echoed back by your program
    what  <- etc.
    up    <- last line printed in reverse order
    what  <- second-last line printed in reverse order
    world <- etc.

Written part

Answer the following questions:

  • What is the purpose of the various auxiliary methods populateList, populateFifoList, and ReverseLines.printReverse?

  • Why do these methods need to have arguments, and how does the argument change from one recursive call to the next?

  • What are the time and space complexity of each of the populateList populateFifoList methods, as well as ReverseLines.printReverse?

  • Which of these methods can be implemented using while loops?


  • 8 submission via GitHub
  • 24 completion of items listed above
  • 8 written part

40 points TOTAL

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.