Question

In: Computer Science

Description( IN C++)!! The purpose of this challenge is to implement a stack using a Linked...

Description( IN C++)!!

The purpose of this challenge is to implement a stack using a Linked List as a backing data structure

Requirements

  1. Write the following structs
    struct Location
    {
      string name;
      string address;
    };
    
    struct VisitNode
    {
      Location loc;
      VisitNode * next;
    };
  2. Create a class called Stack. In this class, create a private variable VisitNode * head. This will keep track of the location of the head node.
  3. Add the following private function. This function will be used to dynamically create new nodes for the linked list.
    VisitNode * create()
    {
      VisitNode * newnode;
      try
      {
        newnode = new VisitNode;
      }
      catch (bad_alloc)
      {
        newnode = NULL;
      }
      return newnode;
    }
    
    // USAGE: To create a new node, use as follows
    // VisitNode * newnode = create();
  4. Create a private function called void deallocate(). This function will traverse the entire list and delete each node. Remember to make a copy of head. Also, realize that if you delete the current node as you’re traversing, you may lose the reference to the next node.
  5. Create a destructor which will call deallocate() and set head to NULL.
  6. Create a public function, bool push(string name, string address). This function will:
    1. create a new node (VisitNode) using the create() function you wrote earlier. The new node will be assigned the values for loc from the function’s parameter values.
    2. add the new node to the front of the linked list (where head points). Remember to deal with two possible scenarios: 1) The list is still empty and this is the first node to be added and 2) The list is not empty
    3. point head to the newly-added node
    4. return true if it’s successful, and false otherwise. The only reason it would be false is if the new node didn’t get created by the create() function (if the new node is NULL)
  7. Create a public function, string pop(). This function will
    1. Identify the node at the front of the list (if not empty)
    2. Copy the value of the node’s loc.name property into a temporary variable
    3. Point head to the next node in the list (or NULL if it’s the last node)
    4. delete the first node (this effectively is the “pop” action)
    5. Return the loc.name value stored in the temporary variable. Return a blank string if the linked list is empty
  8. Create a friend function void show(Stack & S). This will display all the loc.name values of all the nodes on a single line, separated by spaces. Traverse the entire linked list to show the node values.
  9. main() is given below. Use it exactly as is. Note that main uses the Stack class as an abstract data type (ADT). From the perspective of the object browser, it doesn’t even know or care that a linked-list is the mechanism that makes LIFO (last-in, first-out) work.

Sample main()

int main()
{
  Stack browser;

  // simulate a browser history
  browser.push("Google", "https://google.com");
  browser.push("Amazon", "https://amazon.com");
  browser.push("LinkedIn", "https://LinkedIn.com");
  browser.push("Reddit", "https://reddit.com");  

  show(browser);   // this should show the entire history

  // simulate clicking Back button
  string top = browser.pop();
  if (top != "")
    cout << endl << "Clicked back from " << top << endl;
  show(browser);

  // simulate clicking Back button  
  top = browser.pop();
  if (top != "")
    cout << endl << "Clicked back from " << top << endl;
  show(browser);

  // simulate clicking Back button
  top = browser.pop();
  if (top != "")
    cout << endl << "Clicked back from " << top << endl;
  show(browser);

  return 0;
}

Solutions

Expert Solution

please please thumbs up!!!

hope it will help uh out!!

Code::
(IN C++ PROGRAMMING LANGUAGE)

-------------------------------------------------------

#include <iostream>
using namespace std;
struct Location{ // create structure to represent data in node
string name;
string address;
};

// create structure to represent node in linked list
struct VisitNode {
Location loc; // data stored in node
VisitNode* next; // pointer to next node
};

// create class to represent stack
class Stack {
private:
VisitNode* head; // top of the stack

// function to create new node
VisitNode* create() {
VisitNode* newNode;
try {
// dynamically allocte memory to new node
newNode = new VisitNode;
}
catch (bad_alloc) {
// if allocation fail set new node to NULL
newNode = NULL;
}
return newNode;
}

// delete all nodes from stack
void deallocate() {
// create a temparory node to delete current node
VisitNode* temp = head; // assign temp to head to delete top node
while (head != NULL) {
// move head to next node
head = head->next;
// delete current node
delete temp;
// re assign temp to head to delete next node
temp = head;
}
}

public:
// destructor
~Stack() {
deallocate();
head = NULL;
}

// place a new node on topof stack
bool push(string name, string address) {
// create a new node
VisitNode* newNode = create();
// check if newNode created, before addiing data to it
if (newNode == NULL) {
return false;
}
// add data to new node
newNode->loc.name = name;
newNode->loc.address = address;
newNode->next = NULL;
// now assign new node at top of stack
// check if stack have any nodes
if (head == NULL) {
// newNode is first node to be added
head = newNode;
}
else {
// assign newNode to top of head
newNode->next = head;
// re-assign head at top node
head = newNode;
}
}

// removes top node and returns name from loc data
// if stack is empty returns empty string
string pop() {
// check if stack is empty
if (head == NULL) {
// return empty string
return "";
}
else {
// copy the data from top node
string data = head->loc.name;
// create a temporary node to delete first node
VisitNode* temp = head;
// move head to next node in stack
head = head->next;
// delete the top node
delete temp;
return data;
}
}
// create a friend function
// friend function can access the private data of the class member
friend void show(Stack& s) {
// traverse the entire list and print each node's loc.name
// in sigle line
// to traverse the list create a pointer(iterator)
VisitNode* itr = s.head;
while (itr != NULL) { // loop till end of list
// print each node's data
cout << itr->loc.name << " ";
// move iterator to next node
itr = itr->next;
}
}
};

