Структуры данных

Основные структуры данных условно делятся на:

1. Список
2. Стек
3. Очередь
4. Множество

1. Список

Список — это упорядоченный набор элементов, для каждого из которых хранится указатель на следующий (или для двусвязного списка и на следующий и на предыдущий) элементы списка. Иногда называется sequence. Элементы в списке могут повторяться. Одна  из важных особенностей списка - это наличие индекса у каждого элемента.

На рисунке ниже представлена коллекция, в которую добавлены буквы А, B, C, A, A. Как вы видите, буква А добавлена несколько раз - это разрешается в списках. Каждая буква отмечена индексом.

2. Стек

Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это значит, что мы будем иметь доступ только к последнему добавленному элементу. Стек разрешает повтор одинаковых элементов.

Хорошим примером стека является стопка тарелок - верхняя тарелка была добавлена последняя в стопку (Last-In), но забрать ее можно будет первой (First-Out). Самая нижняя тарелка напротив была добавлена первой, но убрать ее можно будет только после удаления всех верхних тарелок. Получить доступ к тарелкам в середине стопки нельзя без удаления верхних тарелок.

Кстати, структура памяти стек организована по этому же принципу - Стуктура памяти.

3. Очередь

Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы помещаются (enqueue) и забираются (dequeue) с разных концов.  У очереди выделяют хвост и голову. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). То есть забирать элементы из очереди мы будем в том же порядке, что и помещали. Как реальная очередь или конвейер. Очереди также разрешают повторы элементов.

4. Множество

Множество — неупорядоченный набор элементов, без повторов. Хорошим примером множества являются автомобили на парковке - каждое авто имеет уникальный номер, и нет необходимости их упорядочивать.