LIFO и FIFO
Терминология, пришедшая в IT из бухучета. Так называют подходы к организации данных.
FIFO (First In, First Out, «первый пришел – первый ушел») – поведение как в очереди в магазине. Ему соответствует структура данных очередь). У такого хранилища две операции: enqueue – добавить элемент в конец, и dequeue – забрать из начала.
LIFO (Last In, First Out, «последний пришел – первый ушел» – наоборот, первый пришедший ждет всех остальных, подобно стопке тарелок. Соответственно, его реализует структура данных стек. Операция push кладет новый элемент наверх стопки, pop забирает сверху же.
Термины применяются не только к способу доступа к данным, но и к порядку разрешения конфликтов. Так, например, по принципу LIFO или FIFO может определяться порядок исполнения параллельно пришедших сигналов какой-либо системы: доступа к диску, планировки задач ОС, и прочих.
#Структуры
Терминология, пришедшая в IT из бухучета. Так называют подходы к организации данных.
FIFO (First In, First Out, «первый пришел – первый ушел») – поведение как в очереди в магазине. Ему соответствует структура данных очередь). У такого хранилища две операции: enqueue – добавить элемент в конец, и dequeue – забрать из начала.
LIFO (Last In, First Out, «последний пришел – первый ушел» – наоборот, первый пришедший ждет всех остальных, подобно стопке тарелок. Соответственно, его реализует структура данных стек. Операция push кладет новый элемент наверх стопки, pop забирает сверху же.
Термины применяются не только к способу доступа к данным, но и к порядку разрешения конфликтов. Так, например, по принципу LIFO или FIFO может определяться порядок исполнения параллельно пришедших сигналов какой-либо системы: доступа к диску, планировки задач ОС, и прочих.
#Структуры
Связный список
Он же просто «список», самая простая после массива структура данных. Каждый элемент данных хранится в ячейке вместе со ссылкой на следующую. Таким образом, ячейки данных выстраиваются в цепочку.
В пользовательском коде сохраняется адрес «головы» списка – первой ячейки. От нее по ссылкам можно дойти до любого элемента «хвоста».
В отличие от простого массива, информация в списке разрозненна в памяти, что делает кэширование процессора менее эффективным. На хранение ссылок тратится дополнительная память. Взамен, список дает возможность вставки/удаления элемента в середине без перезаписывания остальных элементов.
Для ускорения доступа к последним элементам, а также для обхода данных с конца существует модификация, которая называется двусвязный список. В нём каждая ячейка хранит ссылку и на следующую, и на предыдущую.
Сложность поиска по значению и по индексу так же как и модификации в середине – линейная; любых действий с головным элементом – константная.
#Структуры
Он же просто «список», самая простая после массива структура данных. Каждый элемент данных хранится в ячейке вместе со ссылкой на следующую. Таким образом, ячейки данных выстраиваются в цепочку.
В пользовательском коде сохраняется адрес «головы» списка – первой ячейки. От нее по ссылкам можно дойти до любого элемента «хвоста».
В отличие от простого массива, информация в списке разрозненна в памяти, что делает кэширование процессора менее эффективным. На хранение ссылок тратится дополнительная память. Взамен, список дает возможность вставки/удаления элемента в середине без перезаписывания остальных элементов.
Для ускорения доступа к последним элементам, а также для обхода данных с конца существует модификация, которая называется двусвязный список. В нём каждая ячейка хранит ссылку и на следующую, и на предыдущую.
Сложность поиска по значению и по индексу так же как и модификации в середине – линейная; любых действий с головным элементом – константная.
#Структуры
❤1