PLEASE CODE IN C++ AND MAKE IT COPYABLE! In this project, you will design and implement...
PLEASE CODE IN C++ AND MAKE IT COPYABLE!
In this project, you will design and implement an algorithm to determine the next greater element of an
element in an array in Θ(n) time, where 'n' is the number of elements in the array. You could use the Stack
ADT for this purpose.
The next greater element (NGE) for an element at index i in an array A is the element that occurs at index
j (i < j) such that A[i] < A[j] and A[i] ≥ A[k] for all k Î[i+1..., j-1]. That is, index j (j > i) is the first index
for which A[j] > A[i]. If no such index j exists for an element at index i, then the NGE for the element
A[i] is considered to be -1.
For example: if an array is {1, 15, 26, 5, 20, 17, 36, 28}, then the next greater element (NGE) of the
elements in the array are as follows:
1 15
15 26
26 36
5 20
20 36
17 36
36 -1
28 -1
Note: Your code need not print the elements and their NGE values in the same order of the appearance of
the elements in the array. An out of order print is also acceptable as long as the correct NGE for an
element is printed out. For example, the following out of order print for the above array is also acceptable.
1 15
15 26
5 20
17 36
20 36
26 36
28 -1
36 -1
You are given the doubly linked list-based implementation code for Stack along with this project
description. Note that the main function in the code given to you already has the code snippet to generate
an array of random elements. You just extend the main function to implement the algorithm.
#include <iostream>
#include <stdlib.h> //srand, rand
#include <time.h>//clock_t, clock, CLOCKS_PER_SEC
using namespace std;
// Doubly Linked List-based Implementation of 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;
}
};
int main(){
int arraySize;
cout << "Enter the number of elements you want
to analyze: ";
cin >> arraySize;
Stack stack; // Create an empty stack
srand(time(NULL));
int maxValue;
cout << "Enter the maximum value for an element:
";
cin >> maxValue;
int array[arraySize];
for (int i = 0; i < arraySize; i++){
int value = rand() %
maxValue;
cout << value << "
";
array[i] = value;
}
cout << endl;
// Implement a theta(n) algorithm using Stack to find
the next greater element of each
// element in the array and print them
return 0;
}
Homework Answers
#include <iostream>
#include <stdlib.h> //srand, rand
#include <time.h>//clock_t, clock, CLOCKS_PER_SEC
using namespace std;
// Doubly Linked List-based Implementation of 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;
}
};
int main(){
int arraySize;
cout << "Enter the number of elements you want to analyze:
";
cin >> arraySize;
Stack stack; // Create an empty stack
srand(time(NULL));
int maxValue;
cout << "Enter the maximum value for an element: ";
cin >> maxValue;
int array[arraySize];
for (int i = 0; i < arraySize; i++){
int value = rand() % maxValue;
cout << value << " ";
array[i] = value;
}
cout << endl;
// Implement a theta(n) algorithm using Stack to find the next
greater element of each
// element in the array and print them
int i = 0;
int curr, next;
stack.push(array[0]);
for (i=1; i<arraySize; i++)
{
next = array[i];
if (!stack.isEmpty())
{
curr = stack.pop();
while (curr < next)
{
printf("%d -- %d\n", curr, next);
if(stack.isEmpty())
break;
curr = stack.pop();
}
if (curr > next)
stack.push(curr);
}
stack.push(next);
}
while (!stack.isEmpty())
{
curr = stack.pop();
next = -1;
printf("%d -- %d\n", curr, next);
}
return 0;
}
=========================================
See Output
Thanks
Add Answer to:
PLEASE CODE IN C++ AND MAKE IT COPYABLE!
In this project, you will design and implement...
#include <iostream> #include <string> #include <cstring> using namespace std; class Node{ private: ...
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class Node{
private:
int data;
Node* nextNodePtr;
public:
Node(){}
void setData(int d){
data = d;
}
int getData(){
return
data;
}
void setNextNodePtr(Node*
nodePtr){
nextNodePtr = nodePtr;
}
...
In this assignment, you will use a Hashtable to determine the common elements in all the...
In this assignment, you will use a Hashtable to determine the
common elements in all the lists. If an element appears more than
once in one or more lists, the algorithm should capture the
instances the element is present in all the lists.
You are given a code that implements a Hashtable as an array of
linked lists. You are also given a main function that will create
an array of Lists using the input variable values that you enter....
A binary tree is a complete binary tree if all the internal nodes (including the root...
A binary tree is a complete binary tree if all the internal nodes (including the root node) have exactly two child nodes and all the leaf nodes are at level 'h' corresponding to the height of the tree. Consider the code for the binary tree given to you for this question. Add code in the blank space provided for the member function checkCompleteBinaryTree( ) in the BinaryTree class. This member function should check whether the binary tree input by the...
in c++ please program for this code #include <iostream> #include <fstream> #include <string> #include <cstring> //...
in
c++ please
program for this code
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style
string processing
#include <algorithm> // max function
#include <stdlib.h>
#include <time.h>
using namespace std;
// Extend the code here as needed
class BTNode{
private:
int nodeid;
int data;
int levelNum;
BTNode* leftChildPtr;
BTNode* rightChildPtr;
public:
BTNode(){}
void setNodeId(int id){
nodeid = id;
}
int getNodeId(){
return nodeid;
}
void setData(int d){
data = d;
}
int getData(){
return data;...
#include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ...
#include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ListNode *head; class LinkedList { public: int insertNode(float num); void deleteNode(float num); void destroyList(); void displayList(); LinkedList(void) {head = NULL;} ~LinkedList(void) {destroyList();} }; int LinkedList::insertNode(float num) { struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL; newNode = new ListNode; if(newNode == NULL) { cout << "Error allocating memory for new list member!\n"; return 1; } newNode->value = num; newNode->next = NULL; if(head==NULL) { cout << "List...
In this project, you are asked to design and implement a class for double link list...
In this project, you are asked to design and implement a class for double link list to hold integers: – The class should be called DList, you also need a class called Node that contains an int as the data – Node needs the following data: int data; //the data held by the node Node* parent; //the parent of the Node Node* child; //the child of the Node – Node needs the following public functions: Node(int)// constructor to create a...
In C++ Implement a queue data structure using two stacks. Remember a queue has enqueue and...
In C++ Implement a queue data structure using two stacks. Remember a queue has enqueue and dequeue functions. You could use either the array or linked list implementation for stacks and queues. Source for stack array: --------------------------------------------------- #include<iostream> #define SIZE 100 #define NO_ELEMENT -999999 using namespace std; class Stack { int arr[SIZE]; // array to store Stack elements int top; public: Stack() { top = -1; } void push(int); // push an element into Stack int pop(); // pop the...
HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD COMMENTS: stackARRAY: #include<iostream> #define SIZE...
HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD
COMMENTS:
stackARRAY:
#include<iostream>
#define SIZE 100
#define NO_ELEMENT -999999
using namespace std;
class Stack {
int arr[SIZE]; // array to store Stack elements
int top;
public:
Stack() {
top = -1;
}
void push(int); // push an element into Stack
int pop(); // pop the top element from Stack
int topElement(); // get the top element
void display(); // display Stack elements from top to bottom
};
void Stack...
C++ Please ensure code is fully working, will rate Question to be answered: Repeat Exercise...
C++ Please ensure code is fully working, will rate Question to be answered: Repeat Exercise 1 for the class linkedStackType question one: Two stacks of the same type are the same if they have the same number of elements and their elements at the corresponding positions are the same. Overload the relational operator == for the class stackType that returns true if two stacks of the same type are the same, false otherwise. Also, write the definition...
NO ONE HAS PROVIDED THE CORRECT CODE TO PROVIDE THE GIVEN OUTPUT. PLEASE PROVIDE CODE THAT...
NO ONE HAS PROVIDED THE CORRECT CODE TO PROVIDE THE GIVEN OUTPUT. PLEASE PROVIDE CODE THAT WOULD CAUSE THE HW1.java TO PRINT THE RIGHT DATA.!!! The LinkedList class implements both the List interface and the Stack interface, but several methods (listed below) are missing bodies. Write the code so it works correctly. You should submit one file, LinkedList.java. Do not change the interfaces. Do not change the public method headers. Do not rename the LinkedList class. None of your methods...
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class Node{
private:
int data;
Node* nextNodePtr;
public:
Node(){}
void setData(int d){
data = d;
}
int getData(){
return
data;
}
void setNextNodePtr(Node*
nodePtr){
nextNodePtr = nodePtr;
}
...
In this assignment, you will use a Hashtable to determine the
common elements in all the lists. If an element appears more than
once in one or more lists, the algorithm should capture the
instances the element is present in all the lists.
You are given a code that implements a Hashtable as an array of
linked lists. You are also given a main function that will create
an array of Lists using the input variable values that you enter....
in
c++ please
program for this code
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style
string processing
#include <algorithm> // max function
#include <stdlib.h>
#include <time.h>
using namespace std;
// Extend the code here as needed
class BTNode{
private:
int nodeid;
int data;
int levelNum;
BTNode* leftChildPtr;
BTNode* rightChildPtr;
public:
BTNode(){}
void setNodeId(int id){
nodeid = id;
}
int getNodeId(){
return nodeid;
}
void setData(int d){
data = d;
}
int getData(){
return data;...
HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD
COMMENTS:
stackARRAY:
#include<iostream>
#define SIZE 100
#define NO_ELEMENT -999999
using namespace std;
class Stack {
int arr[SIZE]; // array to store Stack elements
int top;
public:
Stack() {
top = -1;
}
void push(int); // push an element into Stack
int pop(); // pop the top element from Stack
int topElement(); // get the top element
void display(); // display Stack elements from top to bottom
};
void Stack...
Most questions answered within 3 hours.
-
Part of an ANOVA table is shown below.
Source of
Variation
Sum of
Squares
Degrees of...
asked 14 minutes ago -
Business process improvement initiatives often include
introducing new technology to support the new or changed ways...
asked 20 minutes ago -
Review your choice of either Agile or the Waterfall models and
for each of the 22...
asked 21 minutes ago -
Suppose an x distribution has mean μ = 4.
Consider two corresponding
x
distributions, the first...
asked 23 minutes ago -
A study of the effects of exercise used rats bred to have high
or low capacity...
asked 50 minutes ago -
Using your data from the experiment, calculate the initial moles
of HCl that you started with....
asked 50 minutes ago -
Suppose you want to make 500 mL of a 0.20 M Tris buffer at pH
8.0....
asked 52 minutes ago -
The titanic hit an iceberg estimated to be half of her mass.
Before hitting the iceberg,...
asked 1 hour ago -
3. The top four firms in Industry A have market shares of 30,
25, 10, and...
asked 1 hour ago -
Are there such things as microscopic multicellular animal
parasites? If so, please give examples.
asked 1 hour ago -
1. What two structures in the ear are involved in your
sense of balance and in...
asked 1 hour ago -
Two ice skaters suddenly push off against one another starting
from a stationary position. The 45...
asked 1 hour ago