// main function as given
int main() {
Stack browser;
// simulate browser history
browser.push("Google", "https://google.com");
browser.push("Amazon", "https://amazon.com");
browser.push("LinkedIn", "https://LinkedIn.com");
browser.push("Reddit", "https://reddit.com");

show(browser); // this should show the entire history

// simulate clicking Back button
string top = browser.pop();
if (top != "") {
cout << endl << "Clicked back from " << top << endl;
}
show(browser);

// simulate clicking Back button
top = browser.pop();
if (top != "") {
cout << endl << "Clicked back from " << top << endl;
}
show(browser);
// simulate clicking Back button
top = browser.pop();
if (top != "") {
cout << endl << "Clicked back from " << top << endl;
}
show(browser);

return 0;
}
-----------------------------------------------------------

output::


Related Solutions

Description The purpose of this challenge is to implement a circular doubly-linked list using a dummy...
Description The purpose of this challenge is to implement a circular doubly-linked list using a dummy node. This challenge simulates an operating system’s window manager. Requirements Write the following struct struct Window { string appname; Window *next; Window *prev; }; Create a class called WindowManager. In this class, create a private variable Window * head. This will keep track of the location of the head node. Create private variables Window * current, * dummy. current will keep track of the...
Description( IN C++) NO TAIL POINTERS!! The purpose of this challenge is to implement a queue...
Description( IN C++) NO TAIL POINTERS!! The purpose of this challenge is to implement a queue using a linked list as a backing data structure Requirements Write the following struct struct JobNode { string name; JobNode * next; }; Create a class called Queue. In this class, create a private variable JobNode * head. This will keep track of the location of the head node. Add the following private function. This function will be used to dynamically create new nodes...
using C++. edit this code down below so that it will implement stack with linked list...
using C++. edit this code down below so that it will implement stack with linked list contains a default constructor, a copy constructor, and a destructor. #include <iostream> #include <vector> #include <string> #include <stack> #include <limits> using namespace std; class Stack { public: bool isEmpty(); int top(); int pop(); void push(int); void printList(); private: vector<int> elements; }; bool Stack::isEmpty() { return elements.empty(); } int Stack::top() { if(isEmpty()) { throw runtime_error("error: stack is empty"); } return elements.back(); } int Stack::pop() {...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you will implement the functionality of a stack and a queue using a linked list. Your program must use of the declaration of the Stack and Queue class in Stack.h and Queue.h You have to implement the functionalities of queue (enq, deq, displayQueue) in a file called Queue.cpp. All the functions in Queue.cpp should follow the prototypes declared in Queue.h. Your code should make use...
How do you implement stack by using linked list? No code just explain it.
How do you implement stack by using linked list? No code just explain it.
in C++ For this program, you are going to implement a stack using an array and...
in C++ For this program, you are going to implement a stack using an array and dynamic memory allocation. A stack is a special type of data structure that takes in values (in our case integers) one at a time and processes them in a special order. Specifically, a stack is what's called a first-in-last-out (FILO) data structure. That is to say, the first integer inserted into the stack is the last value to be processed. The last value in...
Write a code to implement a python stack class using linked list. use these operations isEmpty...
Write a code to implement a python stack class using linked list. use these operations isEmpty   • push. • pop.   • peek. • size Time and compare the performances ( this is optional but I would appreciate it)
Implement a non-recursive reverse print of linked list using stack and the main function to test:...
Implement a non-recursive reverse print of linked list using stack and the main function to test: You will need to finish the printReversed_nonrecursive method in ch04.LinkedStack2 class, and the ch04.UseStack2 is the main function to test. public class LinkedStack2<T> extends LinkedStack<T> { private void revPrint(LLNode<T> listRef) { if (listRef != null) { revPrint(listRef.getLink()); System.out.println(" " + listRef.getInfo()); } } public void printReversed() { revPrint(top); } /* use stack to implement non-recursive reverse print */ public void printReversed_nonrecursive() { } public...
Write a C function to implement operation of a stack using the following format: /** *...
Write a C function to implement operation of a stack using the following format: /** * function: *       push * * expects: *       pointer to the stack *       pointer to the size *       the value to push * * returns: *     true when value has been pushed *       false otherwise * * The push function push a value to the passed in stack */ bool push(int *stack, int *size, int max_size, int to_push) {...
Solve this Write a C++ class that implements a stack using a linked list. The type...
Solve this Write a C++ class that implements a stack using a linked list. The type of data contained in the stack should be double. The maximum size of the stack is 30. Implement the following methods: . · Constructor and destructor; // 5 pts · void push (double value); // pushes an element with the value into the stack. 5 pts. · double pop (); // pops an element from the stack and returns its value. 5 pts. ·...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT