Please fill in these two part:

/* * Instructions: * * 1. Only complete the functions specified below. Do not create any additional function. * 2. Use Visual Studio 2019 to build, test and run your code. * 3. Do not include any additional header or library. * 4. This is an exercise of linked list operations. Do not copy linked lists to arrays for manipulation. * 5. Implement the function reverseList() and the class MyStack as specified below. * 6. All linked lists in this exercise are singly-linked, non-circular and without header node. * */

#include #include #include #include

using namespace std;

/* Linked list node */ template struct node { T data; node* next; };

/* * Stack ADT * Please refer to the definition of stack's functions in the lecture notes. */ template class AbstractStack {

public: virtual int size() const = 0; virtual bool empty() const = 0; virtual T& top() const = 0; virtual void push(const T& item) = 0; virtual void pop() = 0; };

//-------------------------- classes/functions to be implemented by you

/* * Linked list implementation of the AbstractStack. * * Complete the five functions: size, empty, top, push and pop, according to their definition. */ template class MyStack : public AbstractStack {

private: node* head; // internal linked list for storing the stack's items int length; // length of the internal linked list - used to track the stack's size

public:

MyStack() { head = NULL; length = 0; }

~MyStack() { node* temp; while (head != NULL) { temp = head; head = head->next; delete temp; } }

bool empty() const { }

int size() const { }

void push(const T& item) { }

// precondition: stack is not empty T& top() const { return }

void pop() { } };

/* * The function uses a stack to reverse the link in the nodes of the input list. * It returns the head of the reversed list. */ node* reverseList(node* head) {

// Use this stack to reverse the list. // It is used to store node pointers instead of node data. MyStack*> stack;

}

//-------------------------- functions prepared for you

/* * Helper class for creating/printing a list from an array. */ template class ListHelper { public: // build a list based on array input static node* newList(T* arr, int n) {

node dummy = { NULL, NULL }; node* cur = &dummy; for (int i = 0; i < n; i++) { cur->next = new node({ arr[i], NULL }); cur = cur->next; } return dummy.next; // without dummy header }

//print nodes in a given linked list static void printList(node* list) { while (list != NULL) { cout << list->data << "-> "; list = list->next; } cout << "NULL" << endl; }

//delete nodes in a given linked list static void deleteList(node* list) { node* temp; while (list != NULL) { temp = list; list = list->next; delete temp; } } };

/* * Driver program * * Read the test cases from the input file and use them to test * your functions' implementation. * */ int main(int argc, char** argv) {

ifstream fin("tut06_input.txt"); if (!fin) { cout << "Input file not found."; exit(1); }

int testcase = 0; fin >> testcase;

for (int i = 0; i < testcase; i++) {

int n; fin >> n; int* arr = new int[n]; for (int j = 0; j < n; j++) fin >> arr[j];

node* list = ListHelper::newList(arr, n);

cout << "Case " << i + 1 << endl; cout << "Input:\t\t"; ListHelper::printList(list);

cout << "Reversed:\t"; list = reverseList(list); ListHelper::printList(list);

cout << endl;

ListHelper::deleteList(list); delete[] arr; }

return 0; }

Input:

The first line of input contains an integer T denoting the number of test cases. The first line of each test case contains an integer N, which is the length of the list. The second line of each test case contains N integers separated with a space which are the data for the list.

4 1 1 2 2 1 5 1 3 5 7 9 0

output:

Case 1 Input: 1-> NULL Reversed: 1-> NULL

Case 2 Input: 2-> 1-> NULL Reversed: 1-> 2-> NULL

Case 3 Input: 1-> 3-> 5-> 7-> 9-> NULL Reversed: 9-> 7-> 5-> 3-> 1-> NULL

Case 4 Input: NULL Reversed: NULL