Description
Problem 1: Stacks & Queues (7+3=10 points)
- Implement in Python or C++ the data structure of a stack backed up by a linked list, that can workfor whatever type, and analyze the running time of each specific operation. In order to achieve this in C++, make use of template < classT >, on which you can find more information at
Implement the stack such that you have the possibility of setting a fixed size but not necessarily have to (size is -1 when unset). Check for the correctness of your functions and throw exceptions with suggestive messages in cases of underflow or overflow(C++,Python). You can assume that if the size is passed, it always has a valid value.
| class Stack [A ] ( ) :
private : s t r u c t StackNode ( ) { / / linked l i s t A data ; StackNode ∗next ; }; StackNode ∗top ; / / top of stack i n t size ; / /−1 i f not set , value otherwise i n t current size ; / / unused i f size = −1 public : fun push ( x :A) : void / / i f size set , check f o r overflow fun pop ( ) :A / / return element i f not in underflow fun isEmpty ( ) : bool / / 1 i s empty , 0 otherwise fun Stack ( i n t new size ) fun Stack ( ) |
5
10
15
Checking will be done by case-tests alone. The tests will cover overflow and underflow cases, as well as tests for different types of variables.
- Show how a queue can be implemented with two stacks.
Problem 2: Linked Lists & Rooted Trees (4+5+3=12 points)
- Program an in-situ algorithm that reverses a linked list of n elements in Θ(n). Add an explanation to why it is an in-situ algorithm in the code.
- Program an algorithm to convert a binary search tree to a sorted linked list and derive its asymptotictime complexity.
- Program an algorithm to convert a sorted linked list to a binary search tree and derive its asymptotictime complexity.
