CodesJava

Easy learning with example program codes

Java deque implementation


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.

This general data class has some possible sub-types:

  • input-restricted deque: It is one where deletion can be made from both ends, but insertion can be made at one end only.
  • output-restricted deque: It is one where insertion can be made at both ends, but deletion can be made from one end only.

Example

package com.codesjava;
 
import java.util.ArrayList;
import java.util.List;
 
public class Test {
    private List<Integer> deque = new ArrayList<Integer>();
 
    public void insertFront(int item){
        System.out.println("Adding element at front: "+item);
        deque.add(0,item);
        System.out.println(deque);
    }
 
    public void insertRear(int item){
        System.out.println("Adding element at rear: "+item);
        deque.add(item);
        System.out.println(deque);
    }
 
    public void removeFront(){
        if(deque.isEmpty()){
            System.out.println("Underflow state.");
            return;
        }
        int rem = deque.remove(0);
        System.out.println("Remove element from front: "+rem);
        System.out.println(deque);
    }
 
    public void removeRear(){
        if(deque.isEmpty()){
            System.out.println("Underflow state.");
            return;
        }
        int rem = deque.remove(deque.size()-1);
        System.out.println("Removed element from front: "+rem);
        System.out.println(deque);
    }
 
    public int peakFront(){
        int item = deque.get(0);
        System.out.println("Element at first: "+item);
        return item;
    }
 
    public int peakRear(){
        int item = deque.get(deque.size()-1);
        System.out.println("Element at rear: "+item);
        return item;
    }
 
	public static void main(String args[]){
		try {
			Test deque = new Test();
			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
[134]
Adding element at front: 14
[14, 134]
Adding element at front: 13
[13, 14, 134]
Remove element from front: 13
[14, 134]
Adding element at rear: 455
[14, 134, 455]
Remove element from front: 14
[134, 455]


Copyright © 2018 CodesJava DMCA.com Protection Status SiteMap