Perform the Big O analysis for each method in the LinkedDropOutStack<T> class. T
ID: 3834360 • Letter: P
Question
Perform the Big O analysis for each method in the LinkedDropOutStack<T> class.
The code is below:
/**
* Represents a linked implementation of a stack.
*
* @author Java Foundations
* @version 4.0
*/
public class DropOutStack<T> implements StackADT<T>
{
private int count;
private LinearNode<T> top;
private final int n=5;
private LinearNode<T> prev;
private LinearNode<T> curr;
/**
* Creates an empty stack.
*/
public DropOutStack()
{
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);
if(count<n){
temp.setNext(top);
top=temp;
count++;
}
else if(count>=n&&n!=1)
{
prev=top;
curr=top.getNext().getNext();
while(curr!=null){
prev=prev.getNext();
curr=curr.getNext();
}
prev.setNext(null);
count--;
push(element);
}
else {
top.setElement(element);
}
}
/**
* 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()
{
if (isEmpty())
return null;
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()
{
if(isEmpty())
return null;
else
return top.getElement();
}
/**
* Returns true if this stack is empty and false otherwise.
* @return true if stack is empty
*/
public boolean isEmpty()
{
return (count == 0);
}
/**
* Returns the number of elements in this stack.
* @return number of elements in the stack
*/
public int size()
{
return count;
/**
*keeping the track of the number
*of elements in the stack.
*/
}
/**
* Returns a string representation of this stack.
* @return string representation of the stack
*/
public String toString()
{
String result = ""; // initialize it to empty string
LinearNode<T> t = top; // start from top
while (t != null) // iterate until it reaches the end of the list (end of list is when current == null)
{
result = t.getElement()+" "+result; // append it's value to result string
t = t.getNext(); // make current points to next element
}
return result; // return result string
}
}
Explanation / Answer
Hi, Please find my answer.
public void push(T element):
In this method, if number of nodes in stack is less than maximum size, then we are adding at front.
But if stack is full then we drop out bottom element. To do this we have to traverse entire list till end.
It takes O(n) time
public T pop():
We are removing front element from linked list:
It takes O(1) time
public T peek():
We are returning the value of front Node from linked list:
It takes O(1) time
public boolean isEmpty():
We are returning true/false base on count value
It takes O(1) time
public int size():
returning count value
It takes O(1) time
public String toString():
We are traversing whole node to get info of all nodes in linked list
It takes O(n) time
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.