Lab 4

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
    ...
  }