2 Catenable Stack (30 pts) In this problem you will design a data structure that implements Stack ADT using singly-linked list instead of an array. In addition your stack will have the following additional operation: public catenate (Stack s); // appends the contents of Stacks to the current stack The new operation will have the following properties: Let n = 31.size(), m = 82.size(). Then executing 81.catenate(82) results in the following: 1. The new size of sy is the sum of the size of 82 and the original size of S1, i.e., the following evaluates to true: 81.size() == n +m 2. Top n elements of s after the call 81.catenate(82) are the same as the elements of s before the call. The bottom m elements of si after the call 81.catenate(82) are the same as the elements of sy before the call. (a) The implementation described in the book, lecture notes and screencasts uses an array to implement Stack ADT. Can you implement catenate(Stack s) operation that runs in O(1) time for such imple- mentation? If yes, write down the algorithm that achieves that and demonstrate that it runs in O(1) time. If not, describe what goes wrong. (b) Write down algorithms that implement the original Stack ADT using a singly-linked list instead of the array. That is, write down pseudocode for implementing each operation of Stack ADT: Stack(), push(Object o), pop(), size(), isEmpty(), top(). Make sure that each of the above opera- tions takes at most (1) time in your implementation. (c) Design an algorithm that implements catenate(Stack s) operation in O(1) time. Write down the algorithm and demonstrate that it runs in O(1) time