Need Help for the Java Program : A deque (pronounced like deck) is a double-ende

Question

Need Help for the Java Program :

A deque (pronounced like deck) is a double-ended queue. Deques are like ordinary queues, except that objects can be inserted and deleted both at the front and the rear. Unlike the queues described in the lectures, they work without special cases. In this laboratory assignment, you will write a Java class called Deque that implements a deque.

1). Theory.

A deque can be implemented easily using a circular, doubly-linked list with a head node. For example, a deque containing the objects A, B, C, D, and E might use a list that looks like the following diagram. (To save space, the diagram does not show arrows pointing to those objects.)

The variable head points to the head node. The expression head.right points to the node at the front of the deque, which in turn points to the object A. The expression head.left points to the node at the rear of the deque, which in turn points to the object E.

2). Implementation.

You must write a class called Deque that implements a deque, using a doubly-linked circular list with a head node. Instances of Deque must be able to hold objects whose type is given by a class parameter Base. As a result, your class Deque must look like this, with your code in place of the three dots. To simplify grading, your code must use the same names for things that are used here.

class Deque

{

.

.

.

}

Your class Deque must have a private nested class called Node. The class Node implements the nodes of the doubly-linked list. It must have a private pointer slot called object that points to the object at the Node. It must have private pointer slots called left and right that point to the Nodes at the left and right of the Node, respectively.

It must have a constructor that initializes the object, left, and right slots of the Node. Your class Deque must also have a private variable head that points to the head node of the circular doubly-linked list. Also, your class must have the following methods.

• public Deque()

Constructor. Make a new, empty Deque. The variable head must be set to a new head node here.

• public void enqueueFront(Base object)

Add a new Node at the front of the Deque. The object slot of the new Node must point to the parameter object.

• public void enqueueRear(Base object)

Add a new Node at the rear of the Deque. The object slot of the new Node must point to the parameter object.

• public Base dequeueFront()

If the Deque is empty, then throw an IllegalStateException. Otherwise, get the Base object from the Node at the front of the Deque. Delete the Node at the front of the Deque, and return the Base object.

• public Base dequeueRear()

If the Deque is empty, then throw an IllegalStateException. Otherwise, get the Base object from the the Node at the rear of the Deque. Delete the Node at the rear of the Deque, and return the Base object.

• public boolean isEmpty()

Return true if the Deque is empty. Return false otherwise. The file tests.java contains Java code that performs a series of tests. The tests call methods from the Deque class; some of them print what those methods return. Each test is also followed by a comment that tells how many points it is worth, and optionally what must be printed if it works correctly

Run the tests, then turn in the Java source code for your Deque class.

///////////////////////////////////////////////////////////////////////////////////////////////////////////////

tests.java

Explanation / Answer

I HAVE DONE THIS JOB IN ECLIPSE, I PUT SOME COMMENTS FOR BETTER UNDERSTANDING.

HERE IS THE CODE:

//ObservationDeque.java

public class ObservationDeque
{

// MAIN. Test the DEQUE on various example arguments.

public static void main(String [] args)
{
Deque<String> deque = new Deque<String>();

System.out.println(deque.isEmpty()); // true 2 points.

try
{
System.out.println(deque.dequeueFront());
}
catch (IllegalStateException ignore)
{
System.out.println("No dequeueFront."); // No dequeueFront. 2 points.
}

try
{
System.out.println(deque.dequeueRear());
}
catch (IllegalStateException ignore)
{
System.out.println("No dequeueRear."); // No dequeueRear. 2 points.
}

// Enqueueing to the rear and dequeueing from the rear makes the DEQUE act
// like a stack.

deque.enqueueRear("A");
deque.enqueueRear("B");
deque.enqueueRear("C");

System.out.println(deque.isEmpty()); // false 2 points.

System.out.println(deque.dequeueRear()); // C 2 points.
System.out.println(deque.dequeueRear()); // B 2 points.
System.out.println(deque.dequeueRear()); // A 2 points.

System.out.println(deque.isEmpty()); // true 2 points.

// Enqueueing to the rear and dequeueing from the front makes the DEQUE act
// like a queue.

deque.enqueueRear("A");
deque.enqueueRear("B");
deque.enqueueRear("C");

System.out.println(deque.dequeueFront()); // A 2 points.
System.out.println(deque.dequeueFront()); // B 2 points.
System.out.println(deque.dequeueFront()); // C 2 points.

System.out.println(deque.isEmpty()); // true 2 points.

// Enqueueing to the front and dequeueing from the front makes the DEQUE act
// like a stack.

deque.enqueueFront("A");
deque.enqueueFront("B");
deque.enqueueFront("C");

System.out.println(deque.dequeueFront()); // C 2 points.
System.out.println(deque.dequeueFront()); // B 2 points.
System.out.println(deque.dequeueFront()); // A 2 points.

System.out.println(deque.isEmpty()); // true 2 points.

// Enqueueing to the front and dequeueing from the rear makes the DEQUE act
// like a queue.

deque.enqueueFront("A");
deque.enqueueFront("B");
deque.enqueueFront("C");

System.out.println(deque.dequeueRear()); // A 2 points.
System.out.println(deque.dequeueRear()); // B 2 points.
System.out.println(deque.dequeueRear()); // C 2 points.

System.out.println(deque.isEmpty()); // true 2 points.
}
}

