Java has a Stack class that holds elements of type Object. However, many languages do not provide stack types, so it is useful to be able to define your own. File StackADT contains an interface representing the ADT for a stack of objects and LinkedStack contains a skeleton for a class that uses a linked list to implement this interface. It depends on the Node class in Node. (This could also be defined as an inner class.) Fill in code for the following public methods: - void push(Object val) - int pop() - boolean isEmpty() - boolean isFull() In writing your methods, keep in mind that in a linked implementation of a stack, the top of stack is always at the front of the list. This makes it easy to add (push) and remove (pop) elements. File StackTest contains a simple driver to test your stack. Save it to your directory, compile it, and make sure it works.

StackADT.java

// ***************************************************************

// StackADT.java

// The classic Stack interface.

// ***************************************************************

public interface StackADT

{

// ---------------------------------------------------

// Adds a new element to the top of the stack.

// ---------------------------------------------------

public void push(Object val);

// ---------------------------------------------------

// Removes and returns the element at the top of the stack.

// ---------------------------------------------------

public Object pop();

// ---------------------------------------------------

// Returns true if stack is empty, false otherwise.

// ---------------------------------------------------

public boolean isEmpty();

// ---------------------------------------------------

// Returns true if stack is full, false otherwise.

// ---------------------------------------------------

public boolean isFull();

}

LinkedStack.java

// ***************************************************************

// LinkedStack.java

//

// A linked implementation of an Object stack class with operations push,

// pop, and isEmpty and isFull.

//

// ***************************************************************

public class LinkedStack implements StackADT

{

private Node top; // reference to top of stack

// ---------------------------------------------------

// Constructor -- initializes top

// ---------------------------------------------------

public LinkedStack()

{

}

// ---------------------------------------------------

// Adds element to top of stack if it's not full, else

// does nothing.

// ---------------------------------------------------

public void push(Object val)

{

}

// ---------------------------------------------------

// Removes and returns value at top of stack. If stack

// is empty returns null.

// ---------------------------------------------------

public Object pop()

{

}

// ---------------------------------------------------

// Returns true if stack is empty, false otherwise.

// ---------------------------------------------------

public boolean isEmpty()

{

}

// ---------------------------------------------------

// Returns true if stack is full, false otherwise.

// ---------------------------------------------------

public boolean isFull()

{

}

}

Node.java

//***********************************************************

// Node.java

// A general node for a singly linked list of objects.

//***********************************************************

public class Node

{

private Node next;

private Object element;

//----------------------------------------------------

// Creates an empty node

//----------------------------------------------------

public Node()

{

next = null;

element = null;

}

//----------------------------------------------------

// Creates a node storing a specified element

//----------------------------------------------------

public Node(Object element)

{

next = null;

this.element = element;

}

//----------------------------------------------------

// Returns the node that follows this one

//----------------------------------------------------

public Node getNext()

{

return next;

}

//----------------------------------------------------

// Sets the node that follows this one

//----------------------------------------------------

public void setNext(Node node)

{

next = node;

}

//----------------------------------------------------

// Returns the element stored in this node

//----------------------------------------------------

public Object getElement()

{

return element;

}

//----------------------------------------------------

// Sets the element stored in this node

//----------------------------------------------------

public void setElement(Object element)

{

this.element = element;

}

}

StackTest.java

// *******************************************************

// StackTest.java

//

// A simple driver that exercises push, pop, isFull and isEmpty.

// Thanks to autoboxing, we can push integers onto a stack of Objects.

//

// *******************************************************

public class StackTest

{

public static void main(String[] args)

{

StackADT stack = new LinkedStack ();

//push some stuff on the stack

for (int i=0; i<10; i++)

stack.push(i*2);

//pop and print

//should print 18 16 14 12 10 8 6 4 2 0

while (!stack.isEmpty())

System.out.print(stack.pop() + " ");

System.out.println();

//push a few more things

for (int i=1; i<=6; i++)

stack.push(i);

//should print 6 5 4 3 2 1

while (!stack.isEmpty())

System.out.print(stack.pop() + " ");

System.out.println();

}

}