Часть 0.1. Поясняю за структуры данных (часть 2)⁠⁠

Всем привет, меня зовут Артем и я люблю программировать.

Источник картинки [https://rozetked.me/articles/1336-yandeks-kotiki-i-schenochk...]

Сегодня я хочу рассказать вам о структурах данных: что это, зачем нужны и почему это одна из самых важных составляющих программирования. Также в этой статье рассмотрим три простые структуры — стек(stack), очередь(queue) и связной список(linked list).

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

Что дает знание структур данных?

1) Ваши программы оптимизированы и затрачивают только необходимое количество ресурсов. Многие алгоритмы зависят от правильно подобранных структур данных.(правильно подобранные структуры данных — это только один из методов оптимизации).

2) Вы понимаете, как работает ваш код (или код другого человека)

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

Сами по себе структуры данных — это абстрактные "картонные коробки", в которые вы можете положить и достать свои вещи. В некоторых коробках все вещи могут быть перемешаны, в других — вещи должны быть сложены аккуратно и красиво. Есть коробки, которые достаточно просты по своей структуре — открыл коробку, достал нужную вещь. Но некоторые коробки смогут содержать в себе еще пару коробочек. Иногда в контейнерах нельзя хранить две одинаковые вещи, иногда — можно. В общем, вы должны представлять структуру данных как контейнер, в который можно класть и забирать данные. Как эти данные там хранятся — это уже другой разговор, и в большинстве случаев у вас будут все необходимие инструменты по манипуляции этим данными (вам будет все равно, как эти данные там лежат).

Стек

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

Где применяется эта хрень? Представьте себе, что вы работаете в программе Microsoft Word (для тех, кто не работал, представьте программу Photoshop) [если не работали и там и там, представьте себе любую программу, в которой нажатия клавиш Ctrl + Z отменяет последнее действие]. Так вот, когда вы совершаете какое-либо действие в программе, она закидывает совершенное действие в стек. Самый верхний кирпич стека — это состояние вашего документа\фотографии\чего-либо другого на текущий момент. Когда вы хотите отменить последнее изменение (вернуться на одно действие назад), программа берет самый верхний кирпич(последнее действие) со стека, выбрасывает его и кирпич, который был под ним — теперь самый верхний (теперь он становится текущим состоянием). Сам по себе стек очень прикольная структура данных (хотя иногда ее лучше заменить чем-то другим).

Сложность базовых операций в стеке:

Добавить элемент в стек O(1)

Удалить элемент со стека O(1)

Проверить, пуст ли стек O(1)

Как мы знаем из предыдущей статьи, меньшей сложности, чем O(1), пока не существует, что делает стек очень быстрой и малозатратной(по памяти) структурой данных.

Очередь

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

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

Далее мне нужно было выполнить еще одно условие — слова должны быть в таком порядке, как они были в предложении. И тут мне снова помогла очередь. Я представил предложение как очередь из людей, где каждый человек был отдельным словом. И как только я доходил до конца слова (натыкался на знак пробела), я клал очередь-слово в очередь-предложение. Так у меня вышла очередь из очередей, где каждое слово было на своем месте.

Сложность базовых операций:

Добавить элемент O(1)

Удалить элемент O(1)

Связной список

Связной список

Последняя структура данных на сегодня — связной список. Эта штука мало чем отличается от стандартного массива (просто набор данных, которые доступны по индексу). Главная особенность связного списка это то, что каждая ячейка данных в списке имеет связь со следующей ячейкой (таким образом, только ячейка знает, где находиться ее сосед, идущий после нее). С помощью такой структуры данные могут быть физически разбросаны по оперативной памяти, но логически составлять одну структуру данных. Через связной список можно реализовать много других структур. Сама ячейка содержит в себе данные и указатель на соседа.

Сложность базовых операций:

Добавить элемент O(1)

Удалить элемент O(1)

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

[Еще скоро будет перевод статьи про Arch Linux и его установке рядом с Windows 10]