//Node.java

class Deque<Base>
{
private Node head; // Head node of the circular-doubly linked list.
private int count; // Number of nodes in the deque.
  
private class Node
{
private Base object; // The given nodes object.
private Node left; // Pointer to node to given nodes left.
private Node right; // Pointer to node to given nodes right.
  
private Node(Base object, Node prev, Node next)
{
this.object = object;
this.left = prev;
this.right = next;
}
}
  
// Constructs a new instance of a deque.
public Deque()
{
head = new Node(null, null, null); // Creates the "dummy" head node.
head.right = head; // Head's right pointer initially points at itself.
head.left = head; // Head's left pointer initially points at itself.
count = 0; // The count of nodes in the list is set to 0. The head node does not count.
}
// Allows insertion of a new node immediately in front of the head node.
public void enqueueFront(Base object)
{
if (isEmpty()) // A special case is needed if the head node is alone in the list.
{
Node temp = new Node(object, head, head); // Since list empty, new nodes left & right pointers will point at head.
head.left = temp; // Heads left pointer needs to point to the new node.
head.right = temp; // Heads right pointer needs to point to the new node.
count++; // Theres a new node in the list. Increment the count.
}
else // There is more than just the head node in the list.
{
Node temp = new Node(object, head, head.right); // Since enqueueFront, new nodes left = head & right = whatever is right of head.
head.right.left = temp; // Setting whatever is to the right of head's left pointer to new node.
head.right = temp; // Completes the insertion of new node in front of head node.
count++; // Theres a new node in the list. Increment the count.
}
}
  
// Allows insertion of a new node immediately in back of the head node.
// If you understand enqueueFront, you understand enqueueRear. They are almost identical.
public void enqueueRear(Base object)
{
if (isEmpty())
{
Node temp = new Node(object, head, head);
head.left = temp;
head.right = temp;
count++;
}
else
{
Node temp = new Node(object, head.left, head);
head.left.right = temp;
head.left = temp;
count++;
}
}
  
// Allows deletion of the node immediately in front of the head node.
public Base dequeueFront()
{
if (isEmpty()) // You cant delete a node from an empty list.
{
throw new IllegalStateException("Deque is empty. No more nodes to dequeue.");
}
else
{
Base temp = head.right.object; // We want to return the object of the node we are deleting. Store it temporarily.
head.right.right.left = head; // Node to the right of the frontmost node, its left pointer needs to be broken from the front node.
head.right = head.right.right; // Effectively deletes front node, nothing points to it any longer.
count--; // We just deleted a node from the front. Decrement the count.
return temp; // Return the object from the deleted node as intended.
}
}
  
// Allows deletion of the node immediately behind the head node.
// If you understand dequeueFront, you understand dequeueRear. They are almost identical.
public Base dequeueRear()
{
if(isEmpty())
{
throw new IllegalStateException("Deque is empty. No more nodes to dequeue");
}
else
{
Base temp = head.left.object;
head.left.left.right = head;
head.left = head.left.left;
count--;
return temp;
}
}
// Returns true if the list is empty otherwise returns false.
public boolean isEmpty()
{
return head.right == head && head.left == head; // If both pointers are pointing at itself, no nodes have been added.
}
  
// Returns the number of nodes in the deque.
public int getCount()
{
return count;
}
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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