Perform the Big O analysis for each method in the LinkedQueue class. The code is

Question

Perform the Big O analysis for each method in the LinkedQueue class.

The code is written below:

package jsjf;

import jsjf.exceptions.*;

/**
* LinkedQueue represents a linked implementation of a queue.
*
* @author Java Foundations
* @version 4.0
*/
public class LinkedQueue<T> implements QueueADT<T>
{
private int count;
private LinearNode<T> head, tail;

/**
* Creates an empty queue.
*/
public LinkedQueue()
{
count = 0;
head = tail = null;
}

/**
* Adds the specified element to the tail of this queue.
* @param element the element to be added to the tail of the queue
*/
public void enqueue(T element)
{
LinearNode<T> node = new LinearNode<T>(element);

if (isEmpty())
   head = node;
else
   tail.setNext(node);

tail = node;
count++;
}

/**
* Removes the element at the head of this queue and returns a
* reference to it.
* @return the element at the head of this queue
* @throws EmptyCollectionException if the queue is empty
*/
public T dequeue() throws EmptyCollectionException
{
if (isEmpty())
   throw new EmptyCollectionException("queue");

T result = head.getElement();
head = head.getNext();
count--;

if (isEmpty())
   tail = null;

return result;
}

/**
* Returns a reference to the element at the head of this queue.
* The element is not removed from the queue.
* @return a reference to the first element in this queue
* @throws EmptyCollectionsException if the queue is empty
*/
public T first() throws EmptyCollectionException
{
// To be completed as a Programming Project
if(isEmpty())
    throw new EmptyCollectionException("queue");
T result=head.getElement();
return result; // temp
}

/**
* Returns true if this queue is empty and false otherwise.
* @return true if this queue is empty
*/
public boolean isEmpty()
{
// To be completed as a Programming Project

return count==0; // temp
}

/**
* Returns the number of elements currently in this queue.
* @return the number of elements in the queue
*/
public int size()
{
// To be completed as a Programming Project

return count; // temp
}

/**
* Returns a string representation of this queue.
* @return the string representation of the queue
*/
public String toString()
{
// To be completed as a Programming Project
   String q="";
   LinearNode<T> q1=head;
   while(q1!=null){
   q=q+(q1.getElement()).toString()+"";
   q1=q1.getNext();
   }

return q; // temp
}
}

Thanks

Explanation / Answer

Method LinkedQueue() takes O(1) to create an empty queue.

void enqueue() which adds element at the last of the queue takes O(1)

Method T deque() which removes the element at the head of the queue and returns a reference to it, also takes O(1)

Method T first() which works in similar fashion as that of method deque() but it doesn't remove first element, takes O(1)

int size() will take O(n) to give the number of elements in the queue.

method boolean isEmpty() will utilize the method int size() in order to decide whether queue is empty or not, so indirectly this method also take O(n) time.

method String toString() also take O(n) to return a string representation of the queue.

Hope it helps, do give your valuable response.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.