JAVA EXAMPLE PROGRAMS

JAVA EXAMPLE PROGRAMS

Publish Your Article Here

Double-ended queue (Decue) Implementation.


A double-ended queue (dequeue or deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front or rear. Deque differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types:

1) An input-restricted deque is one where deletion can be made from both ends, but insertion can be made at one end only.
2) An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.

Insertion Sort

You can use Deque as a stack by making insertion and deletion at the same side. Also you can use Deque as queue by making insetting elements at one end and removing elements at other end.

The common way of deque implementations are by using dynamic array or doubly linked list. Here this example shows the basic implementation of deque using a list, which is basically a dynamic array.

The complexity of Deque operations is O(1), when we not consider overhead of allocation/deallocation of dynamic array size.


package com.java2novice.ds.queue;

import java.util.ArrayList;
import java.util.List;

public class DoubleEndedQueueImpl {

	private List<Integer> deque = new ArrayList<Integer>();
	
	public void insertFront(int item){
		//add element at the beginning of the queue
		System.out.println("adding at front: "+item);
		deque.add(0,item);
		System.out.println(deque);
	}
	
	public void insertRear(int item){
		//add element at the end of the queue
		System.out.println("adding at rear: "+item);
		deque.add(item);
		System.out.println(deque);
	}
	
	public void removeFront(){
		if(deque.isEmpty()){
			System.out.println("Deque underflow!! unable to remove.");
			return;
		}
		//remove an item from the beginning of the queue
		int rem = deque.remove(0);
		System.out.println("removed from front: "+rem);
		System.out.println(deque);
	}
	
	public void removeRear(){
		if(deque.isEmpty()){
			System.out.println("Deque underflow!! unable to remove.");
			return;
		}
		//remove an item from the beginning of the queue
		int rem = deque.remove(deque.size()-1);
		System.out.println("removed from front: "+rem);
		System.out.println(deque);
	}
	
	public int peakFront(){
		//gets the element from the front without removing it
		int item = deque.get(0);
		System.out.println("Element at first: "+item);
		return item;
	}
	
	public int peakRear(){
		//gets the element from the rear without removing it
		int item = deque.get(deque.size()-1);
		System.out.println("Element at rear: "+item);
		return item;
	}
	
	public static void main(String a[]){
		
		DoubleEndedQueueImpl deq = new DoubleEndedQueueImpl();
		deq.insertFront(34);
		deq.insertRear(45);
		deq.removeFront();
		deq.removeFront();
		deq.removeFront();
		deq.insertFront(21);
		deq.insertFront(98);
		deq.insertRear(5);
		deq.insertFront(43);
		deq.removeRear();
	}
}

Output:
adding at front: 34
[34]
adding at rear: 45
[34, 45]
removed from front: 34
[45]
removed from front: 45
[]
Deque underflow!! unable to remove.
adding at front: 21
[21]
adding at front: 98
[98, 21]
adding at rear: 5
[98, 21, 5]
adding at front: 43
[43, 98, 21, 5]
removed from front: 5
[43, 98, 21]
<< Previous Program | Next Program >>

List of Queue Data Structure Examples

  1. Queue introduction & array based implementation
  2. Dynamic Queue implementation using arrays
  3. Double-ended queue (Decue) Implementation
  4. Double-ended queue (Decue) implementation using Doubly linked list
  5. Priority Queue introduction and Java implementation
Java2Novice - YouTube Channel
  1. Python Tutorial for Beginners
Knowledge Centre
Interface and its usage
Interface is similar to a class which may contain method's signature only but not bodies and it is a formal set of method and constant declarations that must be defined by the class that implements it. Interfaces are useful for declaring methods that one or more classes are expected to implement, capturing similarities between unrelated classes without forcing a class relationship and determining an object's programming interface without revealing the actual body of the class.
Famous Quotations
Insanity: doing the same thing over and over again and expecting different results.
-- Albert Einstein

About Author

I'm Nataraja Gootooru, programmer by profession and passionate about technologies. All examples given here are as simple as possible to help beginners. The source code is compiled and tested in my dev environment.

If you come across any mistakes or bugs, please email me to [email protected].

Most Visited Pages

Other Interesting Sites

Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle.
Privacy Policy | Copyright © 2019 by Nataraja Gootooru. All Rights Reserved.