Question

JAVA

* This is a skeleton file. Complete the functions below. You
* may also edit the function "main" to test your code.
*
* You should not use any loops or recursions. Your code needs to run in
* constant time. It is OK if your testing code has loops (like in checkInvariants).
*
* You must not add fields or static variables. As always, you must not change
* the declaration of any method nor the name of the class or of this file.
*/

public class Deque {

   private Node first;   // A reference to the first item in the Dequeue (or
                           // null if empty)
   private Node last;   // A reference to the last item in the Dequeue (or
                           // null if empty)
   private int N;            // The number of items currently in the Dequeue

   static class Node {
      
       public T item;           // The data stored at this node.
       public Node next;   // The node to the right (or null if there is no
                               // node to the right)
       public Node prev;   // The node to the lett (or null if there is no
                               // node to the left)
   }

   /**
   * Construct an empty Deque.
   */
   public Deque() {
       // TODO - Replace the line below with a correct solution.
       throw new RuntimeException("Not implemented");
   }

   /**
   * Tests if the Dequeue is empty.
   *
   * @return true if this Deque is empty and false
   * otherwise.
   */
   public boolean isEmpty() {
       // TODO - Replace the line below with a correct solution.
       throw new RuntimeException("Not implemented");
   }

   /**
   * Returns the number of items currently in this Deque.
   *
   * @return the number of items currently in this Deque
   */
   public int size() {
       // TODO - Replace the line below with a correct solution.
       throw new RuntimeException("Not implemented");
   }

   /**
   * Inserts an item into the front of this Deque.
   *
   * @param item
   * the item to be inserted
   */
   public void pushFront(T item) {
       // TODO - Replace the line below with a correct solution.
       throw new RuntimeException("Not implemented");
   }

   /**
   * Inserts an item into the back of this Deque.
   *
   * @param item
   * the item to be inserted
   */
   public void pushBack(T item) {
       // TODO - Replace the line below with a correct solution.
       throw new RuntimeException("Not implemented");
   }

   /**
   * Removes and returns the item at the front of this Deque.
   *
   * @return the item at the front of this Deque.
   * @throws NoSuchElementException if this Deque is empty.
   */
   public T popFront() {
       // TODO - Replace the line below with a correct solution.
       throw new RuntimeException("Not implemented");
   }

   /**
   * Removes and returns the item at the back of this Deque.
   *
   * @return the item at the back this Deque.
   * @throws NoSuchElementException if this Deque is empty.
   */
   public T popBack() {
       // TODO - Replace the line below with a correct solution.
       throw new RuntimeException("Not implemented");
   }
}

Answer 1

The completed sourcecode is given below:

package temp;

import java.util.NoSuchElementException;

public class Deque<T> {

   private Node first; // A reference to the first item in the Dequeue (or
   // null if empty)
   private Node last; // A reference to the last item in the Dequeue (or
   // null if empty)
   private int N; // The number of items currently in the Dequeue

   static class Node<T> {
  
   public T item; // The data stored at this node.
   public Node next; // The node to the right (or null if there is no
   // node to the right)
   public Node prev; // The node to the lett (or null if there is no
   // node to the left)
   }

   /**
   * Construct an empty Deque.
   */
   public Deque() {
   // TODO - Replace the line below with a correct solution.
   //throw new RuntimeException("Not implemented");
       first = null;
       last = null;
       N = 0;
   }

   /**
   * Tests if the Dequeue is empty.
   *
   * @return true if this Deque is empty and false
   * otherwise.
   */
   public boolean isEmpty() {
   // TODO - Replace the line below with a correct solution.
   //throw new RuntimeException("Not implemented");
       if(N==0) {
           return true;
       }else {
           return false;
       }
   }

   /**
   * Returns the number of items currently in this Deque.
   *
   * @return the number of items currently in this Deque
   */
   public int size() {
   // TODO - Replace the line below with a correct solution.
   //throw new RuntimeException("Not implemented");
       return N;
   }

   /**
   * Inserts an item into the front of this Deque.
   *
   * @param item
   * the item to be inserted
   */
   public void pushFront(T item) {
   // TODO - Replace the line below with a correct solution.
   //throw new RuntimeException("Not implemented");
       Node<T> n = new Node<T>();
       n.item = item;
       if(!isEmpty()) {
           first.prev=n;
           n.next = first;
           first = n;
       }else {
           first = n;
           last = n;
       }
       N++;
   }

   /**
   * Inserts an item into the back of this Deque.
   *
   * @param item
   * the item to be inserted
   */
   public void pushBack(T item) {
   // TODO - Replace the line below with a correct solution.
       Node<T> n = new Node<T>();
       n.item = item;
       if(!isEmpty()) {
           last.next = n;
           n.prev=last;
           last = n;
       }else {
           first = n;
           last = n;
       }
       N++;
   }

   /**
   * Removes and returns the item at the front of this Deque.
   *
   * @return the item at the front of this Deque.
   * @throws NoSuchElementException if this Deque is empty.
   */
   public T popFront() {
   // TODO - Replace the line below with a correct solution.
   // throw new RuntimeException("Not implemented");
       Node<T> n = null;
       if(isEmpty()) {
           throw new NoSuchElementException("Deque is empty");
       }else {
           n = first;
           first = n.next;
           N--;
       }
       return n.item;
   }

   /**
   * Removes and returns the item at the back of this Deque.
   *
   * @return the item at the back this Deque.
   * @throws NoSuchElementException if this Deque is empty.
   */
   public T popBack() {
   // TODO - Replace the line below with a correct solution.
   // throw new RuntimeException("Not implemented");
       Node<T> n = null;
       if(isEmpty()) {
           throw new NoSuchElementException("Deque is empty");
       }else {
           n = last;
           last = n.prev;
           N--;
       }
       return n.item;
   }
     
   /*
   * main() function to test code
   */
   public static void main(String[] args) {
       //Create empty deque
          Deque<Integer> deqeue = new Deque<Integer>();
           deqeue.pushFront(40);
           deqeue.pushFront(50);
           deqeue.pushBack(60);
           deqeue.pushBack(70);
          
           System.out.println("Front = "+deqeue.popFront());
           System.out.println("Back = "+deqeue.popBack());
   }
   }

You may add your own test code to test the implementation. The output of the current test is given below: