Пара стековых операций (pop + push) против альтернативы Hash Table

Question

У меня есть процесс, и он определен stack.Теперь, когда я перемещаю элемент на stack, мне нужно проверить, существует ли такой же / похожий элемент.Если нет - нажмите новый пункт.Это включает в себя две операции стека

1. извлечение элемента похожего типа, сравните, если он совпадает с выдвигаемым элементом
2. , затем нажмите последний.Вопрос в том, стоит ли понесенная стоимость или я должен пойти на ведение хеш-таблицы для моих записей стека, чтобы облегчить это решение.?Иначе говоря, насколько затратны операции со стеком? .. *

   Еще одна вещь в модели плоской памяти, такой как LINUX, было бы абсолютно неправильно увеличивать размер предварительно выделенного стека по мере необходимости (скажем, посредством realloc)?1013 *

Answer 1

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