Java Deque Implementation

Question

Java newbie question: I'm trying to implement a deque in Java and am having issues with the dequeueBack (remove an element from the rear of the queue) and enqueueFront (add an element to the front of the queue) methods. I've gotten the opposite methods to work (dequeueFront and enqueueBack), but I'm stumped at this point. Any suggestions?

public class Carr_A06Q4
{
/**
 * Program entry point for deque testing.
 * @param args Argument list.
 */    
public static void main(String[] args)
{
    LinkedDequeue<Integer> deque = new LinkedDequeue<Integer>();

    System.out.println("DEQUE TESTING");

    //per Q1
    deque.enqueueBack(3);
    deque.enqueueBack(7);
    deque.enqueueBack(4);
    deque.dequeueFront();        
    deque.enqueueBack(9);
    deque.enqueueBack(8);
    deque.dequeueFront();
    System.out.println("The size of the deque is: " + deque.size());
    System.out.println("The deque contains:\n" + deque.toString());   

    //new features
    System.out.println(deque.dequeueFront());
    deque.enqueueFront(1);
    deque.enqueueFront(11);                         
    deque.enqueueFront(3);                 
    deque.enqueueFront(5);
    System.out.println(deque.dequeueBack());
    System.out.println(deque.dequeueBack());        
    System.out.println(deque.last());
    deque.dequeueFront();
    deque.dequeueFront();
    System.out.println(deque.first());        
    System.out.println("The size of the deque is: " + deque.size());
    System.out.println("The deque contains:\n" + deque.toString());            
}

/**
 * LinkedDeque represents a linked implementation of a deque.
 * 
 */
public static class LinkedDequeue<T> implements DequeADT<T>
{
    private int count;
    private LinearDoubleNode<T> head, tail; //front, back

    /**
     * Creates an empty queue.
     */
    public LinkedDequeue()
    {
        count = 0;
        head = tail = null;
    }

    /**
     * Adds the specified element to the tail of this queue.
     * @param element the element to be added to the tail of the queue
     */
    public void enqueueBack(T element)
    {
        LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);

        if (isEmpty())
            head = node;
        else
            tail.setNext(node);

        tail = node;
        count++;
    }

    /**
     * Adds the specified element to the head of this queue.
     * @param element the element to be added to the head of the queue
     */
    public void enqueueFront(T element)
    {
        LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);

        count++ ;    
        if (head == null) 
        {
            head = node;
        }
        else 
        {
            node.setNext(head);
            head = node;
        }
    }

    /**
     * Removes the element at the head of this queue and returns a
     * reference to it. 
     * @return the element at the head of this queue
     * @throws EmptyCollectionException if the queue is empty
     */
    public T dequeueFront() throws EmptyCollectionException
    {
       if (isEmpty())
            throw new EmptyCollectionException("queue");

        T result = head.getElement();
        head = head.getNext();
        count--;

        if (isEmpty())
            head = null;

        return result;
    }

    /**
     * Removes the element at the tail of this queue and returns a
     * reference to it. 
     * @return the element at the tail of this queue
     * @throws EmptyCollectionException if the queue is empty
     */
    public T dequeueBack() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("queue");

        T result = tail.getElement();
        tail = tail.getNext();

        if (isEmpty())
            head = null;
        count --;

        return result;
    }

    /**
     * Returns a reference to the element at the head of this queue.
     * The element is not removed from the queue.  
     * @return a reference to the first element in this queue
     * @throws EmptyCollectionsException if the queue is empty
     */
    public T first() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        T result = head.getElement();
        return result;
    }

    /**
     * Returns a reference to the element at the tail of this queue.
     * The element is not removed from the queue.  
     * @return a reference to the first element in this queue
     * @throws EmptyCollectionsException if the queue is empty
     */
    public T last() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        T result = tail.getElement();
        return result;
    }

    /**
     * Returns true if this queue is empty and false otherwise. 
     * @return true if this queue is empty 
     */
    public boolean isEmpty()
    {
        if (head == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    /**
     * Returns the number of elements currently in this queue.
     * @return the number of elements in the queue
     */
    public int size()
    {
        return count;
    }

    /**
     * Returns a string representation of this queue. The front element
     * occurs first, and each element is separated by a space. If the
     * queue is empty, returns "empty".
     * @return the string representation of the queue
     */
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
       LinearDoubleNode<T> tmp = head;
       while (tmp != null)
       {
        sb.append(tmp.getElement()).append(" ");
        tmp = tmp.getNext();
       }
       return sb.toString();
    }
}

}

I need to get an output of:

DEQUE TESTING: The size of the deque is: 3 The deque contains:

498

4

8

9

1

11

The size of the deque is: 2 The deque contains: 11 1

But instead I'm getting:

DEQUE TESTING: The size of the deque is: 3 The deque contains:

498

4

8

