Поиск из стека

Question

Я внедряю стек, и, хотя реализовать базовые операции push и pop было не сложно, мне интересно, как реализовать несколько эффективный поиск. Базовая структура представляет собой связанный список

Answer 1

В своей базовой форме стек допускает только медленный линейный поиск. То есть, если в стеке есть n элементов, вам нужно поискать все n (в среднем 1/2 n), чтобы найти совпадение. Если ваш стек относительно мал, этот линейный (один за другим) поиск может не иметь большого значения.

Однако, если у вас гораздо больший набор, вы можете объединить две структуры данных, чтобы сделать поиск более эффективным: например, у вас может быть хеш-таблица в дополнение к стека: Каждый раз, когда вы помещаете что-то в стек, вы также можете добавить это в хеш-таблицу. И наоборот, когда вы удаляете его из стека, вы можете удалить его из таблицы. Хеш-таблицы обеспечивают относительно быстрый поиск даже при очень больших наборах данных, поэтому поиск может быть довольно быстрым.

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

Другая похожая возможность заключается в использовании «мультикарты» - она ​​похожа на хеш-таблицу, но позволит легче обрабатывать дубликаты.

Answer 2

Если вам нужно проверить какой-либо предмет в стеке, кроме предмета наверху, вам, вероятно, не следует использовать стек для хранения ваших предметов. Пересмотрите выбор вашей структуры данных.

Answer 3

Стек не предназначен для поиска. Конечно, вы можете легко реализовать поиск по основному связанному списку и предоставить его пользователю - но это уже не стек.

Линейный поиск в связанном списке может выглядеть следующим образом:

listentry* first;

for(first = head; (first=first->next);) {
  if (first->val == value_to_search) {
     // have a match
     return 1;
  }
}
return 0;

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

Answer 4

Вы не упомянули, реализовали ли вы постоянный стек (push и pop, возвращающие новые стеки, пока стек аргументов продолжает существовать) или изменяемый стек (стек, переданный push и pop, изменено на месте).

В любом случае самые глубокие значения - это те, которые меняются реже всего, поэтому стратегия ускорения поиска будет заключаться в том, чтобы кэшировать результаты предыдущих поисков по самым глубоким 2, 4, 8, ... элементам стеков. Вы справляетесь. Если вы реализовали изменяемый стек, аннулируйте кеш соответствующим образом (аннулируйте записи в кэше для первых 2 ^ n элементов, когда глубина стека опустится ниже 2 ^ n).