Homework SourseJAVA A doubleended queue is a list that allows the addition
**JAVA** A double-ended queue is a list that allows the addition and removal of items from either end. One end is arbitrarily called the front and other the rear, but the two ends behave identically. Specify, design and implement a class for a double-ended queue. Include operations to check if it is empty and to return the number of items in the list. For each end, include operations for adding and deleting items. Use doubly linked list for your implementation. Call your class Deque (pronounced \"deck\").
Solution
//package com.java2novice.ds.queue;
public class DequeDblLinkedListImpl<T> {
private LinkedNode<T> front;
private LinkedNode<T> rear;
public void insertFront(T item){
//add element at the beginning of the queue
System.out.println(\"adding at front: \"+item);
LinkedNode<T> nd = new LinkedNode<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);
LinkedNode<T> nd = new LinkedNode<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
LinkedNode<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 int size(){
if(front == null && rear ==null){
return 0;
}
//remove an item from the beginning of the queue
LinkedNode<T> tmpFront = front;
LinkedNode<T> tmpRear = rear;
int i=0;
while(tmpFront != rear)
{
i++;
tmpFront=tmpFront.getNext();
}
i++;
return i;
}
public void removeRear(){
if(rear == null){
System.out.println(\"Deque underflow!! unable to remove.\");
return;
}
//remove an item from the beginning of the queue
LinkedNode<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);
System.out.println(\"Size of the queue : \"+deque.size());
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 LinkedNode<T>{
private LinkedNode<T> prev;
private LinkedNode<T> next;
private T value;
public LinkedNode<T> getPrev() {
return prev;
}
public void setPrev(LinkedNode<T> prev) {
this.prev = prev;
}
public LinkedNode<T> getNext() {
return next;
}
public void setNext(LinkedNode<T> next) {
this.next = next;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