and then I get a NullPointerException in the dequeueBack method.

Any help is appreciated!

Also, the interface is:

public interface DequeADT<T>
{
/**  
 * Adds one element to the front of this deque. 
 * @param element the element to be added to the front of the deque  
 */
public void enqueueFront(T element); //deque specific

/**  
 * Adds one element to the back of this deque. 
 * @param element the element to be added to the back of the deque  
 */
public void enqueueBack(T element);

/**  
 * Removes and returns the element at the front of this deque.
 * Should throw an exception if the deque is empty.
 * @return the element at the front of this deque
 */
public T dequeueFront();

/**  
 * Removes and returns the element at the back of this deque.
 * Should throw an exception if the deque is empty.
 * @return the element at the back of the deque. 
 */
public T dequeueBack(); //deque specific  

/**  
 * Returns, without removing, the element at the front of this deque.
 * Should throw an exception if the deque is empty.
 * @return the first element in the deque
 */
public T first();

/**  
 * Returns, without removing, the element at the back of this deque.
 * Should throw an exception if the deque is empty.
 * @return the last element in the deque
 */
public T last(); //deque specific  

/**  
 * Returns true if this deque is empty and false otherwise.
 * @return true if this deque is empty
 */
public boolean isEmpty();

/**  
 * Returns the number of elements in this deque. 
 * @return the number of elements in the deque
 */
public int size();

/**  
 * Returns a string representation of this deque. The front element
 * occurs first, and each element is separated by a space. If the
 * deque is empty, returns "empty".
 * @return the string representation of the deque
 */
public String toString();

}

and a description of the node is:

public class LinearDoubleNode<T>
{
private LinearDoubleNode<T> next;
private T element;

/**
 * Creates an empty node.
 */
public LinearDoubleNode()
{
    next = null;
    element = null;
}

/**
 * Creates a node storing the specified element.
 * @param elem element to be stored
 */
public LinearDoubleNode(T elem)
{
    next = null;
    element = elem;
}

/**
 * Returns the node that follows this one.
 * @return reference to next node
 */
public LinearDoubleNode<T> getNext()
{
    return next;
}

/**
 * Sets the node that follows this one.
 * @param node node to follow this one
 */
public void setNext(LinearDoubleNode<T> node)
{
    next = node;
}

/**
 * Returns the element stored in this node.
 * @return element stored at the node
 */
public T getElement()
{
    return element;
}

/**
 * Sets the element stored in this node.
 * @param elem element to be stored at this node
 */
public void setElement(T elem)
{
    element = elem;
}

}

Andreas · Accepted Answer · 2016-04-24 23:20:43Z

3

The only way you can get that to perform, is for the internal list to be double-linked.

Otherwise you'll have to scan the entire list to find the second-last node, in order to remove the last node.

Double-ended queue ➔ Double-linked list
or dynamic array (see Implementations section).

answered Apr 24, 2016 at 23:20

Andreas

160k13 gold badges164 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Beshoy Gerges Yacoub · Accepted Answer · 2018-03-08 10:12:20Z

public class LinkedDQueue implements DQueue {

private int size;
private LinearDoubleNode<T> head, tail; // front, back
private int capcity;

public LinkedDQueue() {
    capcity = 10;
}

public LinkedDQueue(int capcity) {

    this.capcity = capcity;
}

@Override
public boolean full() {
    return size == capcity;
}

@Override
public void addFirst(T e) throws CapcityExceededException {
    if (full())
        throw new CapcityExceededException("size overflow");

    LinearDoubleNode<T> node = new LinearDoubleNode<T>(e);

    if (head == null) {
        head = node;
        tail = node;
    } else {
        node.setNext(head);
        head = node;
    }
    size++;

}

@Override
public void addLast(T e) throws CapcityExceededException {
    LinearDoubleNode<T> node = new LinearDoubleNode<T>(e);

    if (full())
        throw new CapcityExceededException("size overflow");

    if (tail == null) {
        head = tail = node;
    } else {
        tail.setNext(node);
        node.setPrevious(tail);
    }

    tail = node;
    size++;

}

@Override
public T removeFirst() {
    if (isEmpty())
        return null;

    T result = head.getElement();
    head.getNext().setPrevious(null);
    head = head.getNext();
    size--;

    return result;
}

@Override
public T removeLast() {

    LinearDoubleNode<T> temp = tail; // Save address of Node to delete
    if (isEmpty()) {
        return null;
    }

    if (head == tail) {
        head = null;
        tail = null;
        size = 0;
        return tail.getElement();
    }

    T result = tail.getElement();
    tail = temp.getPrevious();
    tail.setNext(null);
    size--;

    return result;
}

@Override
public T getFirst() {
    if (isEmpty())
        return null;

    T result = head.getElement();
    return result;
}

@Override
public T getLast() {
    if (isEmpty())
        return null;

    T result = tail.getElement();
    return result;
}

@Override
public int length() {
    return size;
}

@Override
public void reverse() {

}

@Override
public boolean isEmpty() {
    if (head == null) {
        return true;
    } else {
        return false;
    }
}

@Override
public int size() {
    return size;
}

@Override
public String toString() {
    LinearDoubleNode<T> temp = head; // Save address of Node to delete
    StringBuilder builder = new StringBuilder();
    while (temp != null) {
        builder.append(temp.getElement() + "");
        temp = temp.getNext();

    }
    return builder.toString();
}

class LinearDoubleNode<T> {
    private LinearDoubleNode<T> next;
    private LinearDoubleNode<T> previous;
    private T element;

