CS 112
Spring 2022

Old version

This is the CS 112 site as it appeared on May 12, 2022.

Lab 10: Stacks and Queues

Task 0: Prepare for lab

Download the following zip file: lab10.zip

Unzip this archive, and you should find a folder named `lab10, and within it the files you will need for this lab.

Task 1: Understanding stacks

Your work for the first part of this task should be done on paper. Please show your work to a staff member before you leave the lab.

  1. Given the following stack, depicted here from top to bottom:

    +     +
| "f" |  top
| "e" |
| "a" |
| "c" |
| "b" |
+-----+

    Show what the stack look like after each of the following sequence of pushes and pops:

    pop()
push("x")
push("w")
str = pop()
pop()
push("z")
push(str)

  2. Create a client program called StackClient with a main() method in which you do the following:

    1. Construct a stack object (either an ArrayStack or an LLStack) and assign it to a variable.

      Hint: Don’t forget that our stack implementations are generic classes, so you’ll need to specify the type of item when you declare the variable and when you construct the stack object. For example:

      Stack<...> s1 = new ArrayStack<...>();
or 
Stack<...> s1 = new LLStack<...>();

      where you replace the ... with the appropriate data type. You can create a reference to either stack implementation and the methods will produce the same results.

    2. Perform a series of pushes to create the stack shown at the beginning of this task. Make sure that you push them in the appropriate order!

    3. Print the stack, which should show you the items from top to bottom as follows:

      {f, e, a, c, b}

      If you don’t see this result, modify your calls to push() as needed.

    4. Perform the above sequence of modifications to the stack. When you assign the result of the second call to pop() to a variable, you will not need a type cast. Why not?

    5. Reprint the stack after all of those operations have been performed. Doing so should provide the following output:

      {w, z, e, a, c, b}

  3. Could you add code to your client program that removes the "z" without first removing another item? Why or why not?

Task 2: Use a stack to check for balanced delimiters

In lecture, we discussed how you could use a stack to check if the delimiters in an expression (i.e., the parentheses, brackets, and curly braces) are properly balanced. In this task, you will complete code that does this.

  1. We’ve given you some starter code in Lab10Task2.java. However, it includes a syntax error. Compile the file to see the error.

  2. The error stems from the fact that generic classes in Java require you to use reference types – types that represent objects. Therefore, we can’t use a primitive type like char when we declare or create an instance of a generic collection.

    Instead, Java provides a “wrapper class” for each primitive type that allows us to treat primitive values as if they were objects. In the case of char, the corresponding wrapper class is called Character.

    Change the code so that it uses this wrapper class when declaring and creating the stack that we’re using in this task. Feel free to ask for help as needed.

  3. We have given you three helper methods: isLeftDelim(), isRightDelim(), and matches().

    Review these methods, reading the comments that accompany them and examining how they work.

    At the moment, they each support two types of delimiters but not the third. Extend each method so that it supports all three types of delimiters. Here are some test cases:

    System.out.println(Lab10Task2.isLeftDelim('('));
true

System.out.println(Lab10Task2.isLeftDelim('{'));
true

System.out.println(Lab10Task2.isLeftDelim(']'));
false

System.out.println(Lab10Task2.isRightDelim(']'));
true

System.out.println(Lab10Task2.isRightDelim('}'));
true

System.out.println(Lab10Task2.isRightDelim('('));
false

System.out.printkn(Lab10Task2.matches('[', ']'));
true

System.out.println(Lab10Task2.matches('{', '}'));
true

System.out.println(Lab10Task2.matches('(', '}'));
false

  4. The key method for delimiter checking is called isBalanced(). We have given you a partial implementation, and you should complete it. Consult the lecture notes on delimiter checking as needed to remind yourself of how we can use a stack for this purpose.

    In particular, you will need to:

    • Add code that properly handles right delimiters. As you do so, take advantage of the helper methods.

    • Make whatever other changes are needed so that the method returns true when the delimiters are balanced and false when they are not.

    Here are some test calls:

    System.out.println( Lab10Task2.isBalanced("[(3 + 2) * 7] / 2") );
true

System.out.println( Lab10Task2.isBalanced("[(3 + 2] * 7) / 2") );
false

System.out.println( Lab10Task2.isBalanced("[(({}))]") );
true

System.out.println( Lab10Task2.isBalanced("[(({))]}") );
false

System.out.println( Lab10Task2.isBalanced("((((())") );
false

System.out.println( Lab10Task2.isBalanced("(())))") );
false

Task 3: Use collection objects to divide numbers into subgroups

Suppose that we have an array containing integers between 0 and 999, and that we want to divide these integers into subgroups based on how many digits they have. In Lab10Task3.java, you will complete a method that does this.

The method is called divideByLength(). In takes an array of integers called values that we will assume contains integers between 0 and 999. It should return a list (either an ArrayList or LLList) in which:

For example:

int[] vals = {7, 300, 55, 3, 213, 24, 78, 8, 411};
List results = Lab10Task3.divideByLength(vals);
System.out.println( results );

Should produce:
{7, 3, 8, 55, 24, 78, 300, 213, 411}

Note that the method does not sort the numbers in increasing order by value. Rather, it reorders them based on how many digits they have.

Requirements:

Two other notes: