Разработайте структуру данных с помощью операций вставки (ключ, значение), получения, удаления и получения последних обращений к ключу для каждой сложности O (1)

Question

Я могу создать класс с картой членов для хранения ключа, значения и стека, чтобы поддерживать историю операций, выполняемых над объектами класса.Однако самая сложная часть - это последний поиск ключа в O (1) - если ключ был удален, мне потребуется поискать во всем стеке действительный ключ на карте, который в худшем случае будет иметь значение O (n).

Например,

insert(a,1)
insert(b,1)
get(a) -> output 1
get_last_key -> output a delete(a)
get_last_key -> output b

Есть ли лучший способ проектирования конструкции для повышения производительности?