I need help with a Deque in Object-Oriented Programming. I was given comments ba

Question

I need help with a Deque in Object-Oriented Programming. I was given comments back from my teacher but I can't figure out how to fix what he wants me to.

Here is my code:

class Deque {
private Object[] arrayDeque;
private int dataSize;
private int front;
private int back;
private static final int ALLOC=5;

public Deque() {
arrayDeque=new Object[ALLOC];
front=3;
back=2;
dataSize=0;
}

public void insertOnFront (Object s) {
int insertFront=front;
insert();
arrayDeque[front]=s;
--front;
++dataSize;
}

public void insertOnBack (Object s) {
int insertBack=back;
insert();
arrayDeque[back]=s;
++back;
++dataSize;
}

public void insert () {
int insertFront=front;
int insertBack=back;
if (dataSize==arrayDeque.length) {
Object[] temp=new Object[dataSize*2];
for (int i=0; i<=dataSize-1; ++i) {
if (insertFront==arrayDeque.length) {
insertFront=0;
temp[i]=arrayDeque[insertFront];
++insertFront;
}
else if (insertBack==arrayDeque.length) {
insertBack=0;
temp[i]=arrayDeque[insertBack];
++insertBack;
}
}
arrayDeque=temp;
front=arrayDeque.length-1;
back=arrayDeque.length/2;
}
if (front<0) {
front=arrayDeque.length-1;
}
else if (back>=arrayDeque.length) {
back=0;
}
}

public Object deleteFromFront() {
if (dataSize==0) {
return null;
}
front=front+1;
if (front==arrayDeque.length) {
front=0;
}
--dataSize;
Object deletedItem=arrayDeque[front];
arrayDeque[front]="null";
  
return deletedItem;
}

public Object deleteFromBack() {
if (dataSize==0) {
return null;
}
back=back-1;
if (back==-1) {
back=arrayDeque.length-1;
}
--dataSize;
  
Object deletedItem=arrayDeque[back];
arrayDeque[back]="null";
  
return deletedItem;
}

public boolean isEmpty() {
return (dataSize==0);
}

public String toString() {
String s=" ";
int i;
int ix=front;
  
for (i=0; i<dataSize; ++i) {
if (ix==arrayDeque.length || ix<0)
ix=0;
if (arrayDeque[ix]==null) || arrayDeque[ix].equals(null)) {

}
else {
s=s+arrayDeque[ix] + ",";
}
++ix;
}
return s;
}

public String toStore() {
String s="";
for (int i=0; i<arrayDeque.length-1; ++i) {
s=s+arrayDeque[i] + ",";
}
return s;
}
}

teachers comments:

1. To initialize the front and back indexes, consider what the indexes should be for a Deque with one element, then consider what they are after that element is deleted and the Deque is empty. The result should be the appropriate indexes for the initial empty Deque.
-For example, if front and back refer to the next empty slot to insert an item, with front higher than back, then front must start at a number one more than back.

2. In the expansion code, the index of the source array starts at the wrong place.
   -The 'front' refers to the 'hole', or the slot to insert the next item on the front. Therefore, the item on the front is at the next index (front + 1, with wrap-around).
   -The same happens in 'toString'.

3. In 'insertOnFront', the wrap-around is performed before using the index, and not after the increment. That means that 'front' could be -1 after the function is done. Therefore, other functions that use 'front' (like 'toString' and the code to expand the array) have to be prepared for a potentially invalid setting.
-A simpler, less error-prone way is to make sure that the 'front' is valid at the end of each function. Immediately after incrementing or decrementing, perform the wrap-around and reset to a valid index.
   -The same is true for 'insertOnBack' and the 'back' index.
   -In the 'deletion' methods, if the Deque is empty, return null (the undefined address) and not "null" (a String).

4. When stepping through the elements in the array, there is should be no need to check for a null entry. It should not be possible unless there is an error in the logic of the code. If your program is encountering a null entry, then fix the program so that it does not.
   -In 'toStore', it will be helpful if you also include the current settings for front and back.

Explanation / Answer

// we could use somethink like below to handle the cases your teacher have asked.
// Take a node class and maintain front, rear as null and size as 0 at time of deque initialization

import java.util.*;

/* Class Node */
class Node
{
protected int data;
protected Node link;

/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}

/* Class Dequeue */
class Dequeue
{
private Node front, rear;
private int size;

/* Constructor */
public Dequeue()
{
front = null;
rear = null;
size = 0;
}
/* Function to check if queue is empty */
public boolean isEmpty()
{
return front == null;
}
/* Function to get the size of the queue */
public int getSize()
{
return size;
}
/* Clear dequeue */
public void clear()
{
front = null;
rear = null;
size = 0;
}
/* Function to insert an element at begining */
public void insertAtFront(int val)
{
Node nptr = new Node(val, null);
size++ ;
if (front == null)
{
front = nptr;
rear = front;
}
else
{
nptr.setLink(front);
front = nptr;
}
}
/* Function to insert an element at end */
public void insertAtRear(int val)
{
Node nptr = new Node(val,null);
size++ ;
if (rear == null)
{
rear = nptr;
front = rear;
}
else
{
rear.setLink(nptr);
rear = nptr;
}
}
/* Function to remove front element from the queue */
public int removeAtFront()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
Node ptr = front;
front = ptr.getLink();

if (front == null)
rear = null;
size-- ;

return ptr.getData();
}
/* Function to remove rear element from the queue */
public int removeAtRear()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
int ele = rear.getData();
Node s = front;
Node t = front;
while (s != rear)
{
t = s;
s = s.getLink();
}
rear = t;
rear.setLink(null);
size --;

return ele;
}
/* Function to check the front element of the queue */
public int peekAtFront()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return front.getData();
}
/* Function to check the front element of the queue */
public int peekAtRear()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return rear.getData();
}
/* Function to display the status of the queue */
public void display()
{
System.out.print(" Dequeue = ");
if (size == 0)
{
System.out.print("Empty ");
return ;
}
Node ptr = front;
while (ptr != rear.getLink() )
{
System.out.print(ptr.getData()+" ");
ptr = ptr.getLink();
}
System.out.println();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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