#include

#include //srand, rand

#include //clock_t, clock, CLOCKS_PER_SEC

using namespace std;

// implementing a doubly linked list-based queue

class Node{

private:

int data;

Node* nextNodePtr;

Node* prevNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

void setPrevNodePtr(Node* nodePtr){

prevNodePtr = nodePtr;

}

Node* getPrevNodePtr(){

return prevNodePtr;

}

};

class Queue{

private:

Node* headPtr;

Node* tailPtr;

public:

Queue(){

headPtr = new Node();

tailPtr = new Node();

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

Node* getTailPtr(){

return tailPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void enqueue(int data){

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

Node* lastNodePtr = tailPtr->getPrevNodePtr();

if (lastNodePtr == 0){

headPtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(0);

}

else{

lastNodePtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(lastNodePtr);

}

tailPtr->setPrevNodePtr(newNodePtr);

}

int dequeue(){

Node* firstNodePtr = headPtr->getNextNodePtr();

Node* nextNodePtr = 0;

int poppedData = -100000; //empty queue

if (firstNodePtr != 0){

nextNodePtr = firstNodePtr->getNextNodePtr();

poppedData = firstNodePtr->getData();

}

else

return poppedData;

if (nextNodePtr != 0){

nextNodePtr->setPrevNodePtr(0);

headPtr->setNextNodePtr(nextNodePtr);

}

else{

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

return poppedData;

}

int peek(){

Node* firstNodePtr = headPtr->getNextNodePtr();

if (firstNodePtr != 0)

return firstNodePtr->getData();

else

return -100000; //empty queue

}

int getQueueLength(){

int length = 0;

//Node* headPtr = queue.getHeadPtr();

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

length++;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return length;

}

};

class Stack{

private:

Queue queue;

public:

Stack(){}

void push(int x){

// Implement the push function in such a way that integer x

// is at the top of the stack (i.e., front of the queue object)

}

bool isEmpty(){

return queue.isEmpty();

}

int pop(){

return queue.dequeue();

}

int peek(){

return queue.peek();

}

};

int main(){

srand(time(NULL));

int numElements;

cout

cin >> numElements;

int maxValue;

cout

cin >> maxValue;

Stack stack;

cout

for (int i = 0; i

int value = 1 + rand() % maxValue;

stack.push(value);

cout

}

cout

cout

while (!stack.isEmpty()){

cout

}

cout

system("pause");

return 0;

}

Q1 - 20 pts) For this question, you will implement an integer-based Stack ADT using a Queue (which is in turn implemented using a doubly linked list). You are provided a C++ file that contains the complete implementations of the Class Queue (implemented as a doubly linked list), Class Node (as part of the doubly linked list) and a skeleton of the Class Stack as well as a complete main function. The Stack class includes a Queue object (queue) as the member variable. The front of the queue is to be considered as the top of the Stack. Accordingly, the pop and peek functions of the Stack can be implemented by simply calling the dequeue function on the queue object. Likewise, the isEmpty() function for the Stack class can be implemented by simply calling the isEmpty() function on the queue object. The code for the pop(), peek() and isEmpty() functions for the Stack class are already provided for you. Your task in this question is to implement the push(int) function of the Stack class using ONLY the enqueue, dequeue and getQueueLength functions that can be called on the member variable (object): queue. You will get a ZERO if you implement the push function of the Stack class by directly accessing the underlying doubly linked list or using any other functions. The main function has already been implemented with the code that can push a certain number (numElements) of randomly generated integers in the range [1...maxValue]; the values for numElements and max Value are to be input by the user. The main function has a loop that will push the randomly generated integers to the stack (an object of class Stack) and then a loop to pop out each of these integers from the stack and print their value. You do not need to make any changes to the main function. What to submit: 1) The complete .cpp file containing the class Stack, class Queue, class Node and the main function. 2) A screenshot of the output for numElements = 10 and maxValue = 50