CodesJava

Easy learning with example program codes

Java deque implementation using doubly linked list


A queue is an ADT – Abstract Data Type or a linear data structure. It is a FIFO data structure because element inserted first will be removed first. FIFO stands for First-in-first-out. Queue use one end to insert data which is called REAR or tail and other end to remove the data which is called FRONT or head.

Queue operations

  • enqueue(): Insert an item to the queue.
  • dequeue(): Remove an item from the queue.
  • peek(): Get the top data element of the queue, without removing it.
  • isFull(): Check if queue is full.
  • isEmpty(): Check if queue is empty.

Queue states

  • Overflow state: A queue is in overflow state if it does not contain enough space to accept an entity to be inserted.
  • Underflow state: A queue is in underflow state if we want to operate stack with dequeue operation and the queue is empty.

Deque Queue

Double-ended queue is an abstract data type. A deque represents a linear collection of elements that support insertion, retrieval and removal of elements at both ends. Dequeue, often abbreviated to deque.

Example

package com.codesjava;
 
class Node<T>{    
    private Node<T> prev;
    private Node<T> next;
    private T value;
 
    public Node<T> getPrev() {
        return prev;
    }
    public void setPrev(Node<T> prev) {
        this.prev = prev;
    }
    public Node<T> getNext() {
        return next;
    }
    public void setNext(Node<T> next) {
        this.next = next;
    }
    public T getValue() {
        return value;
    }
    public void setValue(T value) {
        this.value = value;
    }
}
 
public class Test<T>  {
    private Node<T> front;
    private Node<T> rear;
 
    public void insertFront(T item){
        System.out.println("Adding element at front: "+item);
        Node<T> nd = new Node<T>();
        nd.setValue(item);
        nd.setNext(front);
        if(front != null) front.setPrev(nd);
        if(front == null) rear = nd;
        front = nd;
    }
 
    public void insertRear(T item){
        System.out.println("Adding element at rear: "+item);
        Node<T> nd = new Node<T>();
        nd.setValue(item);
        nd.setPrev(rear);
        if(rear != null) rear.setNext(nd);
        if(rear == null) front = nd;
 
        rear = nd;
    }
 
    public void removeFront(){
        if(front == null){
            System.out.println("Underflow state.");
            return;
        }
        Node<T> tmpFront = front.getNext();
        if(tmpFront != null) tmpFront.setPrev(null);
        if(tmpFront == null) rear = null;
        System.out.println("Remove element from front: "+front.getValue());
        front = tmpFront;
    }
 
    public void removeRear(){
        if(rear == null){
            System.out.println("Underflow state.");
            return;
        }
        Node<T> tmpRear = rear.getPrev();
        if(tmpRear != null) tmpRear.setNext(null);
        if(tmpRear == null) front = null;
        System.out.println("Removed element from rear: "+rear.getValue());
        rear = tmpRear;
    }
 
	public static void main(String args[]){
		try {
			Test<Integer> deque = new Test<Integer>();
			deque.insertFront(134);
			deque.insertFront(14);
			deque.insertFront(13);
			deque.removeFront();
			deque.insertRear(455);
			deque.removeFront();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Output

Adding element at front: 134
Adding element at front: 14
Adding element at front: 13
Remove element from front: 13
Adding element at rear: 455
Remove element from front: 14
Sign Up/ Sign In
Ask a Question


Copyright © 2018 CodesJava DMCA.com Protection Status SiteMap Reference: Java Wiki