USE C++ PROGRAMMING LANGUAGE

DO NOT USE any of the STL (including the vector or list type) in your code.

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

Implement a Stack ADT using a singly linked list. The class should be named RecursiveStack. Implement all basic class functions (default constructor, copy constructor, destructor, copy assignment) and basic stack functions (pop, push, top, isEmpty). Pop should be done from the head of the linked list.

Recursive Functions Implement the following functions recursively:

1. recShift(): shifts all the elements in the linked list to the next node. The first element is duplicated, and the last element is moved out of the array.

stack = 1 5 3 8 7 stack.recShift(); stack = 1 1 5 3 8

2. sumOdd(): returns the sum of each element at odd (1st, 3rd, 5th, etc.) nodes. stack = 1 5 3 8 7 stack.sumOdd(); //returns 11 (1 + 3 + 7)

3. popTill(int x): pops all values before x and returns whether x is in the list.

stack = 1 5 3 8 7 stack.popTill(3); stack=387 //returns true stack.popTill(4); stack = { empty } //returns false

4. print(): prints the stack with comma separated values. There should be no trailing comma. For example, the original stack used above will be printed as: 1, 5, 3, 8, 7

For these functions, you can use a helper function that takes (Node* head) as a parameter.

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

The RecursiveStack class should be in two files named stack.h and

stack.cpp. The driver should be in a file named main.cpp.

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

EXECUTION EXAMPLE Your class files should support tests such as these:

RecursiveStack r; r.recShift(); int sum = r.sumOdd(); 

bool b; b = r.popTill(3); r.print(); 

Output: Elements on the stack are: 1,5,3,8,7

Elements on the stack after shift are: 1,1,5,3,8

The sumOdd is 14. 

//calling popTill(5) 

True, 5 was on the list. 

Elements on the stack after popTill(5) are: 5,3,8