Today we will implement a Double-ended queue in Java. We will use generics so that our queue can work with any datatypes, like Integer, Double, String, Cars, Trucks, Cats, Dogs, etc... :)
The source code is in this github repository. https://github.com/khadija-ashraf/data-structure-algorithm.git
The Node is a generic class. That means this class can take different dataypes. A Node object has a generic type 'data' and two pointer 'prev' and 'next'. 'prev' points to the previous node, and 'next' pointer points to the next node in the queue.
package com.deque;
class Node<T>{
T data;
Node<T> prev;
Node<T> next;
public Node(T data){
this.data = data;
this.prev = null;
this.next = null;
}
}
MyDeque is the deque interface. It layout the deque behaviour.
package com.deque;
// A custom Double Ended Queue (Deque) implementation:
public interface MyDeque<T> {
public <T> T addHead(T data);
public <T> T addTail(T data);
public T getHead();
public T getTail();
public <T> boolean contains(T data);
public T removeHead();
public T removeTail();
public T peekHead();
public T peekTail();
public T pollHead();
public T pollTail();
public T pop();
public int size();
public void printDequq() ;
}
A deque is a queue in which we can insert and remove from both the front and rear end. Conversely, in an original queue we insert at the front and remove from the rear end.
In a deque, we have a head node and a tail node representing the start and the end of the queue respectively. We add remove from both front and rear ends from the head and tail referencing nodes.
class MyDequeImpl<T> implements MyDeque<T>{
private Node<T> head;
private Node<T> tail;
private int size;
public MyDequeImpl(){
head = null;
tail = null;
size = 0;
}
public <T> T addHead(T data) {
Node current = new Node<>(data);
if(head == null) {
head = current;
tail = current;
size++;
return data;
}
current.next = head;
head.prev = current;
head = current;
size++;
return data;
}
public <T> T addTail(T data) {
Node current = new Node<T>(data);
if(tail == null) {
head = current;
tail = current;
size++;
return data;
}
tail.next = current;
current.prev = tail;
tail = current;
size++;
return data;
}
public T getHead() {
if (head == null)
return null;
return head.data;
}
public T getTail() {
if(tail == null)
return null;
return tail.data;
}
public <T> boolean contains(T data) {
if(head == null)
return false;
if(head.data == data) {
return true;
}
if(tail.data == data) {
return true;
}
Node current = head;
while(current != null) {
if(current.data == data) {
return true;
}
current = current.next;
}
return false;
}
public T removeHead() {
if(head == null) {
return null;
}
T removedData = head.data;
head = head.next;
if(head == null) {
tail = null;
} else {
head.prev = null;
}
size--;
return removedData;
}
public T removeTail() {
if(tail == null) {
return null;
}
if(tail.prev == null) {
return null;
}
T removedData = tail.data;
tail = tail.prev;
if(tail == null) {
head = null;
} else {
tail.next = null;
}
size--;
return removedData;
}
public T peekHead() {
if(head == null)
return null;
return head.data;
}
public T peekTail() {
if(tail == null)
return null;
return tail.data;
}
public T pollHead() {
if(head == null)
return null;
T polledData = head.data;
head = head.next;
if(head == null) {
tail = null;
} else {
head.prev = null;
}
size--;
return polledData;
}
@Override
public T pollTail() {
if(tail == null) {
return null;
}
T pollData = tail.data;
tail = tail.prev;
if(tail == null)
head = null;
else {
tail.next = null;
}
size--;
return pollData;
}
public T pop() {
if(tail == null)
return null;
T popedData = tail.data;
tail = tail.prev;
if(tail == null)
head = null;
else {
tail.next = null;
}
size--;
return popedData;
}
public int size() {
return size;
}
public void printDequq() {
System.out.println("Printing the deque of size: "+size());
if (head == null) {
System.out.println("Dequq is empty.");
}
Node<T> current = head;
while(current != null) {
System.out.println(current.data);
current = current.next;
}
}
}
Below is some test insertions, removal, polling, peeking, and pop.
package com.deque;
public class TestDeque{
public static void main(String arg[]) {
MyDeque<String> deque = new MyDequeImpl<>();
deque.addHead("cat");
deque.printDequq();
deque.addHead("dog");
deque.printDequq();
deque.addHead("rabbit");
deque.printDequq();
deque.addHead("elephant");
deque.printDequq();
deque.addTail("squirrel");
deque.printDequq();
System.out.println("=============");
System.out.println(deque.getHead());
System.out.println(deque.getTail());
System.out.println(deque.contains("monkey"));
System.out.println(deque.contains("rabbit"));
System.out.println(deque.removeHead());
System.out.println(deque.removeTail());
System.out.println("=======");
System.out.println(deque.getHead());
System.out.println(deque.getTail());
System.out.println("=======");
System.out.println(deque.peekHead());
System.out.println(deque.peekTail());
System.out.println("========");
System.out.println(deque.pollHead());
System.out.println(deque.pollTail());
deque.printDequq();
System.out.println("========");
System.out.println(deque.pop());
deque.printDequq();
deque.addHead("birds");
deque.printDequq();
}
}