СпискиСтекОчередьАТДСтруктуры данных
1 мин чтение
Структуры данных: АТД, Массивы, Связные списки, Стек и Очередь
Смежные vs связные структуры данных. Односвязные, двусвязные и кольцевые списки. Стек (LIFO) и Очередь (FIFO). Вычислительная сложность базовых операций.
Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.
Абстрактные типы данных (АТД)
АТД определяет множество значений и набор операций над ними независимо от конкретной программной реализации.
Сравнение смежных и связных структур
| Операция | Динамический массив | Связный список (Linked List) |
|---|---|---|
| Доступ по индексу 0 | 1 (прямой доступ по адресу) | 2 (последовательный проход) |
| Вставка в начало | 3 (сдвиг элементов) | 4 (перепривязка указателей) |
| Вставка в конец | 5 амортизированно | 6 (при наличии tail указателя) |
| Удаление элемента по указателю | 7 (сдвиг) | 8 в двусвязном списке |
| Локальность по кешу (Cache Locality) | Отличная (непрерывная память) | Плохая (узлы разбросаны в куче) |
Стек (LIFO) и Очередь (FIFO)
push(x), pop(), top() за . Применение: вызовы функций (Call Stack), проверка скобочных последовательностей, DFS.enqueue(x), dequeue(), front() за . Применение: BFS, планировщики задач, буферы ввода-вывода.Что дальше?
Закрепите материал задачей: Повторить число.
Изучено — к практике →Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».