// CLASS LinkedStack package datastructures;

import java.util.EmptyStackException;

public class LinkedStack implements OurStack {

//We build our stack by linking Nodes //Note: Node was a private class - it could only be accessed by LinkedStack //We have now made it protected //A protected class/method/field can be accessed by: //The class which contains it //A class in the same package as the class containing it //A class which inherits from the class containing it //Note that private can only be accessed by the first of these //Without a keyword it can only be accessed by the first two of these protected class Node { E element; //Element stored in the node Node link; //Link to the next node in the stack (the node beneath this one) } private Node top; //the top node in the stack private int size; //the total number of nodes /** * Constructor - creates an empty stack */ public LinkedStack() { size = 0; top = null; } @Override /** * Removes and returns this stack's top element. * @return top element * @throws EmptyStackException if the stack is empty */ public E pop() { if (size == 0) { throw new EmptyStackException(); } E elem = top.element; top = top.link; size--; return elem; }

@Override /** * Adds the given element to the top of the stack. * @param elem - element to add to the stack */ public void push(E elem) { Node n = new Node(); n.element = elem; n.link = top; top = n; size++; }

@Override /** * Returns, but does not remove, the tope element of the stack * @return top element * @throws EmptyStackException */ public E peek() { if (size == 0) { throw new EmptyStackException(); } return top.element; }

@Override /** * Returns the number of elements in the stack * @return size of stack */ public int size() { return size; }

@Override /** * Returns true if the stack is empty * @return true if stack is empty */ public boolean isEmpty() { return top == null; }

@Override /** * Returns this stack as a string * @return string containing the stack's elements */ public String toString() { String s = ""; //This is an example of an iterator Node walker = top; while(walker != null) { s += walker.element + " "; walker = walker.link; } return s; } /** * Returns the top node (useful for equality with other implementations) * @return the top node */ protected Node getTop() { return top; } @Override /** * Returns true if the stack is equal to the given stack. * Two stacks are equal if they have equal elements in the same order. * @return true if stacks are equal */ public boolean equals(Object obj) { if (obj instanceof LinkedStack) { LinkedStack s = (LinkedStack) obj; if(size != s.size) { return false; }else { Node walker = top; Node sWalker = s.top; while(walker != null) { if(!walker.element.equals(sWalker.element)) { return false; } walker = walker.link; sWalker = sWalker.link; } return true; } }else if (obj instanceof ArrayStack) { ArrayStack s = (ArrayStack) obj; if(size != s.size()) { return false; }else { Node walker = top; Object[] sElem = s.getElements(); for(int i = 0; i s = new LinkedStack(); s.push(5); s.push(11); s.push(14); System.out.println(s.peek()); System.out.println(s.pop()); System.out.println(s.toString()); } }

// CLASS

package datastructures;

public interface OurStack{

/** * Removes the top element of the stack * @return the removed element */ public E pop(); /** * Adds a new element to the top of the stack * @param elem the element to add */ public void push(E elem); /** * Returns the top element without removing it * @return the top element */ public E peek(); /** * Returns the size of the stack * @return the size of the stack */ public int size(); /** * Returns true if the stack is empty * @return true if emtpy, false otherwise */ public boolean isEmpty(); }

In this lab, you will gain more experience working with a linked data structure by adding methods to the LinkedStack class. Note that you may need to remove the section of the equals method referring to the ArrayStack and change the OurStack in main to be a LinkedStack. Problem 1: Add the method below that prints every other element in the stack, starting with the top element. For example, if the stack contains the elements 2 4 6 8 10 12, where 2 is the top, then this method will print "2 6 10". public void printEveryOther() { Problem 2: Add the method below that adds the given element to the stack...except it is added as the second element, not the top element. For example, if the stack contains 2 4 6 8 10 12 where 2 is the top, and we want to add 7, then the stack will be 2 7 4 6 8 10 12. Throw the EmptyStackException if the stack is empty. public void addSecond(E element) { Problem 3: Add the method below that removes and returns the bottom element from the stack. For example, if the stack contains 2 4 6 8 10 12 where 2 is the top, then this method will remove the 12. Do not add a new field variable to the class. public E removeBottom() { Problem 4: Add the method below that returns an array containing the elements that are in the stack, in the same order (where the top element will be the last element in the array). The array will be an Object array and should have the same size as the stack. The method must not make any changes to the stack. For example, if the stack contains 2 4 6 8 10 12 where 2 is the top, then this method will return the array 12 10 8 642 public Object[] toArray() {