    /**
     * Creates an empty node.
     */
    public LinearDoubleNode() {
        next = null;
        previous = null;
        element = null;
    }

    /**
     * Creates a node storing the specified element.
     * 
     * @param elem
     *            element to be stored
     */
    public LinearDoubleNode(T elem) {
        next = null;
        previous = null;
        element = elem;
    }

    /**
     * Returns the node that follows this one.
     * 
     * @return reference to next node
     */
    public LinearDoubleNode<T> getNext() {
        return next;
    }

    public LinearDoubleNode<T> getPrevious() {
        return previous;
    }

    public void setPrevious(LinearDoubleNode<T> previous) {
        this.previous = previous;
    }

    /**
     * Sets the node that follows this one.
     * 
     * @param node
     *            node to follow this one
     */
    public void setNext(LinearDoubleNode<T> node) {
        next = node;
    }

    /**
     * Returns the element stored in this node.
     * 
     * @return element stored at the node
     */
    public T getElement() {
        return element;
    }

    /**
     * Sets the element stored in this node.
     * 
     * @param elem
     *            element to be stored at this node
     */
    public void setElement(T elem) {
        element = elem;
    }
}

}

class CapcityExceededException extends Exception { private String message;

public CapcityExceededException(String message) {
    super(message);
    this.message = message;

}

}

Garvit Khamesra · Accepted Answer · 2019-09-27 17:25:09Z

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * The type Deque.
 *
 * @param <Item> the type parameter
 */
public class Deque<Item> implements Iterable<Item> {
    /**
     * The Head.
     */
    private Node<Item> head;
    /**
     * The Tail.
     */
    private Node<Item> tail;
    /**
     * The Deque size.
     */
    private int dequeSize;

    private class Node<Item> {
        /**
         * The Data.
         */
        Item data;
        /**
         * The Next.
         */
        Node<Item> next;
        /**
         * The Prev.
         */
        Node<Item> prev;

        /**
         * Instantiates a new Node.
         *
         * @param data the data
         */
        Node(Item data) {
            this.data = data;
        }
    }

    /**
     * Instantiates a new Deque.
     */
    public Deque() {
        dequeSize = 0;
    }

    /**
     * Is empty boolean.
     *
     * @return the boolean
     */
    public boolean isEmpty() {
        return dequeSize == 0;
    }

    /**
     * Size int.
     *
     * @return the int
     */
    public int size() {
        return dequeSize;
    }

    /**
     * Add first.
     *
     * @param item the item
     */
    public void addFirst(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node<Item> newNode = new Node<Item>(item);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            head.prev = newNode;
            newNode.next = head;
            head = newNode;
        }
        dequeSize++;
    }

    /**
     * Add last.
     *
     * @param item the item
     */
    public void addLast(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node<Item> newNode = new Node<Item>(item);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        dequeSize++;
    }

    /**
     * Remove first item.
     *
     * @return the item
     */
    public Item removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item headData = head.data;
        if (dequeSize == 1) {
            head = null;
            tail = null;
        } else {
            Node<Item> headNext = head.next;
            headNext.prev = null;
            head = headNext;
        }
        dequeSize--;
        return headData;
    }

    /**
     * Remove last item.
     *
     * @return the item
     */
    public Item removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item tailData = tail.data;
        if (dequeSize == 1) {
            head = null;
            tail = null;
        } else {
            Node<Item> tailPrev = tail.prev;
            tailPrev.next = null;
            tail = tailPrev;
        }
        dequeSize--;
        return tailData;
    }

    /**
     * Iterator iterator.
     *
     * @return the iterator
     */
    public Iterator<Item> iterator() {
        return new CustomIterator();
    }

    private class CustomIterator implements Iterator<Item> {
        private Node<Item> temp;

        /**
         * Instantiates a new Custom iterator.
         */
        CustomIterator() {
            temp = head;
        }

        public boolean hasNext() {
            return temp.next != null;
        }
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item tempData = temp.data;
            temp = temp.next;
            return tempData;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        // unit testing (required)
    }
}

Collectives™ on Stack Overflow

Java Deque Implementation

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related