IList implementation of Stack ADT

In this assignment you will:

use the IList class hierarchy to implement the ADT Stack operations, and
use your Stack implementation to write methods that recognize strings in two different languages.

Summary: You will implement a generic Stack ADT. The data structure behind the wall will be the IList class hierarchy we studied earlier this semester. To support the generic Stack ADT, your IList will also be a generic type. Once you've implemented your generic Stack, you will use it to recognize strings in the two languages given in exercise 11 on p. 373 of the text. Since you will use an IList to implement your ADT, the class that will implement StackInterface will be named StackIListBased.

Download the starter project

Click here to download the starter project: lab5.zip.
Save it in your cs102 directory.
Unzip the file.
You should be able to Open this as an existing project in NetBeans.

Launch NetBeans and Open Project

Login and launch NetBeans.
Select "Open Project" and navigate to your cs102 folder; select the folder named "lab5"
The "Open Project Folder" button should be enabled. Click it to open the starter project.
There are many source files in this project, but the only ones you need to modify are StackIListBased.java and Main.java.

Implementing Class StackIListBased

In this class we've left the stubs (headers and empty bodies) for all the methods in the IntegerListInterface that must be implemented. You are permitted to use only the methods provided by the IList class hierarchy (data structure) to implement the ADT methods. In addition, you must override toString().

What follows is the contents of file IntegerListInterface.java--the Java interface for the ADT list you will be implementing.

public class StackIListBased<E> implements Stack<E>{
    private IList<E> stack;
    
    /** Creates a new instance of StackIListBased */
    public StackIListBased() {
      // you implement
    }
    
    /** Determines whether this stack is empty */
    public boolean isEmpty() {
      // you implement
    }
    
    /** Removes all the items from the stack */
    public void popAll( ) {
      // you implement
    }
    
    /** Pushes an item onto the top of this stack */
    public void push(E item) {
      // you implement 
    }
    
    /** 
     * Removes the object at the top of this stack and
     * returns that object as the value of this function. 
     */
    public E pop() {
      // you implement
    }
    
    /** 
     * Looks at the object at the top of this stack without
     * removing it from the stack. 
     */
    public E peek() {
      // you implement
    }
    
    /** Returns a string representation of this stack */
    public String toString() {
      // you implement
    }
}

Using StackIListBased in the Main class

Once you've implemented your StackIListBased class, you can use your stack to implement a language recognizers. In class main you will implement methods isEqualAsAndBs(). This method will recognize strings in the language described in chapter 3 exercise 11 part a. Your solution will make use of two stacks. Comments in the starter code will help you implement this algorithm.

Sample Output

When your StackIListBased class is fully implemented, and you've implemented the two static methods in Main to test whether a given string is in each respective language, running the code in Main will produce the following output:

init: deps-jar: compile: run: Strings to test: s1 = AAAABBBB s2 = AAABABBB s3 = AAABABA Membership in language EqualAsAndBs? s1? : true s2? : true s3? : false BUILD SUCCESSFUL (total time: 0 seconds)
Once you've run and verified that your StackIListBased class and methods in Main are implemented properly, you should add a few additional tests of your own. Finally, have your instructor or one of the coaches verify your solution, you are ready to submit your project.

Submitting your solution

From a terminal window, type the following commands:

cd

cd cs102

submit102 lab5