CODE IN JAVA

LinkedStack.java

public class LinkedStack implements Stack {

private SinglyLinkedList list = new SinglyLinkedList();

public LinkedStack(){}

public int size(){

return list.size();

}

public boolean isEmpty(){

return list.isEmpty();

}

public void push(E element) {

list.addFirst(element);

}

public E top(){

return list.first();

}

public E pop(){

return list.removeFirst();

}

}

Stack.java

public interface Stack {

/**

* Returns the number of elements in the stack.

* @return number of elements in the stack

*/

int size();

/**

* Tests whether the stack is empty.

* @return true if the stack is empty, false otherwise

*/

boolean isEmpty();

/**

* Inserts an element at the top of the stack.

* @param e the element to be inserted

*/

void push(E e);

/**

* Returns, but does not remove, the element at the top of the stack.

* @return top element in the stack (or null if empty)

*/

E top();

/**

* Removes and returns the top element from the stack.

* @return element removed (or null if empty)

*/

E pop();

}

SinglyLinkedList.java

public class SinglyLinkedList {

//---------------- nested Node class ----------------

private static class Node {

private E element;

private Node next;

public Node(E e, Node n) {

element = e;

next = n;

}

public E getElement() {

return element;

}

public Node getNext() {

return next;

}

public void setNext(Node n) {

next = n;

}

} //----------- end of nested Node class -----------

private Node head = null;

private Node tail = null;

private int size = 0;

public SinglyLinkedList() {

}

public int size() {

return size;

}

public boolean isEmpty() {

return size == 0;

}

public E first() {

if (isEmpty()) {

return null;

}

return head.getElement();

}

public E last() {

if (isEmpty()) {

return null;

}

return tail.getElement();

}

// update methods

public void addFirst(E e) {

head = new Node(e, head);

if (size == 0) {

tail = head;

}

size++;

}

public void addLast(E e) {

Node newest = new Node(e, null);

if (isEmpty()) {

head = newest;

} else {

tail.setNext(newest);

}

tail = newest;

size++;

}

public E removeFirst() {

if (isEmpty()) {

return null;

}

E answer = head.getElement();

head = head.getNext();

size--;

if (size == 0) {

tail = null;

}

return answer;

}

public String toString() {

StringBuilder sb = new StringBuilder("[");

Node n = head;

while (n != null) {

sb.append(n.getElement());

if (!n.equals(tail)) {

sb.append(", ");

}

n = n.getNext();

}

sb.append("]");

return sb.toString();

}

}

1. Implement the generic LinkedStack that we covered in class. The Stack interface of our ADT is provided. Note that you will need the SinglyLinkedList class from Lab 3. a. In a Lab4_driver class, create a static method ispalindrome that determines if a word is a palindrome (i.e., reads the same backwards as forwards). - declare a Stack as an instance of LinkedStack that holds Character objects Use this stack to check if the word (passed as a parameter) is a palindrome and return the Boolean result. b. Store the following strings in an array: tracer Racecar a Hannah 99 Baabaa Stats Hedwig Colon Abba baabaab Iterate through the list to check whether or not the word is a palindrome. C. Display the list of words and the result of each palindrome test. - Sample Output: tracer is NOT a palindrome Racecar is a palindrome