Java LinkedList In-class Exercise It is often the case that new data structures

Question

Java LinkedList In-class Exercise

It is often the case that new data structures are written using other existing data structures as an underlying model. In this practice exercise we will be creating a Queue class using Java’s LinkedList as a basis for our new class.

A Queue data structure behaves similarly to a set of people waiting in line. There are restrictions on entering and exiting the line:

1. You may only enter the line at the back, referred to as an “enqueue” operation.

2. You may only exit the line at the front, referred to as a “dequeue” operation.

3. You may also look at the person in the front of the line, referred to as a “peek” operation.

4. You cannot be helped if you are in the middle of the line.

Because of these restrictions, a Queue data type is referred to as a FIFO structure (first-in-firstout).

Note: because we only allow access to elements at the front/back of a Queue, this removes the index-based access of structures such as Arrays and ArrayLists

Write a new Queue class using a LinkedList as the underlying storage structure (in other words, a private instance field). You can simulate the behavior described above by adding items to the front of your LinkedList and removing items from the back.

Hint: I would suggest looking for helpful methods in the Java API for the LinkedList class. In particular the following methods: addFirst, addLast, removeFirst, removeLast

Use the following class diagram as a basis for your class:

Queue<T>

- data : LinkedList<T>

+ enqueue(newElement : T) : void

+ dequeue() : T

+ peek() : T

+ isEmpty() : boolean

+ size() : int

Note: your Queue class should throw an appropriate exception when dequeue() is called on an empty Queue.

Write a test class to show that your Queue class is working correctly.

Challenge: create a new class called BoundedQueue that enforces a maximum number of elements in your queue.

1. Use the code from your Queue class as a starting point in your new BoundedQueue class

2. Include only a parameterized constructor that takes a positive integer that specifies the maximum number of elements in your bounded queue

3. Throw an appropriate exception if you queue size exceeds the bounds given

Explanation / Answer

package queue;

import java.util.LinkedList;

public class Queue<T> {
   protected LinkedList<T> data;
  
   public Queue() {
       data = new LinkedList<T>();
   }
  
   public void enqueue(T newElement) {
       data.addLast(newElement);
   }
  
   public T dequeue() throws Exception{
       if(isEmpty())
           throw new Exception("Queue is Empty");
      
       return data.removeFirst();
   }
  
   public T peek() throws Exception {
       if(isEmpty())
           throw new Exception("Queue is Empty");
      
       return data.get(0);
   }
  
   public boolean isEmpty() {
       return size() == 0;
   }
  
   public int size() {
       return data.size();
   }
}

package queue;

public class BoundedQueue<T> extends Queue<T> {
   private int maxElements;
  
   public BoundedQueue(int maxElements) {
       this.maxElements = maxElements;
   }
  
   @Override
   public void enqueue(T newElement) {
       if(isFull())
           try {
               throw new Exception("Queue is Full");
           } catch (Exception e) {
               e.printStackTrace();
           }
      
       data.addLast(newElement);
   };
  
   public boolean isFull() {
       return size() >= maxElements;
   }
}

package queue;

public class TestQueue {
   public static void main(String[] args) {
       Queue<String> queue = new Queue<String>();
      
       queue.enqueue("First");
       queue.enqueue("Second");
       queue.enqueue("Third");
      
       int size = queue.size();
       System.out.println("Queue has size of " + size);
       for(int i = 0; i <= size; i++) {
           try {
               System.out.println("Dequeue : " + queue.dequeue());
           } catch (Exception e) {
               e.printStackTrace();
           }
       }
      
       BoundedQueue<String> boundedQueue = new BoundedQueue<>(3);
      
       boundedQueue.enqueue("First");
       boundedQueue.enqueue("Second");
       boundedQueue.enqueue("Third");
       boundedQueue.enqueue("Fourth");      
   }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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