In Java with everything well explained / with comments 1. (a) Implement, using J

Question

In Java with everything well explained / with comments

1. (a) Implement, using Java or C++, a queue with a time complexity of O(1) for access to the maximum element. (b) Test your implementation and exhibit the test results

Explanation / Answer

public class MyQueue implements Queue,DeQueue{ protected int front = 0; protected int rear =-1; protected E[] elements =null; private static final int DEFAULT_INTIAL_CAPACITY =100; private int size =0; public MyQueue(){ this(DEFAULT_INTIAL_CAPACITY); } @SuppressWarnings("unchecked") public MyQueue(int intialCapacity){ if(intialCapacity < 0){ throw new IllegalArgumentException("intial capacity can't be null"); } elements =(E[]) new Object[intialCapacity]; } @Override public boolean addR(E e) { if(! isFull()) { elements[++rear] = e; size++; return true; } return false; } @Override public E removeL() { E element =null; if(!isEmpty()){ element=elements[front]; // Nullify the reference elements[front] =null; ++front; --size; } return element; } @Override public E element() { E element =null; if(!isEmpty()){ element=elements[front]; } return element; } @Override public E elementR() { E element =null; if(!isEmpty()){ element=elements[rear]; } return element; } public boolean isFull() { return rear == elements.length; } public boolean isEmpty() { return size == 0; } Override public String toString() { return "MyQueue [front=" + front + ", rear=" + rear + ", elements=" + Arrays.toString(elements) + ", size=" + size + "]"; } @Override public void trim() { @SuppressWarnings("unchecked") E[] dest =(E[]) new Object[size]; System.arraycopy(elements, front, dest, 0, size); elements = dest; front =0; rear=size-1; } @Override public boolean addL(E element) { if(front != 0) { elements[--front] = element; size++; return true; } return false; } @Override public E removeR() { E element =null; if(size > 0) { element=elements[rear]; // Nullify the reference elements[rear] =null; --rear; --size; } return element; } } package com.java.util.collection.advance.datastructure.queue; public class MinAndMaxFinderQueue extends MyQueue implements FindMinMaxQueue { private Queue maxValuesQueue =null; private Queue minValuesQueue =null; public MinAndMaxFinderQueue (int intialCapacity){ super(intialCapacity); maxValuesQueue =new MyQueue(intialCapacity); minValuesQueue =new MyQueue(intialCapacity); } @Override public boolean addR(Integer e) { if(super.addR(e)){ if(max() == null || max() = e){ minValuesQueue.addR(e); } return true; } return false; } @Override public Integer removeL() { Integer element =super.removeL(); if(element !=null){ if(maxValuesQueue.element() == element){ maxValuesQueue.removeL(); } if(minValuesQueue.element() == element){ minValuesQueue.removeL(); } } //Need to re-generate MIN and MAX queue when the main queue is not empty and min/max queue is empty regenerateMin(); regenerateMax(); return element; } private void regenerateMin(){ Integer current =null; if(!super.isEmpty() && min() ==null){ for(int front = super.front; front= current){ minValuesQueue.addR(current); } } } } private void regenerateMax(){ Integer current =null; if(!super.isEmpty() && max() ==null){ for(int front = super.front; front

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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