Question:

Write java code to build a Stack using a NodePositionList as the underlying data structure. You should assume the NodePositionList has the PositionList interface as shown on below, use the methods shown. You should use the adapter pattern discussed below. Your class (NodeListStack) should merely call the NodeList methods. It must be able to satisfy the exception behavior specified by the Stack ADT. You do not need to actually compile this; however, it should be correct java.

/////////////////////////////////////////////////////////////////////////////////////////////////

positional list ADT:

addFirst(e): Inserts a new element e at the front of the list, returning the position of the new element. addLast(e): Inserts a new element e at the back of the list, returning the position of the new element. addBefore(p, e): Inserts a new element e in the list, just before position p, returning the position of the new element. addAfter(p, e): Inserts a new element e in the list, just after position p, returning the position of the new element. set(p, e): Replaces the element at position p with element e, returning the element formerly at position p. remove(p): Removes and returns the element at position p in the list, invalidating the position.

///////////////////////////////////////////////////////////////////////////////////////////////

Some useful details and given hints:

Stack Method	Queue Method	Deque Method
size ()	size()	size()
isEmpty()	IsEmpty()	isEmpty()
top()		last()
	front()	first()
push()	enqueue()	insertLast()
pop()		removeLast()
	dequeue()	removeFirst()

Adapter This approach to wrapping a shell around one data structure to emulate another is termed using an adapter pattern Another interesting application of this concept is to write an adapter which converts an Object Stack to a more specialized stack - hides casts -- efficiency impact

Example: public class AppleStack {

private Stack aStack;

public AppleStack() { aStack = new ArrayStack(); }

public push (Apple newApple) {aStack.push ((Object) newApple); }

public Apple pop () throws StackEmptyException { return ( (Apple) aStack.pop() ); // note dont catch exception } // others left off for room }

Example: Using a Deque as a Stack public class DequeStack implements Stack { private Deque deck;

public DequeStack() { deck = new ArrayDeque(); }

public boolean isEmpty() { return deck.isEmpty(); }

public int size() { return deck.size(); }

public void push (Object newElem) { deck.insertLast(newElem); }

public Object pop() throws StackEmptyException { if (deck.isEmpty()) { throw new StackEmptyException (Stack is empty!); } return deck.removeLast(); } } // top() not shown for space }

//////////////////////////////////////////////////////////////////////////////////////////////////////////

public interface Position { /** * Returns the element stored at this position. * * @return the stored element * @throws IllegalStateException if position no longer valid */ E getElement( ) throws IllegalStateException; }

/** An interface for positional lists. */ public interface PositionalList < E > { /** Returns the number of elements in the list. */ int size();

/** Tests whether the list is empty. */ boolean isEmpty();

/** Returns the first Position in the list (or null, if empty). */ Position < E > first();

/** Returns the last Position in the list (or null, if empty). */ Position < E > last();

/** Returns the Position immediately before Position p (or null, if p is first). */ Position < E > before(Position < E > p) throws IllegalArgumentException;

/** Returns the Position immediately after Position p (or null, if p is last). */ Position < E > after(Position < E > p) throws IllegalArgumentException; /** Inserts element e at the front of the list and returns its new Position. */ Position < E > addFirst(E e);

/** Inserts element e at the back of the list and returns its new Position. */ Position < E > addLast(E e);

/** Inserts element e immediately before Position p and returns its new Position. */ Position < E > addBefore(Position < E > p, E e) throws IllegalArgumentException;

/** Inserts element e immediately after Position p and returns its new Position. */ Position < E > addAfter(Position < E > p, E e) throws IllegalArgumentException;

/** Replaces the element stored at Position p and returns the replaced element. */ E set(Position < E > p, E e) throws IllegalArgumentException;

/** Removes the element stored at Position p and returns it (invalidating p). */ E remove(Position < E > p) throws IllegalArgumentException;

}