ValidStack<T> and ValidQueue<T>
- Due Oct 21, 2019 by 10pm
- Points 0
- Submitting a file upload
- File Types cpp
Introduction
This lab comes in two parts: the first part completes the lab from two weeks ago by building an object using the ValidPointer<T> class, and the second part sets up a new class from scratch using all the learning you've done to-date.
Part 1: Creating a ValidStack<T>
Now that you have a ValidPointer<T>, you can build other classes that use the ValidPointer<T> to ensure all the state in the ADT remains valid. For instance, if you did something like
ValidPointer<Stack<int>> my_valid_stack;
you would be able to ensure that the data in the Stack object is valid and unchanged, BUT, the Stack object only has a top member. The rest of the state in the ADT is pointed to by the top member in a chain of values that are not checked beyond the value of the top pointer. To have a fully validated stack, we need to check all the values in this chain to see that each one is correct--not just the first value.
The interface
For this first part, you will create a new class named ValidStack<T> that has the following methods:
- push() puts a T element on the top of the stack
- pop() returns a T element that it removes from the top of the stack
- isEmpty() returns a boolean value indicating whether the stack is empty
- isValid() returns a boolean value indicating whether all elements in the stack are valid
The process
There are several steps necessary to create a ValidStack<T>.
Creating a ValidStackElement<T>
To start with, you will want to create a new class named ValidStackElement<T> that has the following class definition:
template <typename T>
class ValidStackElement {
T data;
ValidPointer<ValidStackElement<T>> next;
public:
ValidStackElement(T init, ValidStackElement<T> *ptr);
bool isValid();
};
Note that we've created a constructor for this new class that will initialize both the data value and provide a pointer for the ValidPointer<T> constructor. This ensures that our ValidStackElement<T> can always be valid.
You will want to use the technique of member initialization in the constructor so that you can set up the member values properly. In this example, that looks like:
ValidStackElement<T>::ValidStackElement(T init, ValidStackElement<T> *ptr)
: data(init), next(ptr)
{
}
What this does is call the T constructor for data and passes it init AND call the ValidPointer<ValidStackElement<T>> constructor for next and passes it ptr. The point of member initialization is that the compiler has to call some constructor for every member of the container class prior to allowing you to change values in the container--member initialization allows you to specify which constructor the compiler should use. If you do this strategically, you may not need to update any values inside the constructor because you've passed the best values into each member's constructor. The code above is an excellent example.
Creating an isValid() member function for ValidStackElement<T>
Now, you need to specify the implementation for the isValid() member function. To do so, you're going to have to check two things:
- is the current stack element valid, and
- are all the other stack elements we're pointing to are valid.
Checking the current stack element's validity is pretty easy given the interface to ValidPointer<T>. Checking the other elements' validity is pretty difficult because you have no way to access the pointer held by ValidPointer<T>. You will have to add a new method to ValidPointer<T> that returns the internal pointer. For now, call this new method get(). With this new method, you can follow the pointer to the next element and recursively check its validity.
Creating a ValidStack<T> class
Now that you have a ValidStackElement<T> class, you can use this to create a new ValidStack<T>. This should be a matter of changing the type of the data member top and any calls to create a new StackElement<T>.
Creating an isValid() member function for ValidStack<T>
The process here is very similar to the isValid() method for ValidStackElement<T>. If you can check that the top stack element is valid and that all the elements it points to are valid, then you should have a valid stack.
Part 2: Creating a ValidQueue<T>
Use your knowledge of how to build ValidStack<T> and research on how to build a Queue<T> to create a ValidQueue<T> ADT. The ADT should have the following methods:
- enqueue() put a T element at the end of the queue
- dequeue() removes the first element from the front of the queue and returns it
- isValid() returns a boolean value indicating whether the queue and all its elements are valid
- isEmpty() returns a boolean value indicating whether the queue has any elements