1
\$\begingroup\$

I have just started learning to code for interviews and I would like to request a code review of a "Dequeue" data structure. I could not find any implementation anywhere to compare it to. I would like to request a code review. The program is written in Java.

// Copyright 2017 ManOf Logan. All Rights Reserved.
package com.manoflogan.ds;

/**
 * Strategy definition for dequeue data structure.
 */
 public interface Dequeue<T> {

   /**
    * Enqueues from the front.
    *
    * @param object object to be enqueued
    */
   void enqueueFront(T object);

   /**
    * Enqueues from the rear
    *
    * @param object object to be enqueued
    */
   void enqueueRear(T object);

   /**
    * Dequeues from the front.
    *
    * @return dequeued object
    */
   T dequeueFront();

   /**
    * Dequeued from the rear.
    *
    * @return dequeued object
    */
   T dequeueRear();

  /**
   * Peeks the object from the front
   *
   * @return peeked object
   */
  T peekFront();

  /**
   * Peeks the object from the rear
   *
   * @return peeked object
   */
  T peekRear();

  /**
   * Returns {@code true} if the queue is full; false otherwise
   */
  boolean isFull();

  /**
   * Returns {@code true} if the queue is empty; false otherwise
   */
  boolean isEmpty();
}

The implementation is given below

// Copyright 2017 ManOf Logan. All Rights Reserved.
package com.manoflogan.ds;

import java.lang.reflect.Array;

/**
 * Implements a dequeue structure with an array.
 */
public class DequeueWithAnArray<T> implements Dequeue<T> {

  private final T[] queueObjects;

  private final int capacity;

  private int frontInsertIndex;

  private int frontDeleteIndex;

  private int rearInsertIndex;

  private int rearDeleteIndex;

  /**
   * Constructor for {@link DequeueWithAnArray}.
   *
   * @param clazz class to be instantiated
   * @param capacity size of the array
   */
  @SuppressWarnings("unchecked")
  // Casting from object array to generic type array.
  public DequeueWithAnArray(Class<T> clazz, int capacity) {
    this.queueObjects = (T[]) Array.newInstance(clazz, capacity);
    this.capacity = capacity;
    this.frontInsertIndex = -1;
    this.frontDeleteIndex = 0;
    this.rearInsertIndex = this.capacity;
    this.rearDeleteIndex = (this.capacity - 1);
  }
  /**
   * Enqueues from the front.
   *
   * @param object object to be enqueued
   */
  @Override
  public void enqueueFront(T object) {
    if (this.isFull()) {
      throw new IllegalStateException("The queue is full");
    }
    if (this.frontInsertIndex < (this.rearInsertIndex - 1)) {
      this.queueObjects[++ this.frontInsertIndex] = object;
    }
  }

  /**
   * Enqueues from the rear
   *
   * @param object object to be enqueued
   */
  @Override
  public void enqueueRear(T object) {
    if (this.isFull()) {
      throw new IllegalStateException(("The queue is full."));
    }
    if (this.rearInsertIndex > (this.frontInsertIndex + 1))
    this.queueObjects[--this.rearInsertIndex] = object;
  }

  /**
   * Dequeued from the front.
   *
   * @return dequeued object
   */
  @Override
  public T dequeueFront() {
    if (this.isEmpty()) {
      throw new IllegalStateException("The queue is empty.");
    }
    if (this.frontDeleteIndex < (this.rearDeleteIndex -1)) {
      T object = this.queueObjects[this.frontDeleteIndex];
      this.queueObjects[this.frontDeleteIndex ++] = null;

      return object;
    }
    throw new IllegalStateException("The queue is empty.");
  }

  /**
   * Dequeued from the rear.
   *
   * @return dequeued object
   */
  @Override
  public T dequeueRear() {
    if (this.isEmpty()) {
      throw new IllegalStateException("The queue is empty.");
    }
    if ((this.rearDeleteIndex > (this.frontDeleteIndex + 1)) &&
        (this.rearInsertIndex <= this.rearDeleteIndex)) {
      T object = this.queueObjects[this.rearDeleteIndex];
      this.queueObjects[this.rearDeleteIndex --] = null;
      return object;
    }
    throw new IllegalStateException("The queue is empty.");
  }

  /**
   * Peeks the object from the front
   *
   * @return peeked object
   */
  @Override
  public T peekFront() {
    if (this.isEmpty()) {
      throw new IllegalStateException("The queue is empty.");
    }
    return this.queueObjects[this.frontInsertIndex];
  }

  /**
   * Peeks the object from the rear
   *
   * @return peeked object
   */
  @Override
  public T peekRear() {
    if (this.isEmpty()) {
      throw new IllegalStateException("The queue is empty.");
    }
    return this.queueObjects[this.rearInsertIndex];
  }

  /**
   * Returns {@code true} if the queue is full; false otherwise
   */
  @Override
  public boolean isFull() {
    if ((this.frontInsertIndex == (this.capacity -1) && (this.rearInsertIndex == this.capacity)) ||
        (this.rearInsertIndex == 0 && this.frontInsertIndex == -1)){
      return true;
    }
    return false;
  }

  /**
   * Returns {@code true} if the queue is empty; false otherwise
   */
  @Override
  public boolean isEmpty() {
    if (this.frontInsertIndex == -1 && this.rearInsertIndex == (this.capacity - 1)) {
      return true;
    }
    if ((this.rearDeleteIndex - 1) == this.frontDeleteIndex) {
      return true;
    }
    return false;
  }
}

I am attempting to prepare for an interview so any feedback is gratefully appreciated. I have uploaded other data structures on my GitHub profile as well.

\$\endgroup\$
  • 2
    \$\begingroup\$ Does it work as intended? \$\endgroup\$ – πάντα ῥεῖ Mar 15 '17 at 21:39
  • \$\begingroup\$ I don't know how to verify my implementation. Hence my question. \$\endgroup\$ – manoflogan Mar 15 '17 at 22:23
  • \$\begingroup\$ Java comes with its own Deque interface. You might want to look at that, and java.util.ArrayDeque and how it works. I guess not being aware of that would be not a great way to start your job interview. Not knowing how to write a unit test to check if your (is it actually yours?) code actually works doesn't help. So you may want to look into that as well. \$\endgroup\$ – Jilles van Gurp Mar 16 '17 at 12:02
  • \$\begingroup\$ Hi Jilles, I am aware that there is a Deque interface and ArrayDeque class. But I have been told that I need to implement these data structures from scratch during interviews. So I am trying to implement them myself for practice. I also did write these classes myself in addition to ones in my Github profile. If I have to write tests for it, then I have to set up expectations for the results. The issue is that if I get my expectations incorrect, then I may tweak the source code to make sure that the expectations are correct. That is my fear, so I asked this question on StackExchange. \$\endgroup\$ – manoflogan Mar 17 '17 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.