Answer in Java, thank you.

Update: All Stack Interface is provided below

StackInterface.java:

package stacks220; public interface StackInterface220 { public void push(T anItem); public T pop(); public T peek(); public boolean isEmpty(); 

StackArray.java

package stacks220;

import java.util.*;

public class StackArray220 implements StackInterface220 {

private T[] myStack; // array of stack entries private int topIndex; // index of top entry private static final int INITIAL_CAPACITY = 10; // Initial capacity of the stack private boolean integrityOK = false;

public StackArray220 () {

this (INITIAL_CAPACITY);

} // end default constructor

public StackArray220(int initialCapacity) {

// the cast is safe because the new array contains null entries T[] tempStack = (T[])new Object[initialCapacity]; myStack = tempStack; topIndex = 0; // for the empty initial stack integrityOK = true; } // end constructor with initial capacity

// Throws an exception if this object is not initialized. private void checkIntegrity() {

if (!integrityOK) throw new SecurityException ("ArrayStack object is corrupt."); } // end checkIntegrity

public void push(T newItem) {

checkIntegrity(); topIndex++; //increment topIndex counter

if (topIndex >= myStack.length) // if array is full, doubleCapacity(); // this doubles array and lays out elements

myStack[topIndex] = newItem;

} // end push

public T peek() {

checkIntegrity(); T topItem = null; if(!this.isEmpty()) // check if array is empty and return result topItem = myStack[topIndex]; return topItem;

} // end peek

public T pop() {

checkIntegrity(); T topItem = null;

if( !this.isEmpty() ) { topItem = myStack[topIndex]; myStack[topIndex] = null; // kill top item topIndex--;// reset top of stack counter } return topItem; } // end pop

public boolean isEmpty() { return topIndex

/** * This is a private method, and can be called by any instance method of the class that determines the need to increment bag capacity */ private void doubleCapacity() { int newBagCapacity = INITIAL_CAPACITY * 2; myStack = Arrays.copyOf(myStack, newBagCapacity); } } // end class StackArray220

LinkedStack.java

package stacks220; import java.lang.StringBuilder; import java.util.*; public class LinkedStack220 implements StackInterface220 { Node topNode; // pointer to top node of stack public LinkedStack220() { topNode = null; } // end default constructor public LinkedStack220(T anEntry) { topNode = new Node(anEntry); } // end 1-arg constructor public void push(T dataElement) { Node n = new Node(dataElement, topNode); // create new node topNode = n; } // end push public T pop() { T top = null; try { top = peek(); if(!isEmpty()){ topNode = topNode.next; } } catch(EmptyStackException ese) { } return top; } // end pop public T peek() { String top = null; if(!isEmpty()) return topNode.data; else throw new EmptyStackException(); } // end peek public boolean isEmpty() { return topNode == null; } // end isEmpty public void print() { StringBuilder sBuilder = new StringBuilder(); Node currentNode = topNode; boolean completed = false; while(!completed && currentNode != null) { sBuilder.append(currentNode.data + ", "); currentNode = currentNode.next; } String start = "[ "; int len = sBuilder.length(); System.out.println(start + sBuilder.replace(len, len, " ]")); } //inner class Node private class Node { private T data; private Node next; public Node() { } // default constructor private Node(T data){ this(data, null); } private Node(T dataEntry, Node n){ this.data = dataEntry; this.next = n; // this node's next will be the argument node } } } 

VectorStack.java

package stacks220;

import java.util.*;

public class VectorStack220 implements StackInterface220 { private Vector stack; // last element is top of stack private int numEntries; private boolean integrityOK = false; static final int DEFAULT_CAPACITY = 10;

public VectorStack220() { this(DEFAULT_CAPACITY); // vector doubles as needed } // end default constructor

public VectorStack220(int size) { stack = new Vector (size); integrityOK = true; } // end constructor

private void checkIntegrity() {

if (!integrityOK) throw new SecurityException ("ArrayStack object is corrupt."); } // end checkIntegrity public void push(T dataElement) { checkIntegrity(); stack.add(dataElement); } // end push

public T pop() { checkIntegrity(); T top = null; if(!isEmpty()){ top = stack.lastElement(); stack.remove((stack.size() - 1)); } return (T)top; } // end push

public T peek() { T top = null; if(!isEmpty()) top = stack.lastElement(); return (T)top; } // end push public boolean isEmpty() { return stack.isEmpty(); } // end push

public void print() { String resultStr = "[ "; ArrayList strArray = new ArrayList(); for(T item: stack) { strArray.add(item); } System.out.println(strArray); } }

**6-1, 6-2, 6-3 for Reference:

6-3:

VectorStack.Java

package stacks220; import java.util.*; public class VectorStack220 implements StackInterface220 { private Vector stack; // last element is top of stack private int numEntries; private boolean integrityOK = false; static final int DEFAULT_CAPACITY = 10; public VectorStack220() { this(DEFAULT_CAPACITY); // vector doubles as needed } // end default constructor public VectorStack220(int size) { stack = new Vector (size); integrityOK = true; } // end constructor private void checkIntegrity() { if (!integrityOK) throw new SecurityException ("ArrayStack object is corrupt."); } // end checkIntegrity public void push(T dataElement) { checkIntegrity(); stack.add(dataElement); } // end push public T pop() { checkIntegrity(); T top = null; if(!isEmpty()){ top = stack.lastElement(); stack.remove((stack.size() - 1)); } return (T)top; } // end push public T peek() { T top = null; if(!isEmpty()) top = stack.lastElement(); return (T)top; } // end push public boolean isEmpty() { return stack.isEmpty(); } // end push public void print() { String resultStr = "[ "; ArrayList strArray = new ArrayList(); for(T item: stack) { strArray.add(item); } System.out.println(strArray); } }

Figure 6-2 (a) A new node that references the node at the top of the stack newNode FOT topNode (b) The new node is now at the top of the stack an Duc topNode Adding a new node to the top of a linked stack Figure 6-2 Full Alternative Text public void push(T newEntry) Node newNode = new Node (newEntry, topNode); topNode = newNode; } // end push Note that you can replace the two statements in the body of this method with topNode = new Node (newEntry, topNode); This operation is independent of the other entries in the stack. Its performance is thus O(1). 4. 6.4 Retrieving the top. We get the top entry in the stack by accessing the data portion of the first node in the chain. Thus, peek, like push, is an O(1) operation. Note that if the stack is empty, peek throws an exception public T peek() if (isEmpty()) throw new EmptyStackException(); else return topNode.getData(); } // end peek (a) Before pop Chain topNode Top entry of stack 0 0 0 0 - Stack (b) After pop topNode Returned to client top 000 Stack The stack before and after pop deletes the first node in the chain Figure 6-3 Full Alternative Text public T pop() T top = peek(); // Might throw EmptyStackexception // Assertion: topNode != null topNode = topNode.getNextNode (); return top; 1 // end pop This operation also is O(1). Figure 6-2 (a) A new node that references the node at the top of the stack newNode FOT topNode (b) The new node is now at the top of the stack an Duc topNode Adding a new node to the top of a linked stack Figure 6-2 Full Alternative Text public void push(T newEntry) Node newNode = new Node (newEntry, topNode); topNode = newNode; } // end push Note that you can replace the two statements in the body of this method with topNode = new Node (newEntry, topNode); This operation is independent of the other entries in the stack. Its performance is thus O(1). 4. 6.4 Retrieving the top. We get the top entry in the stack by accessing the data portion of the first node in the chain. Thus, peek, like push, is an O(1) operation. Note that if the stack is empty, peek throws an exception public T peek() if (isEmpty()) throw new EmptyStackException(); else return topNode.getData(); } // end peek (a) Before pop Chain topNode Top entry of stack 0 0 0 0 - Stack (b) After pop topNode Returned to client top 000 Stack The stack before and after pop deletes the first node in the chain Figure 6-3 Full Alternative Text public T pop() T top = peek(); // Might throw EmptyStackexception // Assertion: topNode != null topNode = topNode.getNextNode (); return top; 1 // end pop This operation also is O(1)