You are given the code skeleton for implementing a queue using Stack (that is in turn implemented using a Doubly Linked List).

Complete the code for the enqueue(), dequeue() and isEmpty() functions of the Queue class. The code for the main function is also given to you. After you implement the above three functions, you can run your main function and capture screenshot. The queue size can range from 5 to 10 and the maximum value for an element in the queue can be 50.

As you can notice, there are two Stacks (stack1 and stack2) declared as private member variables in the Queue class. You need to use these two Stacks for implementing the functionalities of a queue. I suggest the following design (you are free to choose your own design; provide a detailed explanation in your project report if your design is different from mine).

Use stack1 to store the elements of the queue (with the invariant that the topmost element of stack1 is the element at the front of the queue and the bottommost element of stack1 is the element at the end of the queue) and use stack2 as an auxiliary data structure to implement the enqueue function. Since the topmost element of stack1 is the element in the front of the queue, the dequeue function can be simply implemented as the result of a pop operation on stack1. It is the enqueue function that needs to be thought out in greater detail and implemented. I suggest the following idea for enqueue of an integer 'data':

First check if stack1 is empty or not. If it is empty, simply push the 'data' to it and return from the enqueue function. If stack1 is not empty to start with, then pop out all the elements of stack1 and push each of them to stack2. After stack1 gets empty, push the 'data' to it. Now, pop out all the elements of stack2 and push them back to stack1. As a result of this, the newly enqueued 'data' will be in the bottom of stack1.

The code is given is:

import java.util.*;

// implementing a queue using Stack

class Node{

private int data; private Node nextNodePtr; private Node prevNodePtr;

public Node(){}

public void setData(int d){ data = d; }

public int getData(){ return data; }

public void setNextNodePtr(Node nodePtr){ nextNodePtr = nodePtr; }

public Node getNextNodePtr(){ return nextNodePtr; }

public void setPrevNodePtr(Node nodePtr){ prevNodePtr = nodePtr; }

public Node getPrevNodePtr(){ return prevNodePtr; }

}

class Stack{

private Node headPtr; private Node tailPtr;

public Stack(){ headPtr = new Node(); tailPtr = new Node(); headPtr.setNextNodePtr(null); tailPtr.setPrevNodePtr(null); }

public Node getHeadPtr(){ return headPtr; }

public Node getTailPtr(){ return tailPtr; }

public boolean isEmpty(){

if (headPtr.getNextNodePtr() == null) return true;

return false; }

public void push(int data){

Node newNodePtr = new Node(); newNodePtr.setData(data); newNodePtr.setNextNodePtr(null);

Node lastNodePtr = tailPtr.getPrevNodePtr();

if (lastNodePtr == null){

headPtr.setNextNodePtr(newNodePtr); newNodePtr.setPrevNodePtr(null);

} else{

lastNodePtr.setNextNodePtr(newNodePtr); newNodePtr.setPrevNodePtr(lastNodePtr);

}

tailPtr.setPrevNodePtr(newNodePtr);

}

public int pop(){

Node lastNodePtr = tailPtr.getPrevNodePtr(); Node prevNodePtr = null;

int poppedData = -100000; //empty stack

if (lastNodePtr != null){ prevNodePtr = lastNodePtr.getPrevNodePtr(); poppedData = lastNodePtr.getData(); } else return poppedData;

if (prevNodePtr != null){ prevNodePtr.setNextNodePtr(null); tailPtr.setPrevNodePtr(prevNodePtr); } else{ headPtr.setNextNodePtr(null); tailPtr.setPrevNodePtr(null); }

return poppedData;

}

public int peek(){

Node lastNodePtr = tailPtr.getPrevNodePtr();

if (lastNodePtr != null) return lastNodePtr.getData(); else return -100000; // empty stack

}

public void IterativePrint(){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){ System.out.print(currentNodePtr.getData() + " "); currentNodePtr = currentNodePtr.getNextNodePtr(); }

System.out.println();

}

public void ReversePrint(){

Node currentNodePtr = tailPtr.getPrevNodePtr();

while (currentNodePtr != null){

System.out.print(currentNodePtr.getData() + " "); currentNodePtr = currentNodePtr.getPrevNodePtr(); }

System.out.println(); }

}

class Queue{

private Stack stack1; private Stack stack2;

public Queue(){ stack1 = new Stack(); stack2 = new Stack(); }

public void enqueue(int data){

// complete the code for the enqueue function

}

public int dequeue(){

// complete the code for the dequeue function

}

public boolean isEmpty(){

// complete the code for the isEmpty function

}

}

class DoublyLinkedList_Stack_Queue{

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int queueSize; System.out.print("Enter the number of elements you want to insert: "); queueSize = input.nextInt();

int maxValue; System.out.print("Enter the maximum value for an element: "); maxValue = input.nextInt();

Random randGen = new Random(System.currentTimeMillis());

Queue queue = new Queue();

for (int i = 0; i < queueSize; i++){ int value = randGen.nextInt(maxValue); queue.enqueue(value); System.out.print(value + " "); }

System.out.println();

while (!queue.isEmpty()){

System.out.print(queue.dequeue() + " "); }

System.out.println();

}

}