Defining the Abstract Data Type Stack

The first step in implementing a data structure consists in defining the set of operations: Create a new file “StackADT.java” which contains the interface below:

interface StackADT<E>{
  void push(E x);
  E pop();
  E top();
  boolean isEmpty();
}

Stack based LinkedList implementation

  1. Go to the List interface and add a method to get the value of the head

    You should also add the implementation of the method the the LinkedList and DoublyLinkedList classes.

    public E getHead(){
 if(! empty())
     return head.data;
 return null;
}
  2. The Stack class 
    class Stack<E> implements StackADT<E> {
  //ToDo
 ...
}

Implementing the checkBalance method

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in exp.

static boolean checkBalance(String expr) {
    //ToDo
    ...
  }