Муравьи идут друг за другом по неровной лесной тропе. На их пути встречаются ямки, в которые могут провалиться несколько муравьёв. Когда ямка заполняется муравьями, остальные муравьи проходят через неё, а затем по одному вытаскивают провалившихся. Например, четыре муравья при прохождении ямки вместимостью два муравья меняют порядок с 4321 на 1243. Пусть по тропе идут 8 муравьёв. В каком порядке они будут идти после преодоления участка с четырьмя ямками, вмещающими 2, 4, 5 и 1 муравья соответственно? Какую структуру данных иллюстрирует данный пример? На рисунке исходный порядок показан как 87654321; первым движется муравей 1.
Запись порядка читаем слева направо, как на рисунке: правый муравей идёт первым. Первые муравьи заполняют ямку, следующие проходят мимо, после чего провалившихся вытаскивают в обратном порядке. Это правило стека: последним провалился — первым вышел.
Проследим порядок после каждой ямки. В третьем столбце перечислены муравьи, попавшие в ямку в порядке прихода; при извлечении их порядок обращается.
| Вместимость ямки | Порядок до ямки | Попали в ямку | Порядок после ямки |
|---|---|---|---|
Поясним последний переход: до четвёртой ямки первым шёл муравей
После четырёх ямок:
