Implementation of Double-Ended Queue (Deque)

I have already covered Queue Implementation in my previous posts. Let's consider now a queue-like data structure that supports insertion and deletion at both the front and the rear of the queue. Such an extension of queue is called "Double-Ended Queue" or "Deque".

Let's look at the abstraction of Deque:

1. Deque.java

package ora.deque;

public interface Dequeue {

void insertFirst(Object obj);

void insertLast(Object obj);

Object removeFirst();

Object removeLast();

int size();

}

Now let's implement deque functionality using a following linked list data structure.

2. DLNode.java

package ora.linked;

public class DLNode {

private DLNode next, previous;

private Object element;

public DLNode(Object element, DLNode next, DLNode previous) {

this.element = element;

this.next = next;

this.previous = previous;

}

public DLNode() {

this(null, null, null);

}

public DLNode getNext() {

return this.next;

}

public DLNode getPrevious() {

return this.previous;

}

public Object getElement() {

return this.element;

}

public void setNext(DLNode node) {

this.next = node;

}

public void setPrevious(DLNode node) {

this.previous = node;

}

}

3. DequeImpl.java

package ora.deque;

import ora.linked.DLNode;

public class DequeImpl implements Dequeue {

private DLNode header, tail;

private int size=0;

public DequeImpl() {

this.header = new DLNode();

this.tail = new DLNode();

this.size = 0;

header.setNext(tail);

tail.setPrevious(header);

}

@Override

public void insertFirst(Object obj) {

DLNode nextNode = header.getNext();

DLNode node = new DLNode(obj, header, nextNode);

nextNode.setPrevious(node);

header.setNext(node);

size++;

}

@Override

public void insertLast(Object obj) {

DLNode previous = tail.getPrevious();

DLNode node = new DLNode(obj, tail, previous);

previous.setNext(node);

tail.setPrevious(node);

size++;

}

@Override

public Object removeFirst() {

if (size() == 0)

return null;

DLNode first = header.getNext();

Object o = first.getElement();

DLNode node = first.getNext();

header.setNext(node);

node.setPrevious(header);

header = node;

size--;

return o;

}

@Override

public Object removeLast() {

if (size() == 0)

return null;

DLNode lastNode = tail.getPrevious();

Object o = lastNode.getElement();

DLNode node = lastNode.getPrevious();

node.setNext(tail);

tail.setPrevious(node);

size--;

return o;

}

@Override

public int size() {

return this.size;

}

}

Stack implementation in java using Queue

This is the one of the most frequently asked question in core-java interviews.

I would recommend you to look previous posts in my blog about "Stack implementation" and "Queue implementation" so that, it would make more sense to understand below code.


 1. StackImplUsingQueue.java

package ora.stackex;

import ora.queue.Queue;
import ora.queue.QueueImpl;

public class StackImplUsingQueue implements Stack {
   
    private Queue queue;
   
    @Override
    public boolean isEmpty() {
        return queue == null ? true : (queue.size() == 0);
    }

    @Override
    public Object pop() throws StackEmptyException {
        if (isEmpty())
            return null;
       
        for (int i=0; i<size()-1; i++)
            queue.enqueue(queue.dequeue());
        return queue.dequeue();
    }

    @Override
    public void push(Object obj) throws StackOverflowException {
        if (isEmpty())
            queue = new QueueImpl();
        queue.enqueue(obj);
    }

    @Override
    public int size() {
        return queue == null ? 0 : queue.size();
    }

    @Override
    public Object top() throws StackEmptyException {
        if (isEmpty())
            return null;
       
        Object obj = pop();
        queue.enqueue(obj);
        return obj;
    }

}

Queue implementation in Java

Lets' imagine, there is no Queue functionality (First In - First Out) present in the Java library, and if you were asked to implement Queue functionality, how would you do that?

I am here with java code for the Queue functionality implementation.

1. Queue.java

package ora.queue;

/**
 * @author sateesh
 *
 */
public interface Queue {

    /**
     * @param obj
     */
    void enqueue(Object obj);
   
    /**
     * @return
     */
    Object dequeue();
   
    /**
     * @return
     */
    int size();
}

2. QueueImpl.java

package ora.queue;

import ora.stackex.*;

public class QueueImpl implements Queue {
    private Stack input;
    private Stack output;
    public QueueImpl() {
        input = new StackImpl();
        output = new StackImpl();
    }
   
    @Override
    public Object dequeue() {
        if (input.size() > 0) {
            int j = input.size();
            for (int i=0; i<j; i++) {
                output.push(input.pop());
            }
        }
       
        if (output.size() == 0)
            return null;
       
        return output.pop();
    }

    @Override
    public void enqueue(Object obj) {
       
        if (output.size() == 0) {
            input.push(obj);
        } else {
            int j = output.size();
            for (int i=0; i<j; i++)
                input.push(output.pop());
           
            input.push(obj);
        }
    }

    @Override
    public int size() {
        return input.size() == 0 ? output.size() : input.size();
    }

}

Stack implementation in Java

Most of java developers are not really interested to know about the internal implementation of collections framework/data structure implementation. Of-course, I too was not the exceptional, initial days of my programming, I never really bothered about this, however, during last one year I started looking into the internal implementation of collections framework/data structure.

Recently I have taken decision to document all of my work, so that it would be helpful for both me and others who are interested to know.

Now, lets look how we can implement Stack data-structure using java.
Stack data-structure principle: First-In, Last-Out

1. StackEmptyException.java

package ora.stackex;

public class StackEmptyException extends RuntimeException {

    /**
     * serialVersionUID
     */
    private static final long serialVersionUID = 1L;
   
    public StackEmptyException(String message) {
        super(message);
    }

}

2.  StackOverflowException.java 

package ora.stackex;

public class StackOverflowException extends RuntimeException {

    /**
     *
     */
    private static final long serialVersionUID = 1L;
   
    public StackOverflowException(String message) {
        super(message);
    }

}

3. Stack.java

package ora.stackex;

public interface Stack {

    int size();
   
    boolean isEmpty();
   
    Object top() throws StackEmptyException;
   
    void push(Object obj) throws StackOverflowException;
   
    Object pop() throws StackEmptyException;
}

4. StackImpl.java

package ora.stackex;

public class StackImpl implements Stack {

    Object[] stackArr = new Object[10];
    int pos = -1; 
   
    @Override
    public boolean isEmpty() {
        if(pos == -1)
            return true;
        return false;
    }

    @Override
    public Object pop() throws StackEmptyException {
        if (pos == -1) {
            throw new StackEmptyException("Stack is empty");
        }
       
        Object obj = stackArr[pos];
        stackArr[pos] = null;
        pos--;
        return obj;
    }

    @Override
    public void push(Object obj) throws StackOverflowException {
        int npos = pos + 1;
        if (npos == 10)
            throw new StackOverflowException("Stack is full");
        pos = npos;
        stackArr[pos] = obj;       
    }

    @Override
    public int size() {
        return pos+1;
    }

    @Override
    public Object top() throws StackEmptyException {
        if (pos == -1)
            throw new StackEmptyException("Stack is empty");
        Object obj = stackArr[pos];
        return obj;
    }

}