Description
Further understanding of interfaces
Introduction to the applications of stacks
Introduction to the implementation of stacks
Review of inheritance concepts
Part I
Interface
1 Combination
Let’s revisit the class Combination from laboratory 1. Make all the necessary changes to the class
Combination (see below) so that it implements the interface java.lang.Comparable.
public interface Comparable
// Compares this object with the specified object for order.
// Returns a negative integer, zero, or a positive integer
// as this object is less than, equal to, or greater than the
// specified object.
public int compareTo( E other );
}
When two Combination objects are compared, the first pair of values is compared first, if the value of this
object is smaller than that of the other then the method will return -1, if it is greater, then it will return 1, if
those values are equal, then the second pair of values is considered, the value -1 or 1 will be returned if the
second value of this object is smaller than that of the second, finally, if those values are also equal then the
third pair of values is considered.
Comparable is part of a package, called lang, that is imported by default. Therefore, no need to import
Comparable.
Write a test program for thouroughly testing your implementation.
File:
Combination.java
ITI 1121. Introduction to Computer Science II 2015-06-16, 11:39
http://www.site.uottawa.ca/~lucia/courses/ITI1121-15/labs/t07/index.html Page 2 of 5
Part II
Stacks
Introduction
This laboratory is about an implementation of the interface Stack as well as an application
2 Modifying the interface Stack: adding a method clear()
Modify the interface Stack below adding an abstract method public void clear().
public interface Stack
public abstract boolean isEmpty();
public abstract E peek();
public abstract E pop();
public abstract void push( E element );
}
File:
Stack.java
3 Implementing the method clear() in the class ArrayStack
The class ArrayStack uses a fixed-size array and implements the interface Stack. Now that the interface
Stack has been modified to have a method clear(), the current implementation of the class ArrayStack is
broken (try compiling it without making any change, what is the error message displayed?).
Since the class ArrayStack implements the interface Stack, it has to provide an implementation for all
the methods that are declared by the interface. Consequently, write an implementation for the method void
clear(). It removes all of the elements from this ArrayStack. The stack will be empty after this call returns.
Files:
ArrayStack.java
L4Q2.java
4 Quiz (1 mark)
Write out the order of the elements that are contained in a stack (designated by s) after the following
operations are performed. Make sure to indicate which element is the top element.
s.push( new Integer( 8 ) );
s.push( new Integer( 6 ) );
Integer num = s.pop();
s.push( new Integer( 3 ) );
ITI 1121. Introduction to Computer Science II 2015-06-16, 11:39
http://www.site.uottawa.ca/~lucia/courses/ITI1121-15/labs/t07/index.html Page 3 of 5
s.push( new Integer( 4 ) );
s.push( new Integer( 15 ) );
s.push( new Integer( 12 ) );
s.pop();
s.pop();
s.pop();
s.push( new Integer( 19 ) );
Answer:
Submit your answer using Blackboard Learn:
https://uottawa.blackboard.com/
5 Algo1
For this part of the laboratory, you will experiment with two algorithms for validating expressions containing
parentheses (round, curly and square parentheses).
The class Balanced contains a simple algorithm to validate expressions. Observation: for an expression
consisting of well balanced parentheses the the number of opening ones is the same as the closing ones. This
suggest an algorithm:
public static boolean algo1( String s ) {
int curly = 0;
int square = 0;
int round = 0;
for ( int i=0; i