Tutorial 7, CPSC 331, Winter 2012

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  tests -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23

  Stacks

About This Exercise

This exercise can be used by students to make sure that they are familiar with the properties, implementations, and applications of stacks that have been discussed in class. Students should read through and try to solve the problems on this exercise before attending the tutorial.

Expected Background and Preparation

It is assumed that students have attended the lecture in which stacks were discussed or carefully reviewed the online lecture notes that are now available.

The material on stacks in Chapter 4 of Data Structures and Algorithms in Java is also recommended.

Warmup Exercises — To Check That You Understand the Basics

It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, attended the lecture in which stacks were discussed, and read through the material about this that is listed above.

Teaching assistants will not be spending very much time in tutorials discussing these questions! Students should look at them anyway to make sure that they know how to answer them.

Students who do have difficulty with these questions, after completing the suggested reading, should contact the course instructor to get extra help.

  1. Give a brief a description of a stack. What operations does does this abstract data type support?

  2. Consider the following stack.

    A Simple Stack

    1. Draw the array that would be used to represent this stack, using the array-based representation of a stack described in class, with an array of length eight.

    2. Draw the linked list that would be used to represent this stack, using the list-based representation of a stack described in class.

    3. Show the stacks (represented using pictures like the above, as well as arrays and lists) that would result from the following sequence of operations if you started with the above stack:

      1. push(“epsilon”)
      2. pop()
      3. push(”zeta”)

  3. Consider the “Parenthesis Matching” problem that was discussed as an application of stacks during the lecture on stacks as well as the stack-based algorithm for this problem that was described.

    1. Trace the execution of the algorithm on the following expression, noting the contents of the stack after each is symbol is processed.

      (2 × [(3 × 4) − (5 × 6)])

    2. What happens if this algorithm is applied to a string that includes a left bracket that is matched by the wrong kind of right bracket, like

      [(2 × 3) - 4) + 5

      or that includes a left bracket that is not matched at all, like the following?

      ((2 × 3) + 4

    3. What happens if the algorithm is applied to an expression with an unmatched right bracket (that is preceeded by an expression with properly balanced brackets) like the following?

      (2 + 3) × 4]

  4. A second application of stacks that was described in the lecture involved the execution of recursive methods.

    After a review of this part of the lecture material, show the contents of the “process stack” during each step of the execution of the recursive fib method (that was given as part of the description of this application) when it is called, with input 4, to computer the Fibonacci number F4.

To Be Discussed in the Tutorial

  1. As discussed during the lecture about stacks, Java does include a Stack class. As the online documentation for this class indicates, this class is a subclass of Java’s Vector class,

    1. Explain why this was (arguably) a bad idea.

    2. In order to provide a less troublesome Stack class, write a class MyStack that implements the cpsc331Stack interface that you will use for Assignment 2, by applying methods that are provided by Java’s Stack class (so that each of your methods is only a few lines long) and that does not provide any other methods (that are not provided by every Object in Java).

      If you do not have time to do all of this then, at least, try to implement push, in order to make sure that you could do the rest.

    3. Finally, think about (and, as time permit, design) tests that you would write to test this class.

    Note: It is to be expected that some of the information provided during the discussion of this problem, in the tutorial, will be of use to students who are working on Assignment 2.

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial7.html