Question

Give an example of a commonly used product-type from type algebra. Give it’s type algebraic description, and a type constructor in the C++17 standard library that implements it.

Answer 1

A stack is either empty or it consists of two parts, a top element and stack (the remaining elements). The elements in a stack may be of any type, but all the elements in a given stack must be the same type. The operations on stacks are Pre-conditions: none Post-conditions: S is defined and empty CreateStack)Inputs: no inputs required Outputs: S - a stack has been created Algorithm: stack is initialised. Pre-conditions: none Post-conditions: S is undefined. All resources (eg memory) allocated to S have been released. No stack operation can be performed on S Inputs: the stack Outputs: an empty stack Algorithm: stack is re-initialised Pre-conditions: stack is not empty Post-conditions: the top element has been removed from the stack Inputs: the stack Outputs: the changed stack, ie top element, has been removed Algorithm: remove the top element of the stack; give a copy of the element back to the user DestroyStack) Pop(element) Push(element) Pre-conditions: the stack exists, element is of appropriate type Post-conditions: Element is put onto the top of the stack. Inputs: a stack and an element Outputs: a changed stack Algorithm: insert the element into the stack Pre-conditions: a stack exists Post-conditions: returns true if empty false otherwise Inputs: a stack Outputs: boolean value Algorithm: check initial status of the stack and report whether empty or not. IsEmpty) Class to represent a stack Data members Node<TstkTop Pointer to top (first) node in list. stkSize - Number of items currently stored in stack. Methods 1. Default constructor Sets stack to initial empty state stkTop nullptr; stkSize0 2. size(0

Return stkSize 3. empty0 True if stkSize == 0; otherwise, false. (Could check whether or not stkpTop 4. clear) Similar to queue 5. top) Returns top item of the stack. if (stack is empty) nullptr instead.) throw exception return stkTop->data 6. push0 Insert new item at top of stack. NodeT* newNodenew Node-T>(item, stkTop); stkTop newNode; stkSize++; 7. popo Remove top item from stack. if (stack is empty) throw exception stkTop = stkTop->next; delete delNode stkSize- // or stkTop = delNode.)next 8. Copy Constructor template <class T> Stack<TStack(const Stack<T>& other) stkTop = nullptr; copyList(other) stkSize other.stkSize 9. C opy Assignment Operator template <class T> Stack«T>& Stack-T>. :operator=(const Stack<T>& Other) if (this !- &other)

clear) copyList(other) stkSizeother.stkSize return *this; 10. Destructor Sames as queue 11. copyList) template <class T> void StackT: copyList(const Stack<T>& other) Node<Tptr, newNode, lastnullptr; for (pt. Other.stkTop, ptr != nullptr; ptr = ptr->next) newNode = new Node<T>(ptr->data) if (last = nullptr) stkTop = newNode; else last->next new Node; last newNode