In Java: Write the bodies of the methods assuming that the front of the queue is

Question

In Java: Write the bodies of the methods assuming that the front of the queue is stored in
position 0. What is the worst-case efficiency category for each of the methods, using
storage into the array as the representative operation?

public class StringQueue
{
// construct an empty queue
public StringQueue(){}

// place the given item on the rear of the queue
public void add( String s ){}

// return a reference to the front item
public String peek(){}

// remove the front item from the queue
public void remove(){}

// return the number of items in the stack
public int size(){}
}

Explanation / Answer

public class StringQueue
{
   Queue stringQueue;
   // construct an empty queue
   public StringQueue(){
       stringQueue = new LinkedList();
   }

   // place the given item on the rear of the queue
   public void add( String s ){
       stringQueue.add(s);
   }

   // return a reference to the front item
   public String peek(){
       return ( String ) stringQueue.peek();
   }

   // remove the front item from the queue
   public void remove(){
       stringQueue.remove();
   }

   // return the number of items in the stack
   public int size(){
       return stringQueue.size();
    }
}

If we use array as a representation for this program then worst case complexity will be as follows:

add Method- O(n) where n is current size of array

peek method- O(1) since we have to return element at top

delete method- O(1) since we have to delete element at top

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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