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


Industrial Training

We offers Placement Oriented Training on Java, Spring, JSF, Hibernate, PHP, AngularJS, Angular 4, PLSQL, Oracle BI Publisher etc. We also provides Online training, please mail us at hr@codesjava.com.

Development

We also provides the Development services for Website Development , Java Development, PHP Development, Android App Development etc. You can contact us on hr@codesjava.com.

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