Структуры данных и алгоритмы стали проще

В следующий раз, когда вы войдете в столовую или кафетерий (для всех вас, студентов колледжей/университетов…), учтите тот факт, что вокруг вас есть простые структуры данных!

Посмотрите на любую стопку тарелок, мисок или чашек. Когда вы хотите что-то добавить в этот стек, вы кладете что-то сверху, а когда хотите удалить из стека, вы берете что-то сверху. Если вы можете понять, как обрабатываются эти физические стеки, вы сможете легко понять, как работают и обрабатываются компьютерные стеки. Когда вы видите конвейерную ленту, на которую вы ставите свои грязные тарелки и миски для мытья и очистки персонала, поймите, что это на самом деле очередь в реальной жизни! Все, что вы вложите, будет обработано в том порядке, в котором вы вложили вещи. То, что войдет первым, выйдет первым, а то, что войдет последним, выйдет последним.

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

Цель/Отказ от ответственности

Цель этой серии статей («Простые структуры данных и алгоритмы») — помочь всем «любителям обучения» развить интуитивное понимание концепций и тем DSA (структуры данных и алгоритмы). Я убежденный сторонник философии обучения, которую разделяли и Альберт Эйнштейн, и Ричард Фейнман. Эйнштейн однажды сказал: «Если вы не можете объяснить это 6-летнему ребенку, вы сами этого не понимаете». По сути, Фейнман сказал то же самое: «Если вы не можете объяснить что-то простыми словами, вы этого не понимаете. Лучший способ учиться — учить». Я искренне надеюсь, что в процессе написания этих статей я сам укреплюсь в своем концептуальном понимании DSA, и что многие другие также получат пользу от этого интуитивного понимания.

Рассмотрим обычный жизненный сценарий.

Однажды я решаю положить на стол свою греческую Библию Нового Завета. Затем, после этого, я хочу положить еще одну книгу поверх моей греческой Библии Нового Завета. Что, если я решу добавить еще две книги поверх существующей стопки книг?

Если бы я хотел снова получить доступ к моей Библии Нового Завета на греческом языке (не производя слишком много шума и не повреждая книги, роняя их), единственный способ, которым я могу это сделать, — это сначала удалить другие книги, которые находятся поверх нее в стопке. . Я должен снять свой сборник гимнов (который я ставлю последним), затем я должен убрать свою Библию KJV (которую я ставлю предпоследней), затем, наконец, я должен убрать книгу, которую ставлю второй.

Давайте переключим передачу и рассмотрим наших хороших приятелей Джона, Пола, Джорджа и Ринго. Допустим, на блошином рынке в Ливерпуле проходит грандиозная распродажа яблок, и наши приятели хотят получить как можно больше яблок по выгодной цене.

На самом деле им удается попасть на блошиный рынок раньше всех, поэтому, какая бы очередь ни стояла за яблоками, она будет состоять максимум из четырех человек.

Джон, будучи лидером, встает в очередь первым. Однако прежде чем Джон получает шанс выйти на блошиный рынок, остальные его приятели встают в очередь. В очередь входит Ринго, затем Пол и, наконец, Джордж.

Как только все четверо приятелей встанут в очередь, Джон сможет быстро выйти на блошиный рынок. Затем Ринго и Пол могут войти, оставив бедного Джорджа в одиночестве (пока его гитара тихонько плачет…).

Если вы можете понять эти два сценария, вы можете понять стеки и очереди!

Есть несколько терминов, которые нам нужно определить.

Проще говоря, структура данных — это способ организации данных. Некоторые способы организации данных лучше подходят для разных ситуаций, и всегда есть свои плюсы и минусы. И стеки, и очереди являются примерами базовых структур данных.

стек – это структура данных "LIFO", в которой элементы хранятся в виде "вертикальной башни", как в нашем примере с иллюстрацией.

LIFO — это аббревиатура, означающая "последний пришел - первый ушел".

Очередь — это структура данных "FIFO", в которой вы храните элементы в "строке", как в нашем примере с Abbey Road.

FIFO — это аббревиатура, означающая "первым пришел - первым ушел".

Для стеков основными функциями являются "протолкнуть" и "вытолкнуть". «Протолкнуть» означает ДОБАВИТЬ элемент на вершину стека, а «вытолкнуть» — это УДАЛИТЬ элемент с вершины стека. Поскольку стеки представляют собой структуры данных LIFO, чтобы получить доступ к элементам, которые находятся «под» последним элементом, вы должны последовательно «вытолкнуть» все элементы, которые «над» ним, чтобы получить к нему доступ.

Вот очень простая реализация концепции стеков в Python (мой любимый язык программирования).

Для очередей основными функциями являются "удаление" и "добавление" (также могут называться "удаление из очереди" и "постановка в очередь" соответственно). «Удалить» означает удалить элемент, стоящий первым в строке, а «добавить» — добавить элемент в конец строки. Поскольку очереди являются структурами данных FIFO, чтобы получить доступ к элементам, которые являются «последними в очереди», вы должны «удалить» или «удалить из очереди» все элементы, которые находятся «до» в очереди.

Резюме

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

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

Ресурсы

Если вам нужна дополнительная помощь в получении интуитивного понимания стеков и очередей, посмотрите эти видео:

Если вы хотите углубиться в теорию, применение и формальное понимание этих тем, ознакомьтесь со следующими ресурсами: