Динамические структуры данных (стек, список, дерево, граф).

 

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

В современных компьютерах стек используется для :
1размещения локальных переменных
2размещения параметров процедуры или функции
3сохранения адреса возврата (по какому адресу надо вернуться из процедуры)
4временного хранения данных, особенно при программировании на Ассемблере

Всего существует 6 основных видов динамических структур данных :

1Стек

2Очередь

3Хэш таблица

4Список (односвязный, двусвязный, циклический)

5Дерево

6Граф

Список
Существует 3 вида списков :
1односвязный (линейный)
2двусвязный
3циклический
Односвязный список похож на очередь, но в отличии от нее при работе со списком можно добавлять элемент в любое его место и при этом испольуется всего один указатель на начало списка.
Двусвязный список.
Многие проблемы при работе с односвязным списком вызваны тем, что в них невозможно перейти к предыдущему элементу. Возникает естественная идея – хранить в памяти ссылку не только на следующий, но и на предыдущий элемент списка. Для доступа к списку используется не одна переменная-указатель, а две – ссылка на «голову» списка (Head) и на «хвост» - последний элемент (Tail).