The University of Western Australia
School of Computer Science and Software Engineering

School of Computer Science and Software Engineering

CITS2200 Data Structures and Algorithms

Warning! Exercise 3a of this labsheet is worth 2.5% of your final mark in this unit. The final date for submission is: 11:59pm Friday, 20 March 2020.

The aims of this labsheet are to:

  1. practice creating and using an interface,

  2. become familiar with the javadoc automatic documentation generation facility, and

  3. implement a block version of a stack ADT,

  4. implement a linked version of a stack ADT, and


  1. Writing and Implementing Interfaces

    A Java interface specifies a series of operations required of a class in order for the class to meet a certain behaviour or standard. That is, an interface defines the minimum functionality required of a class, without specifying how those methods should be implemented. Interfaces are used to capture the functional similarities of different types that do not necessarily constitute a hierarchical class relationship.

    The general form of an interface is:

    public interface MyInterface { public returnType myFirstMethod (argumentType argumentName, ...); public returnType mySecondMethod (...); ... }

    Notice that it has the same layout as a class file, except that:

    • the keyword interface replaces the keyword class,

    • there are no member variables, and

    • there is no code associated with the methods of the interface.

    A Java implementation is a class that provides a concrete instantiation of the functionality demanded by an interface; the class asserting it provides an implementation for all methods specified in the interface. The Java compiler ensures this compliance, generating an error if the provided coverage of methods is incorrect or incomplete.

    Java implementations are defined just like normal classes, except the additional keyword implements and an interface name is added to the class definition. For example:

    // An implementation of a Lock using an integer to store the combination public class LockInt implements Lock { private int combination; ... }

    1. In a file called, complete an interface for the combination lock question of Tutorial of Week 3. The three methods should return true if the operation succeeded (for example, if the lock opened with the combination passed to it), and false otherwise. Compile your interface to ensure you have the correct syntax. The compiler should not report any errors.

    2. Write two different implementations of the Lock interface. The first implementation (LockInt) should store the hidden combination as an integer between 000 and 999 inclusive. The second implementation (LockString) should store the hidden combination as a String.

      In both cases, the member variables should be private (obviously you don't want anyone looking at the combination!). Also, as specified by the interface and regardless of how the combination is stored, the combination must be passed to the methods of the class as an integer in both implementations. This means that the LockString implementation will need to convert the integer argument to a string.

      Compile both classes and write a small test program LockTest to ensure both implementations work.

    3. A reference variable of an interface type can "hold" an object of any class that implements that interface. For example, consider the following portion of a test program:

      Lock myLock; myLock = new LockInt(345, true); myLock.changeCombo(345, 777); if ( System.out.println("Hey, I'm in!");

      Notice that the only part of the program that refers to the specific implementation is the assignment statement on the second line. From then on, we only use the public methods available in the interface, regardless of which implementation we have picked. Try the above code and ensure your program works.

      Now change the second line to:

      myLock = new LockString(345, true);

      and confirm that the rest of the program still works correctly. If it doesn't, seek help!

      This is a powerful feature of object-oriented programming that we will be using throughout the unit to define and implement ADTs.

  2. Using javadoc

    As described in the lecture notes and the Java Programming Conventions document, all code submitted for assessment in this unit must be documented using the javadoc automatic documentation facility.

    1. Fully document your combination lock code of Question 1. You may need to reread Topic 4 of the lecture notes to understand how you can appropriately "mark-up" the code you are writing.

    2. Open a new terminal window and change to the directory that contains your code. Make a subdirectory called doc to store your javadoc documentation.

      You can run the javadoc automatic documentation generator program on a single class by entering a command of the form:

      csse2100% javadoc -d doc ./

      instructing the shell to run the javadoc program on the file in the current directory, directing the output to the doc directory.

      Typically it is more usual to run javadoc on all the files in a directory (or, once you have packages, on all your packages) as javadoc will create indices, lists of packages, etc, giving a complete linked hierarchical view of all your code, just as it does for the Java A.P.I.. You can run javadoc on a list of files by putting the names one after another, or on all Java source files in a directory by using Unix "wildcard" characters like "*" (the * wildcard character matches any string). In particular, the command:

      csse2100% javadoc -d doc ./*.java

      will produce HTML index and contents ("packages") files for all the Java source files found in the current directory.

      To view the documentation you have generated, use the Finder to navigate to your doc directory and double click on the index.html file. You should see the documentation for all your classes defined in the directory, just as it appears in the Java A.P.I.. Try the Tree and Index options at the top of the page.

      Using a graphical IDE like Eclipse you should be able to automate this process within the IDE, forcing an update to the javadoc documentation whenever the code is recompiled within the IDE. Achieving this probably requires modification of the project's build.xml XML build file - a file used by the ant program to determine which commands to execute when your code is recompiled. To learn more, and to get a better idea of what XML commands do and what additional commands are at your disposal, look at the man page for the ant program or at the online manual on the Apache Ant Project web-site. Don't be afraid to try things!

  3. Block Implementation of a Stack

    As described in the lecture notes, a stack acts as a last-in, first-out (LIFO) buffer: a collection class in which the last element added to the collection is the first element to be removed. Access to elements is via the top of the stack: the push operation adds to the top of the collection, hiding the previous top element on the stack, while the pop operation removes the top element, revealing the previously concealed top element.

    1. Write a block implementation of a stack called StackBlock. Your stack should contain the following public methods:

      1. StackBlock(s): create an empty stack of size s

      2. isEmpty(): return true iff the stack is empty, false otherwise

      3. isFull(): return true iff the stack is full, false otherwise

      4. push(o): push Object o onto the top of the stack, or throw an Overflow exception if the stack is full

      5. examine(): return the Object on top of the stack, or throw an Underflow exception if the stack is empty

      6. pop(): remove and return the Object on the top of the stack, or throw an Underflow exception if the stack is empty

      Your stack ADT must implement the CITS2200.Stack interface (that is, the Stack interface in the CITS2200 package). Fully document your code using javadoc comments.

      Warning! Submit your StackBlock implementation to cssubmit.

      If submitted before the due date, the system will compile and run your code, estimate your mark, and provide you with feedback. Final marking will occur after the posted due date and is subject to further examination, testing, and plagiarism checks of your code. Note that for security reasons, your code cannot contain any I/O commands, including printing statements. Although the auto-marking program provides you with some feedback, it should not be used as a substitute for your own testing.

    2. Write a test program that thoroughly tests each operation of your stack ADT to satisfy yourself that your code is working correctly.

  4. Linked Implementation of a Stack

    1. Write a recursive (linked) implementation of a stack of characters called StackLinked. Your stack ADT must implement the CITS2200.Stack interface. Note that while the interface allows for an Overflow exception to be thrown by the push method, this has been included only for the block representation - there is no need for your linked implementation to throw an exception in this case.

    2. Write a test program that thoroughly tests each operation of your stack ADT to satisfy yourself that your code is working correctly.

Sample solution for Lab 2

This Page