Lab 4 (100 pts)

Due Thursday, October 27 at 11:20am on Catalyst and as a hard copy in class at 11:30am

Writing the Stack From Your List Class
Hint: Writing these functions is much easier than you think! Many require just one line of code.
  • For our Stack data structure we built a Stack class from scratch.
  • Let's write a second implementation based off of our List class.
  • You can use either your singly-linked list implementation, or, if you are finished with your homework, your doubly-linked list implementation.
  • In the same folder where you saved your List.h and List.cpp create a new file called Stack.h and one called Stack.cpp.
  • Copy and paste the following code into the Stack.h file.
  • Note that you should not change this file in any way.



#ifndef Stack_H_
#define Stack_H_

#include "List.h"
#include <iostream>
#include <cstddef>

using namespace std;

class Stack
{
    public:
        /**constructors and destructors*/

        Stack();

        //initializes an empty stack
        //postcondition: an empty stack

        Stack(const Stack &S);
        //initializes this stack to have same elements as S
        //postcondition: a copy of stack

        ~Stack();

        //frees memory allocated to the stack
        //postcondition: memory for stack has been freed

        /**manipulation procedures*/

        void pop();
        //removes an element from the top of the stack
        //precondition: the stack isn't empty
        //postcondition: an element has been removed from the top of the stack

        void push(int data);
        //adds an element to the top of the stack
        //postcondition: an element added to the top of the stack

        /**accessors*/   


bool operator==(const Stack &S);
//returns whether this stack is equal to another stack S

int get_top();
//returns the element at the top of the stack
//precondition: the stack is not empty

int get_size();
//returns the size of the stack


/**additional operations*/


    void print();
    //prints the elements in the stack in a programmer-specified format to stdout


    private:
        List<int> stack;
 

};


#endif /* Stack_H_ */


  • You are going to be storing the data for your Stack in a linked list called stack.
  • Note that it is the single private field inside your Stack.h file:

private:
        List<int> stack;

  • Unlike our List, there are no other private fields in the Stack header file. The reason: We are using this List named stack to store all of the data pertaining to the Stack. We do not need any other fields but this one, as the List can perform all the operations we need!


Stack Operations and Your Stack.cpp File:
  • Now, write your Stack implementation inside of your Stack.cpp file.
  • Inside each of the Stack functions, you should call the appropriate List functions to update stack.
  • For example:
void Stack::push(int data)
{
    stack.add_front(data);
}
  • You should not be re-writing any of your List functions here, just calling them!

Stack constructor and destructor
  • The body of these two functions should simply be left blank. Why?
  • The constructor body should be left blank, because there are no new fields to initialize in the constructor
    • The private List name stack is already initialized inside the Stack.h file, with this line of code:
List<int> stack; //calls the List default constructor
  • The body of the destructor also should be left blank. For example, you would NOT wish to write the following:
Stack::~Stack()
{
    stack.~List(); //<--don't do this!!!
    //you never need to explicitly call a destructor in this class!
}
  • Instead, leave the body of this function empty.
  • The reason?
    • Only in the rarest of circumstances would you need to call a destructor explicitly.
    • Instead, the destructor is called automatically once an object goes out of scope.
    • For our Stack, once its private List named stack goes out of scope, the List destructor will be called automatically.
Stack Copy Constructor
  • Here, you will want to call the copy constructor of the List class:
Stack::Stack(const Stack &S):stack(S.stack){}
  • How do you test this copy constructor?

//make a new Stack object with the default constructor

Stack s1;

//add data to s1

s1.push(20); //can add more data below

...

//make another new Stack object named s2 by calling the copy constructor

Stack s2(s1); // passing in s1 to make a copy of

//Now, print s2 to make sure it contains the same data as s1

s2.print();

  • Don't forget to test all of your functions inside of your main function in a file called StackTest.cpp
  • Also, don't forget to print out the results of your tests in your StackTest.cpp in your comment at the bottom of main.


What to submit

  • Submit your List.h, Stack.h, Stack.cpp, and StackTest.cpp files to Catalyst when you are finished.
  • Note that your StackTest.cpp should provide a copy of the print out of running your tests inside a comment at the bottom of the file.
  • Submit your Stack.cpp and StackTest.cpp as hard copies in class


How You Will Be Graded

  • You will receive 80 points for providing a working Stack data structure with all functions implemented.
    • 20 points will be for adequate testing
    • 15 points for a correct implementation of the == function.
    • 10 points each for all remaining functions
  • You will receive no credit if you do not use the Stack.h file provided above or alter it in any way