A double-ended queue or deque is like a stack or a queue but supports adding and
ID: 3913918 • Letter: A
Question
A double-ended queue or deque is like a stack or a queue but supports adding and removing items at both ends. A deque stores a collection of items and support the following API ublic class dequesItem> implement Iterable deque0 isEmpty0 size pushLeft(Item item)//add an item to the left end pushRight(Item item)//add an item to the right end popLeft0 popRight0 //create an empty deque //is the deque empty? //number of items in the deque boolean int void void Item Item void void void //remove and return an item from left end /remove and return an item from right end //remove all items /display the items in the deque left to right //display the items in the deque right to left clear0 printo printRevO API for generic double-ended queue 1. Write a class Deque that uses a doubly-linked list to implement this API. You need to implement all methods of the doubly-linked list class and the deque class Write a driver program for this class. The driver program is a menu-driven For each method in the deque class (except the constructor), there will be a corresponding choice in the menu. 2. program Deliverables A softcopy and hardcopy of the project are both required and include the following. a. A single Word file containing the following i. Complete code listings for all classes required in addition to the main0 function Screen shots of the output. This should include normal cases as well as invalid input caseslike popping an empty deque ii.Explanation / Answer
import java.io.*;
class Node
{
public int data;
public Node next;
public Node previous;
public Node(int x)
{
data=x;
}
public void dispnode()
{
System.out.print(data);
}
}
class Dblst
{
private Node first;
private Node last;
public Dblst()//Creating the doubly linked list
{
first=null;
last=null;
}
public void PushLeft(int x)//push items at start of the queue
{
Node newNode=new Node(x);//creating the new node
newNode.next=null;//setting the next pointer to null
if(isEmpty())//checks if the list is empty if yes then the created will
be the last node
last=newNode;
else
first.previous=newNode;//if the above condition fails then the
previous ptr of the created node is made to point to the newly created node and it also made as “first node”
newNode.next=first;
first=newNode;
}
public void PusRight(int x)//insert at the end or at the rear
{
Node newNode=new Node(x);//create space for the node
newNode.next=null;//set next ptr to null
if(isEmpty())
first=newNode;
else
{
last.next=newNode;//the next ptr of last node in the queue is fetched
and its next made to point to the newly created node
newNode.previous=last;
}
last=newNode; // the newly created is made the last node
}
public int popLeft()//remove the first or top element of the queue
{
int t=first.data;//get the first node data
if(first.next==null)//if the node is the only node of the queue
last=null;
else
first.next.previous=null; //set its next,previous ptr to null as we will
have to free it
first=first.next;
return t;
}
public int popRight()//remove the last or rear element of the queue
{
int t=last.data;
if(first.next==null)
first=null;
else
last.previous.next=null;
last=last.previous;
return t;
}
public boolean isEmpty()//Checks the queue emptyness
{
return(first==null);
}
public void printFirst()//return queue elements starting from the head position
{
Node current=first;//create a new node called current and point to the
First
while(current!=null)
{
current.dispnode();
current=current.next;
}
}
public void printbck()//print from the rear elements
{
Node current=last;
while(current!=null)
{
current.dispnode();
current=current.previous;
}
}
}
class Dq
{
private Dblst dbl;
public Dq()
{
dbl=new Dblst();
}
public void insL(int x)
{
dbl.PushLeft(x);
System.out.print("Inserted at left ");
}
public void insR(int x)
{
dbl.PusRight(x);
System.out.print("Inserted at right ");
}
public int delL()
{
return dbl.popLeft();
System.out.print("Deleted from left ");
}
public int delr()
{
return dbl.popRight();
System.out.print("Inserted from Right ");
}
public boolean qempty()
{
return dbl.isEmpty();
}
public void dsipfront()
{
dbl.printFirst();
}
public void dsipbck()
{
dbl.printbck();
}
}
class dqmain
{
public static void main(String args[])throws IOException
{
String ch="y";
DataInputStream ip=new DataInputStream(System.in);
int n,d;
Dq q=new Dq();//creating a dq
while(ch.equals("y"))
{
System.out.println("1.PushLeft");
System.out.println("2.PushRight");
System.out.println("3.Pop Left");
System.out.println("4.Pop Right");
System.out.println("5.Print First");
System.out.println("6.Print from last");
System.out.println("your choice ");
n=Integer.parseInt(ip.readLine());
switch(n)
{
case 1: System.out.println("Enter the data ");
d=Integer.parseInt(ip.readLine());
q.insL(d);
break;
case 2: System.out.println("Enter the data ");
d=Integer.parseInt(ip.readLine());
q.insR(d);
break;
case 3: if(q.qempty())
System.out.print("Deque is Empty ");
else
{
d=q.delL();
System.out.print("Deleted data:- "+d);
}
break;
case 4: if(q.qempty())
System.out.print("Deque is Empty ");
else
{
d=q.delr();
System.out.print("Deleted data:- "+d);
}
break;
case 5: if(q.qempty())
System.out.print("Deque is Empty ");
else
{
System.out.print("Datas in Deque From Front:- ");
q.dsipfront();
}
break;
case 6: if(q.qempty())
System.out.print("Deque is Empty ");
else
{
System.out.print("Data in Deque From Rear:- ");
q.dsipbck();
}
break;
default: System.out.print("Invalid,choose correct opton");
}
System.out.print("Enter y to continue ");
ch=ip.readLine();
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.