JAVA EXAMPLE PROGRAMS

JAVA EXAMPLE PROGRAMS

Checkout for Promo Codes

Double-ended queue (Decue) implementation using Doubly linked list.


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. We have given more details on Deque in the previous example

In this page you will see Deque implementation by using doble linked list.


package com.java2novice.ds.queue;

public class DequeDblLinkedListImpl<T> {

	private Node<T> front;
	private Node<T> rear;
	
	public void insertFront(T item){
		//add element at the beginning of the queue
		System.out.println("adding 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){
		//add element at the end of the queue
		System.out.println("adding 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("Deque underflow!! unable to remove.");
			return;
		}
		//remove an item from the beginning of the queue
		Node<T> tmpFront = front.getNext();
		if(tmpFront != null) tmpFront.setPrev(null);
		if(tmpFront == null) rear = null;
		System.out.println("removed from front: "+front.getValue());
		front = tmpFront;
	}
	
	public void removeRear(){
		if(rear == null){
			System.out.println("Deque underflow!! unable to remove.");
			return;
		}
		//remove an item from the beginning of the queue
		Node<T> tmpRear = rear.getPrev();
		if(tmpRear != null) tmpRear.setNext(null);
		if(tmpRear == null) front = null;
		System.out.println("removed from rear: "+rear.getValue());
		rear = tmpRear;
	}
	
	public static void main(String a[]){
		DequeDblLinkedListImpl<Integer> deque = new DequeDblLinkedListImpl<Integer>();
		deque.insertFront(34);
		deque.insertFront(67);
		deque.insertFront(29);
		deque.insertFront(765);
		deque.removeFront();
		deque.removeFront();
		deque.removeFront();
		deque.insertRear(43);
		deque.insertRear(83);
		deque.insertRear(84);
		deque.insertRear(546);
		deque.insertRear(356);
		deque.removeRear();
		deque.removeRear();
		deque.removeRear();
		deque.removeRear();
		deque.removeFront();
		deque.removeFront();
		deque.removeFront();
	}
}

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;
	}
}

Output:
adding at front: 34
adding at front: 67
adding at front: 29
adding at front: 765
removed from front: 765
removed from front: 29
removed from front: 67
adding at rear: 43
adding at rear: 83
adding at rear: 84
adding at rear: 546
adding at rear: 356
removed from rear: 356
removed from rear: 546
removed from rear: 84
removed from rear: 83
removed from front: 34
removed from front: 43
Deque underflow!! unable to remove.
<< 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
Knowledge Centre
doPost Vs doGet methods
doGet() method is used to get information, while doPost() method is used for posting information. doGet() requests can't send large amount of information and is limited to 240-255 characters. However, doPost()requests passes all of its data, of unlimited length. A doGet() request is appended to the request URL in a query string and this allows the exchange is visible to the client, whereas a doPost() request passes directly over the socket connection as part of its HTTP request body and the exchange are invisible to the client.
Famous Quotations
The greatest obstacle to discovery is not ignorance; it is the illusion of knowledge.
-- Daniel J. Boorstin

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 © 2020 by Nataraja Gootooru. All Rights Reserved.