Algorithms and Data Structures

1.

Summer Trimester
Algorithms and Data Structures
Assignment 2 – Stack, Queue, Heap, Hash Table, BST
Deadline: 21.08.2022 23:59
Cheating is strongly prohibited.
Task 1 – Stack
Implement the logic of postfix expression using Stack. Example is below.
Input: 3 10 5 + *
Output: 45
Task 2 – Queue
Complete the implementation of WaitingQueue using the code snippet below. There will be at
most 9 people in the queue. Nobody will be able to join the queue when it is full.

2.

Task 3 – Heap
Convert an input array to a Min Heap.
Input: [9, 4, 7, 1, -2, 6, 5]
Output: [-2, 1, 5, 9, 4, 6, 7]
Task 4 – Hash Table
Hash Table key-value pairs are stored unsorted. Which means no matter what keys and values you insert
into Hash Table, the result would not be in any particular order. The task is to sort a Hash Table keys in
ASC & DESC order (users chooses the order of sorting).
Input: {“1”: “One”, “7”: “Seven”, “3”: “Ush”, “2”: “Dva”}
Output: {“1”: “One”, “2”: “Dva”, “3”: “Ush”, “7”: “Seven”}

3.

Input: {“Watermelon”: “Qarbyz”, “Apple”: “Alma”, “Pear”: “Almurt”, “Peach”: “Orik”}
Output: {“Apple”: “Alma”, “Peach”: “Orik”, “Pear”: “Almurt”, “Watermelon”: “Qarbyz”}
Task 5 – BST
Write a Java program to convert an array to binary search tree. Maintain minimal height of the tree.
Input: [1, 2, 3, 4, 5, 6]
Output: 2 1 4 6 5 3