This question is written in java. You are not allowed to use Java API classes fo
ID: 3788517 • Letter: T
Question
This question is written in java. You are not allowed to use Java API classes for queues, stacks, arrays, arraylists and linkedlists. You have to write your own implementations for them. The problem needs to work like the example below.
A deque is a data structure consisting of a list of items, on which the following operations are possible:
push(x): Insert item x on the front end of the deque.
pop(): Remove the front item from the deque and return it.
inject(x): Insert item x on the rear end of the deque.
eject(): Remove the rear item from the deque and return it.
Write a program in Java for the deque data structure. All the above operations should take O(1) time per operation. Your program should create a menu-driven interface as shown in the example below.
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 1
Enter element to push: 5
Current Deque: 5
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 3
Enter element to inject: 79
Current Deque: 5 79
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 3
Enter element to inject: 23
Current Deque: 5 79 23
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 1
Enter element to push: 16
Current Deque: 16 5 79 23
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 1
Enter element to push: 59
Current Deque: 59 16 5 79 23
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 2
Current Deque: 16 5 79 23
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 4
Current Deque: 16 5 79
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 4
Current Deque: 16 5
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 2
Current Deque: 5
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 4
Current Deque:
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 2
Deque is empty, nothing to pop.
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 4
Deque is empty, nothing to eject.
Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit): 5
Bye!
Explanation / Answer
package any;
/*
* Java Program to Implement Double Ended Queue
*/
import java.util.*;
class Node{
protected int data;
protected Node link;
public Node(){
link = null;
data = 0;
}
public Node(int d,Node n){
data = d;
link = n;
}
public void setLink(Node n){
link = n;
}
public void setData(int d){
data = d;
}
public Node getLink(){
return link;
}
public int getData(){
return data;
}
}
/* Class Dequeue */
class Dequeue
{
private Node front, rear;
private int size;
public Dequeue()
{
front = null;
rear = null;
size = 0;
}
public boolean isEmpty(){
return front == null;
}
public void push(int val){
Node nptr = new Node(val, null);
size++ ;
if (front == null){
front = nptr;
rear = front;
}else{
nptr.setLink(front);
front = nptr;
}
}
public void inject(int val){
Node nptr = new Node(val,null);
size++ ;
if (rear == null){
rear = nptr;
front = rear;
}else{
rear.setLink(nptr);
rear = nptr;
}
}
public int pop(){
if (isEmpty())
throw new NoSuchElementException("Deque is empty, nothing to pop");
Node ptr = front;
front = ptr.getLink();
if (front == null)
rear = null;
size-- ;
return ptr.getData();
}
public int eject(){
if (isEmpty())
throw new NoSuchElementException("Deque is empty, nothing to eject");
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;
}
public void printQueue()
{
System.out.print("Current Deque : ");
if (size == 0){
System.out.println();
return ;
}
Node ptr = front;
while (ptr != rear.getLink()){
System.out.print(ptr.getData()+" ");
ptr = ptr.getLink();
}
System.out.println();
}
}
public class Deque{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
Dequeue queue = new Dequeue(); //Creating object of class Dequeue
while (true){
/* Display Operations */
System.out.println("Enter operation for deque (1: Push, 2: Pop, 3: Inject, 4: Eject, 5: Quit):");
int input = scan.nextInt();
switch (input){
case 1 :
System.out.println("Enter element to push");
queue.push(scan.nextInt());
break;
case 2 :
try{
queue.pop();
}catch (NoSuchElementException e){
System.out.println(e.getMessage());
}
break;
case 3 :
System.out.println("Enter element to inject");
queue.inject(scan.nextInt());
break;
case 4 :
try{
queue.eject();
}catch (NoSuchElementException e){
System.out.println(e.getMessage());
}
break;
case 5 :
System.exit(0);
break;
default :
System.out.println("Wrong Input ");
break;
}
queue.printQueue();
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.