#include <iostream> #include <stdlib.h> //srand, rand #include <time.h>//clock_t
ID: 3724707 • Letter: #
Question
#include <iostream>
#include <stdlib.h> //srand, rand
#include <time.h>//clock_t, clock, CLOCKS_PER_SEC
using namespace std;
// implementing a queue using Stack
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 Stack{
private:
Node* headPtr;
Node* tailPtr;
public:
Stack(){
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 push(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 pop(){
Node* lastNodePtr = tailPtr->getPrevNodePtr();
Node* prevNodePtr = 0;
int poppedData = -100000; //empty stack
if (lastNodePtr != 0){
prevNodePtr = lastNodePtr->getPrevNodePtr();
poppedData = lastNodePtr->getData();
}
else
return poppedData;
if (prevNodePtr != 0){
prevNodePtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(prevNodePtr);
}
else{
headPtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(0);
}
return poppedData;
}
int peek(){
Node* lastNodePtr = tailPtr->getPrevNodePtr();
if (lastNodePtr != 0)
return lastNodePtr->getData();
else
return -100000; // empty stack
}
void IterativePrint(){
Node* currentNodePtr = headPtr->getNextNodePtr();
while (currentNodePtr != 0){
cout << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getNextNodePtr();
}
cout << endl;
}
void ReversePrint(){
Node* currentNodePtr = tailPtr->getPrevNodePtr();
while (currentNodePtr != 0){
cout << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getPrevNodePtr();
}
cout << endl;
}
};
class Queue{
private:
Stack stack1;
Stack stack2;
public:
Queue(){}
void enqueue(int data){
// complete the code for the enqueue function
}
int dequeue(){
// complete the code for the dequeue function
}
bool isEmpty(){
// complete the code for the isEmpty function
}
};
int main(){
int queueSize;
cout << "Enter the number of elements you want to insert: ";
cin >> queueSize;
Queue queue; // Create an empty queue
srand(time(NULL));
int maxValue;
cout << "Enter the maximum value for an element: ";
cin >> maxValue;
for (int i = 0; i < queueSize; i++){
int value = 1 + rand() % maxValue;
queue.enqueue(value);
cout << value << " ";
}
cout << endl;
while (!queue.isEmpty()){
cout << queue.dequeue() << " ";
}
cout << endl;
return 0;
}
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 isEmptyO 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 (stack 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 stackl to store the elements of the queue (with the invariant that the topmost element of stackl is the element at the front of the queue and the bottommost element of stackl is the element at the end of the queue) and use stack2 as n auxiliary data structure to implement the enqueue function. Since the topmost element of stacks the element in the front of the queue, the dequeue function can be simply implemented as the result of a pop operation on stackl. 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 stack is empty or not If it is empty, simply push the 'data' to it and return from the enqueue function. If stackl is not empty to start with, then pop out all the elements of stackl and push each of them to stack2. After stackl gets empty, push the 'data' to it. Now, pop out all the elements of stack2 and push them back to stackl. As a result of this, the newly enqueued'data' will be in the bottom of stack Submission (through Canvas): (1) Write a pseudo code of the enqueue function implemented for this problem. Explain how the invariant that "the topmost element of stackl is the element at the front of the queue and the bottommost element of stackl is the element at the end of the queue is maintained with each enqueue and dequeue operation." (2) Discuss the theoretical time complexity of the enqueue and dequeue implementations (3) Include the complete C++ code of the (Doubly Linked List-based) Stack-based Queue implementation, including the main function (4) Show a screenshot of the execution of your implementation for a queue of size anywhere chosen fromm 5 to 10, with the maximum value of an element in the queue being 50Explanation / Answer
CODE :
#include<stdio.h>
#include<stdlib.h>
struct stack_node
{
int data;
struct stack_node *newval;
};
void push(struct stack_node** stack_top, int new_data);
int pop(struct stack_node** stack_top);
struct queue
{
struct stack_node *first_stack;
struct stack_node *second_stack;
};
void enQueue(struct queue *q, int val)
{
push(&q->first_stack, val);
}
int deQueue(struct queue *q)
{
int val;
if(q->first_stack == NULL && q->second_stack == NULL)
{
printf("Q is empty");
exit(0);
}
if(q->second_stack == NULL)
{
while(q->first_stack != NULL)
{
val = pop(&q->first_stack);
push(&q->second_stack, val);
}
}
val = pop(&q->second_stack);
return val;
}
void push(struct stack_node** stack_top, int new_data)
{
struct stack_node new_node = (struct stack_node) malloc(sizeof(struct stack_node));
if(new_node == NULL)
{
printf("Stack overflow ");
//getchar();
exit(0);
}
new_node->data = new_data;
new_node->newval = (*stack_top);
(*stack_top) = new_node;
}
int pop(struct stack_node** stack_top)
{
int result;
struct stack_node *top;
if(*stack_top == NULL)
{
printf("Stack overflow ");
//getchar();
exit(0);
}
else
{
top = *stack_top;
result = top->data;
*stack_top = top->newval;
free(top);
return result;
}
}
// Driver function
int main()
{
struct queue *q = (struct queue*)malloc(sizeof(struct queue));
q->first_stack = NULL;
q->second_stack = NULL;
enQueue(q, 4);
enQueue(q, 6);
enQueue(q, 100);
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.