Write functional code for solving the problem given below:

1.	Write functional code for solving the problem given below:
Answer» Return the result of a sequence of enqueue and dequeue actions without utilising a queue data structure. The FOLLOWING op are presented in the form of a linked list: A non-negative integer denotes "enqueue me." -1 denotes either of the following: Dequeue the current root and append it to the result if the queue is not empty. Append -1 to the result if the queue is empty. The end result should be returned as a linked list. As an auxiliary data structure, use two stacks. It is not permitted to use a queue. C ++ code SNIPPET which solves the given Data Structures and Algorithm problem is given below: Node* makeAnswerList(Node root, Node last, int VALUE){ if (root == NULL) { root = new Node(value); last = root; } else { Node node = new Node(value); last->link = node; last = last->link; } return last;}int dequeue(stack &stk1, stack &stk2){ if (stk1.empty() && stk2.empty()) { return -1; } // If the second stack is not empty, popping and returning from it. if (stk2.empty() == false) { int value = stk2.top(); stk2.pop(); return value; } / Otherwise we pop each and every element from the first stack and push into the second stack. / while (stk1.empty() == false) { stk2.push(stk1.top()); stk1.pop(); } // Lastly, we pop and return the root of the second stack. int value = stk2.top(); stk2.pop(); return value;}Node implementingQueue(Node* op){ stack stk1, stk2; Node root = NULL; Node last = NULL; while (op != NULL) { if (op->val >= 0) { stk1.push(op->val); } else { last = makeAnswerList(root, last, dequeue(stk1, stk2)); if (!root) { root = last; } } op = op->link; } return root;} In this question, we use two stacks to implement the queue data structure. As soon as a non-negative integer is found, we add it into the first stack and when we get a -1 in the input list, we perform the dequeue operation using the following criteria: If the second stack is not empty, we return its TOPMOST value and pop it. If the second stack is empty, we pop all the elements of the first stack, push them into the second stack and at the end, we pop and return the topmost element of the second stack. This way, the FIFO (First In First Out) property of a queue is preserved and we get our required answer list.

Answer»

Return the result of a sequence of enqueue and dequeue actions without utilising a queue data structure. The FOLLOWING op are presented in the form of a linked list:

A non-negative integer denotes "enqueue me."
-1 denotes either of the following:
- Dequeue the current root and append it to the result if the queue is not empty.
- Append -1 to the result if the queue is empty.

The end result should be returned as a linked list. As an auxiliary data structure, use two stacks. It is not permitted to use a queue.

C ++ code SNIPPET which solves the given Data Structures and Algorithm problem is given below:

Node* makeAnswerList(Node *root, Node *last, int VALUE){ if (root == NULL) { root = new Node(value); last = root; } else { Node *node = new Node(value); last->link = node; last = last->link; } return last;}int dequeue(stack &stk1, stack &stk2){ if (stk1.empty() && stk2.empty()) { return -1; } // If the second stack is not empty, popping and returning from it. if (stk2.empty() == false) { int value = stk2.top(); stk2.pop(); return value; } /* Otherwise we pop each and every element from the first stack and push into the second stack. */ while (stk1.empty() == false) { stk2.push(stk1.top()); stk1.pop(); } // Lastly, we pop and return the root of the second stack. int value = stk2.top(); stk2.pop(); return value;}Node* implementingQueue(Node* op){ stack stk1, stk2; Node *root = NULL; Node *last = NULL; while (op != NULL) { if (op->val >= 0) { stk1.push(op->val); } else { last = makeAnswerList(root, last, dequeue(stk1, stk2)); if (!root) { root = last; } } op = op->link; } return root;}

In this question, we use two stacks to implement the queue data structure. As soon as a non-negative integer is found, we add it into the first stack and when we get a -1 in the input list, we perform the dequeue operation using the following criteria:

If the second stack is not empty, we return its TOPMOST value and pop it.
If the second stack is empty, we pop all the elements of the first stack, push them into the second stack and at the end, we pop and return the topmost element of the second stack.

This way, the FIFO (First In First Out) property of a queue is preserved and we get our required answer list.

Write functional code for solving the problem given below:

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment