Can you please give me this answer in java. Problem #1 Complete the implementati
ID: 3833368 • Letter: C
Question
Can you please give me this answer in java.
Problem #1
Complete the implementation of the LinkedStack<T> class as written below: Complete implementations of peek, size, isempty and toString. Note that the text book implementation uses a count variable to keep track of the number of elements in the stack.
Verify the functionality of your LinkedStack<T> class with a test application (driver).
The code is:
//StackADT.java
package jsjf;
/**
* Defines the interface to a stack collection.
*
* @author Java Foundations
* @version 4.0
*/
public interface StackADT<T>
{
/**
* Adds the specified element to the top of this stack.
* @param element element to be pushed onto the stack
*/
public void push(T element);
/**
* Removes and returns the top element from this stack.
* @return the element removed from the stack
*/
public T pop();
/**
* Returns without removing the top element of this stack.
* @return the element on top of the stack
*/
public T peek();
/**
* Returns true if this stack contains no elements.
* @return true if the stack is empty
*/
public boolean isEmpty();
/**
* Returns the number of elements in this stack.
* @return the number of elements in the stack
*/
public int size();
/**
* Returns a string representation of this stack.
* @return a string representation of the stack
*/
public String toString();
}
//LinkedStack.java
package jsjf;
import jsjf.exceptions.*;
/**
* Represents a linked implementation of a stack.
*
* @author Java Foundations
* @version 4.0
*/
public class LinkedStack<T> implements StackADT<T>
{
private int count;
private LinearNode<T> top;
/**
* Creates an empty stack.
*/
public LinkedStack()
{
count = 0;
top = null;
}
/**
* Adds the specified element to the top of this stack.
* @param element element to be pushed on stack
*/
public void push(T element)
{
LinearNode<T> temp = new LinearNode<T>(element);
temp.setNext(top);
top = temp;
count++;
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
* @return element from top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T pop() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
T result = top.getElement();
top = top.getNext();
count--;
return result;
}
/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
* @return element on top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T peek() throws EmptyCollectionException
{
// To be completed as a Programming Project
return null; // temp
}
/**
* Returns true if this stack is empty and false otherwise.
* @return true if stack is empty
*/
public boolean isEmpty()
{
// To be completed as a Programming Project
return true; // temp
}
/**
* Returns the number of elements in this stack.
* @return number of elements in the stack
*/
public int size()
{
// To be completed as a Programming Project
return 0; // temp
}
/**
* Returns a string representation of this stack.
* @return string representation of the stack
*/
public String toString()
{
// To be completed as a Programming Project
return ""; // temp
}
}
//LinearNode.java
package jsjf;
/**
* Represents a node in a linked list.
*
* @author Java Foundations
* @version 4.0
*/
public class LinearNode<T>
{
private LinearNode<T> next;
private T element;
/**
* Creates an empty node.
*/
public LinearNode()
{
next = null;
element = null;
}
/**
* Creates a node storing the specified element.
* @param elem element to be stored
*/
public LinearNode(T elem)
{
next = null;
element = elem;
}
/**
* Returns the node that follows this one.
* @return reference to next node
*/
public LinearNode<T> getNext()
{
return next;
}
/**
* Sets the node that follows this one.
* @param node node to follow this one
*/
public void setNext(LinearNode<T> node)
{
next = node;
}
/**
* Returns the element stored in this node.
* @return element stored at the node
*/
public T getElement()
{
return element;
}
/**
* Sets the element stored in this node.
* @param elem element to be stored at this node
*/
public void setElement(T elem)
{
element = elem;
}
}
//EmptyCollectionException.java
package jsjf.exceptions;
/**
* Represents the situation in which a collection is empty.
*
* @author Java Foundations
* @version 4.0
*/
public class EmptyCollectionException extends RuntimeException
{
/**
* Sets up this exception with an appropriate message.
* @param collection the name of the collection
*/
public EmptyCollectionException(String collection)
{
super("The " + collection + " is empty.");
}
}
Problem #2
Perform the Big O analysis for each method in the LinkedStack<T> class.
thanks
Explanation / Answer
//LinkedStack.java
package jsjf;
import jsjf.exceptions.*;
/**
* Represents a linked implementation of a stack.
*
* @author Java Foundations
* @version 4.0
*/
public class LinkedStack<T> implements StackADT<T>
{
private int count;
private LinearNode<T> top;
/**
* Creates an empty stack.
*/
public LinkedStack()
{
count = 0;
top = null;
}
/**
* Adds the specified element to the top of this stack.
* @param element element to be pushed on stack
*/
public void push(T element)
{
LinearNode<T> temp = new LinearNode<T>(element);
temp.setNext(top);
top = temp;
count++;
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
* @return element from top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T pop() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
T result = top.getElement();
top = top.getNext();
count--;
return result;
}
/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
* @return element on top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T peek() throws EmptyCollectionException
{
// To be completed as a Programming Project
if(isEmpty())
{
throw new EmptyCollectionException("stack");
}
return top.getElement();
}
/**
* Returns true if this stack is empty and false otherwise.
* @return true if stack is empty
*/
public boolean isEmpty()
{
// To be completed as a Programming Project
return count==0;
}
/**
* Returns the number of elements in this stack.
* @return number of elements in the stack
*/
public int size()
{
// To be completed as a Programming Project
return count; // temp
}
/**
* Returns a string representation of this stack.
* @return string representation of the stack
*/
public String toString()
{
// To be completed as a Programming Project
LinearNode<T> runner=top;
String s="";
for(int i=0;i<count;i++)
{
s=s+runner.toString()+" ";
runner=runner.getNext();
}
return s;
}
}
-----------------------
push,pop,size,peek all takes constant amount of time irrespective of the number of elements in stack hence
they have theta(1) complexity.
totring() method has a method which iterates throgh the whole stack in order to form a concatenated string of all thhe elments in the stack.
since it itrater throgh through all elements of stack it comlexity is theta(n)