что такое барьер? (структуры данных)

#алгоритм #структуры_данных #терминология

По предмету "Алгоритмы и структуры данных" дали задание создать:


  Структуру данных для организации линейного односвязного списка
  
  Структура данных: очередь (FIFO)  с барьером. 
  
  Представление памяти - динам. память.


Все, в принципе понятно, кроме барьера.

Кто то может простым языком объяснить, что это, и с чем его едят?
    

Ответы

Ответ 1

У вас имеется линейный неупорядоченный список элементов, а именно, в данном случае
- FIFO (не будем заморачиваться с тем, что такая структура хранения данных - это очередь,
будем называть списком).

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

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

В вашем же случае с FIFO (First In, First Out) придется добавлять барьерный элемент
в список самым последним в связи с порядком обхода данного списка, а затем при обходе
списка проверять не является ли текущий элемент барьером, т.е. вы должны заранее знать
значение барьера.