Question

Implement the SimpleQueue interface with the MyQueue class. You can use either a linked list or a dynamic array to implement the data structure.

A queue is a specialised form of list in which you can only get and remove the first element in the queue.

The class should be able to work with the following code:

SimpleQueue queue = new MyQueue();

NB: You cannot import anything from the standard library for this task. The data structure must be of your own creation, not a modified form of a pre-existing class.

-----------------------------------------------------------

public interface SimpleQueue {
  
   /**
   * Returns true if the queue is empty, else false.
   *
   * @return   whether the queue is empty
   */
   public boolean isEmpty();

   /**
   * Removes all elements from the queue.
   */
   public void clear();
  
   /**
   * Returns the first element, null if empty.
   *
   * @return   the first element
   */
   public T peek();
  
   /**
   * Returns and removes the first element, null if empty.
   *
   * @return   the first element
   */
   public T dequeue();
  
   /**
   * Appends the element to the end of the queue. Does nothing if the element is null.
   *
   * @param elem   the element to be added
   */
   public void enqueue(T elem);
  
   /**
   * Returns the size of the queue
   *
   * @return   the size of the queue
   */
   public int size();
  
   /**
   * Returns true if the queue contains the given element.
   *
   * @return   whether the element is present
   */
   public boolean contains(T elem);
}

Answer 1

//SimpleQueue.java

public class MyQueue<T> implements SimpleQueue<T> {
   Object arr[];
   int size, count;

   public MyQueue() {
       arr = new Object[1];
       size = 1;
       count = 0;
   }

   public void double_size() {
       Object temp[] = new Object[count];
       for (int i = 0; i < count; i++) {
           temp[i] = arr[i];
       }
       size = size * 2;
       for (int i = 0; i < count; i++) {
           arr[i] = temp[i];
       }
   }

   @Override
   public boolean isEmpty() {
       if (count == 0)
           return true;
       return false;
   }

   @Override
   public void clear() {
       count = 0;
       size = 1;
       arr = new Object[1];
   }

   @Override
   public T peek() {
       if (count == 0)
           return null;
       return (T) arr[count - 1];
   }

   @Override
   public T dequeue() {
       if (count == 0)
           return null;
       else {
           count--;
           T temp = (T) arr[count];
           arr[count] = null;
           return temp;
       }
   }

   @Override
   public void enqueue(T elem) {
       if (count == size)
           double_size();
       arr[count] = elem;
       count++;
   }

   @Override
   public int size() {
       return count;
   }

   @Override
   public boolean contains(T elem) {
       for (int i = 0; i < count; i++) {
           if (arr[i].equals(elem))
               return true;
       }
       return false;
   }

}

============================================================

//MyQueue.java

public class MyQueue<T> implements SimpleQueue<T> {
   Object arr[];
   int size, count;

   public MyQueue() {
       arr = new Object[1];
       size = 1;
       count = 0;
   }

   public void double_size() {
       Object temp[] = new Object[count];
       for (int i = 0; i < count; i++) {
           temp[i] = arr[i];
       }
       size = size * 2;
       for (int i = 0; i < count; i++) {
           arr[i] = temp[i];
       }
   }

   @Override
   public boolean isEmpty() {
       if (count == 0)
           return true;
       return false;
   }

   @Override
   public void clear() {
       count = 0;
       size = 1;
       arr = new Object[1];
   }

   @Override
   public T peek() {
       if (count == 0)
           return null;
       return (T) arr[count - 1];
   }

   @Override
   public T dequeue() {
       if (count == 0)
           return null;
       else {
           count--;
           T temp = (T) arr[count];
           arr[count] = null;
           return temp;
       }
   }

   @Override
   public void enqueue(T elem) {
       if (count == size)
           double_size();
       arr[count] = elem;
       count++;
   }

   @Override
   public int size() {
       return count;
   }

   @Override
   public boolean contains(T elem) {
       for (int i = 0; i < count; i++) {
           if (arr[i].equals(elem))
               return true;
       }
       return false;
   }

}

===================================

// Code Snippet