Problem 8.1 Stacks & Queues
(a) Implement using C++, Python or Java the data structure of a stack backed up by a linked list, that can store data of any type, and analyze the running time of each specific operation. Implement the stack such that you have the possibility of setting a fixed size but not necessarily have to (size should be −1 if unset). Your functions should print suggestive messages in cases of underflow or overflow. You can assume that if the size is passed, it will have a valid value.
class Stack[T]:
private:
struct StackNode {
T data;
StackNode ∗ next;
};
// linked list
StackNode ∗ top;
// top of stack
int size;
// -1 if not set, value otherwise
int current_size; public:
// unused if size = -1
push(x : T) : void
// if size set, check for overflow
pop() : T
// return element if not in underflow
isEmpty() : bool Stack(int new_size)
Stack()
// true if empty, false otherwise
(b) Implement a queue which uses two stacks to simulate the queue behavior.
Problem 8.2 Linked Lists & Rooted Trees
(a) Write down the pseudocode for an in-situ algorithm that reverses a linked list of n elements in Θ(n). Explain why it is an in-situ algorithm.
(b) Implement an algorithm to convert a binary search tree to a sorted linked list and derive its asymptotic time complexity.
Implement an algorithm to convert a sorted linked list to a binary search tree and derive its asymptotic time complexity. The search time complexity of the resulting binary search tree should be lower than the one for the equivalent sorted linked list
