Задание 4. Поиск минимумов
Задание 4.1. Стек минимумов
Сделать стек на основе односвязного списка, у которого трудоемкость взятие минимума, вставка в стек и удаление из него за O(1)
.
Связный список надо написать самим.
Операции:
- вставить в конец стека
- удалить последний элемент стека
- выдать минимальный элемент в стеке
Входные данные
На вход программы подаются команды, их количество не превышает 100_000. В каждой строке находится одна из команд:
push k
— положить число k в стек.pop k
— убрать последний элемент в стеке.top
- выдать последний элемент в стеке.min
- выдать текущий минимум в стеке.
Тип данных k — int.
Гарантируется, что некорректные команды подаваться НЕ будут.
Выходные данные
Вывести результат выполнения команд top
и min
в консоль.
Пример
Вход
push 42
top
min
push 12
min
push 13
top
min
pop
pop
min
Выход
42
42
12
13
12
42
Шаблон кода
public interface MinStack<T extends Number> {
void push(T value);
T pop();
T top();
T min();
}
// НЕ ДЕЛАЙТЕ это всё в одном файле 🙏🙏🙏
public class MinStackImpl implements MinStack<Integer> {
@Override
public void push(Integer value) {
// TODO
}
@Override
public Integer pop() {
// TODO
return null;
}
@Override
public Integer top() {
// TODO
return null;
}
@Override
public Integer min() {
// TODO
return null;
}
}
Задание 4.2 Очередь с приоритетом на основе Кучи
Разработать структуру данных Очередь, выполняющую следующие операции:
- Вставить в очередь за .
- Извлечь максимальный элемент .
- Увеличить
i-ый
элемент наv
.
Все операции вставки в очередь вводятся по очереди и нумеруются с 1.
При извлченении элемента из очереди, нужно вывести в стандартый поток вывода сам элемент и номер операции, когда его добавили.
То есть в структуре данных надо хранить само значение элемента и номер операции, когда его добавили.
Входные данные
На вход программы подаются команды, их количество не превышает 100_000. В каждой строке находится одна из команд:
enqueue k
— вставить в очередь число k.dequeue-max
— извлечь из очереди максимальный элемент.inc i v
- найти элемент вставленныей на i-ой операции и увеличить его на v. Если элемента уже нет, то ничего не делать.
Тип данных k, v
— Integer
, i
— Long
.
Гарантируется, что некорректные команды подаваться НЕ будут.
Выходные данные
Команда dequeue-max
печатает в консоль номер операции i, когда элемент был вставлен, и сам элемент k
.
Если очередь пустая, то печатаем *
.
Пример
Вход
enqueue 10
enqueue 42
enqueue 9
dequeue-max
inc 3 10
dequeue-max
dequeue-max
dequeue-max
Выход
2 42
3 19
1 10
*
Шаблон кода
public interface PriorityQueue<T extends Number> {
void enqueue(T value);
T dequeueMax();
void increment(long operation, T addition);
}
// НЕ ДЕЛАЙТЕ это всё в одном файле 🙏🙏🙏
public class PriorityQueueImpl implements PriorityQueue<Integer> {
@Override
public void enqueue(Integer value) {
// TODO
}
@Override
public Integer dequeueMax() {
// TODO
return null;
}
@Override
public void increment(long operation, Integer addition) {
// TODO
}
}