A double-ended queue is a list that allows the addition and removal of items fro

Question

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 the other the rear, but 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. Implement the double-ended queue as a doubly linked list. Call your class Deque ( which is pronounced "deck"). By the way, please present it as a Java language code.

Please provide the code and the output in "command box" or applet form. Thank you.

Explanation / Answer

/*
* Java Program to Implement Double Ended Queue
*/

import java.util.*;

/* Class Node */
class Node
{
protected int data;
protected Node link;

/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}

/* Class Dequeue */
class Dequeue
{
private Node front, rear;
private int size;

/* Constructor */
public Dequeue()
{
front = null;
rear = null;
size = 0;
}
/* Function to check if queue is empty */
public boolean isEmpty()
{
return front == null;
}
/* Function to get the size of the queue */
public int getSize()
{
return size;
}
/* Clear dequeue */
public void clear()
{
front = null;
rear = null;
size = 0;
}
/* Function to insert an element at begining */
public void insertAtFront(int val)
{
Node nptr = new Node(val, null);
size++ ;
if (front == null)
{
front = nptr;
rear = front;
}
else
{
nptr.setLink(front);
front = nptr;
}
}
/* Function to insert an element at end */
public void insertAtRear(int val)
{
Node nptr = new Node(val,null);
size++ ;
if (rear == null)
{
rear = nptr;
front = rear;
}
else
{
rear.setLink(nptr);
rear = nptr;
}
}
/* Function to remove front element from the queue */
public int removeAtFront()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
Node ptr = front;
front = ptr.getLink();

if (front == null)
rear = null;
size-- ;

return ptr.getData();
}
/* Function to remove rear element from the queue */
public int removeAtRear()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
int ele = rear.getData();
Node s = front;
Node t = front;
while (s != rear)
{
t = s;
s = s.getLink();
}
rear = t;
rear.setLink(null);
size --;

return ele;
}
/* Function to check the front element of the queue */
public int peekAtFront()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return front.getData();
}
/* Function to check the front element of the queue */
public int peekAtRear()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return rear.getData();
}
/* Function to display the status of the queue */
public void display()
{
System.out.print(" Dequeue = ");
if (size == 0)
{
System.out.print("Empty ");
return ;
}
Node ptr = front;
while (ptr != rear.getLink() )
{
System.out.print(ptr.getData()+" ");
ptr = ptr.getLink();
}
System.out.println();
}
}

/* Class DoubleEndedQueueTest */
public class DoubleEndedQueueTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class Dequeue */   
Dequeue dq = new Dequeue();
/* Perform Dequeue Operations */
System.out.println("Dequeue Test ");
char ch;
do
{
System.out.println(" Dequeue Operations");
System.out.println("1. insert at front");
System.out.println("2. insert at rear");
System.out.println("3. delete at front");
System.out.println("4. delete at rear");
System.out.println("5. peek at front");
System.out.println("6. peek at rear");
System.out.println("7. size");
System.out.println("8. check empty");
System.out.println("9. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
dq.insertAtFront( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
dq.insertAtRear( scan.nextInt() );
break;   
case 3 :
try
{
System.out.println("Removed Element = "+ dq.removeAtFront());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 4 :
try
{
System.out.println("Removed Element = "+ dq.removeAtRear());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;   
case 5 :
try
{
System.out.println("Peek Element = "+ dq.peekAtFront());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 6 :
try
{
System.out.println("Peek Element = "+ dq.peekAtRear());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;   
case 7 :
System.out.println("Size = "+ dq.getSize());
break;
case 8 :
System.out.println("Empty status = "+ dq.isEmpty());
break;
case 9 :
System.out.println(" Dequeue Cleared ");
dq.clear();
break;   
default :
System.out.println("Wrong Entry ");
break;
}
/* display dequeue */
dq.display();

System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.