Метафоры структур данных,
или добро пожаловать в "Му-му" с порога маршрутки-душегубки
Деревья — сложная структура данных, но объяснять её студентам довольно просто в параллели с обычными живыми деревьями.
Для стека (Stack, LIFO), очереди (Queue, FIFO) и дека (Deque, двусторонний доступ) я придумала другие метафоры.
Так стек и очередь превращаются в поход в кафе "Му-му". Подносы складываются в стек: последний уложенный в стопку поднос берётся первым (LIFO - Last In, First Out). А человек, вставший в очередь первым, обслуживается на кассе также в первую очередь (FIFO - First In, First Out).
Этот скомбинированный пример я придумала ещё во время своей учёбы. Сложнее было с деком, гибридом стека и очереди. И подходящую метафору я внезапно обнаружила лишь на этой неделе.
Для этого я совершила путешествие в своё собственное студенческое прошлое. Приглашаю и вас присоединиться к этому мысленному эксперименту.
Вообразите: провинция. Вы живёте в посёлке Канищево. Вуз Радик находится далеко в городе. Канищево соединяется с городом двумя длинными узкими дамбами. По дамбам ходят маршрутки-душегубки.
И вот утром, в самый час пик вам нужно добраться на пару. На остановку подъезжает маршрутка. У неё 2 двери для пассажиров. Заходить и выходить можно в любую из этих дверей. Денежку соответственно передаём водителю по цепочке.
До того, как маршрутка подошла к вашей остановке, в неё практически до отказа уже успели набиться люди из деревни Семчино. Так что все сидячие места уже заняты, и люди ещё кое-как помещаются в очень узкий проходик между двух рядов сидений. Люди стоят реально, как кильки в бочке.
Залезая в одну из дверей, вы становитесь в начало или в конец очереди относительно движения этой чудо-машины. Но, если вам нужно выйти, и вы, не дай бог, оказались в центре очереди, то вам придётся буквально выталкивать всех людей по очереди слева от себя или справа от себя. По-другому не получится, потому что проходик реально очень узкий.
И вот это, как мне кажется, отличная иллюстрация дека (Double-ended queue, двухсторонняя очередь). А также... одна из главных причин, почему я работаю в Москве.
Интересно, какие ещё можно придумать хорошие метафоры для структур данных?
