On the subject "Algorithms and Data Structures" were given the task to create:

Data structure for organizing a linear singly-linked list

Data structure: queue (FIFO) with a barrier.

Presentation of memory - dynam. memory.

Everything, in principle, is clear, except for the barrier .

Someone can simply explain what it is and what it is eaten with?

  • The first time I hear such a name - maybe you better ask the lecturer what he had in mind? - VladD
  • @VladD No, I heard it once before, now I will try to describe it in the answer. - StateItPrimitive
  • Probably, I mean the sentinel node, which shows the end of the list. And why is the "list representing the queue" and not the "queue implemented as a list"? The first formulation is schizophrenic. - typemoon
  • Yes, really a little schizophrenic, now I will correct it, thanks. - ANU CHEEKI BREEKI

1 answer 1

You have a linear unordered list of elements, namely, in this case - FIFO (we will not bother with the fact that such a data storage structure is a queue , we will call it a list).

One day you will need to search for an item in the list by value, but since the items in it are not ordered, then the search option is only one: complete list traversal elementwise (if, of course, without directly applying sorting before the search).

At each step of the search, you will have to check whether you go beyond the boundaries of your list, and only then compare the current list item with the desired one. There are several ways to verify this fact: one of them is to place a unique element at the end of the list, bumping into which you will be sure that you have reached the end of the list. It is necessary to ensure the uniqueness of this element. Exactly this element will be called a барьером (i.e. you should not look further than that - you went around the whole list).

In your case with FIFO (First In, First Out) will have to add the barrier element to the list most recently in connection with the bypass order of this list, and then, if you go around the list, check whether the current element is a barrier , i.e. you must know in advance the value of the barrier.

  • Thank you clarified. But that's why he is in the queue is not very clear, because the queue for that and the queue that we have access only to the first element ... Although, probably, all the training tasks are not very practical and meaningless .. - ANU CHEEKI BREEKI
  • 3
    @ANUCHEEKIBREEKI Well, a barrier is a somewhat abstract thing. For example, in the pros, if the elements of your list are pointers to nodes ( node 's), then instead of some kind of “special” node element, you can use just nullptr as a barrier (i.e., standard language tools make it easy make and the programmer may not even think about the fact that he applied this approach). - StateItPrimitive
  • one
    @ANUCHEEKIBREEKI At the expense of your question from the comment above directly: yes, you only have access to the first element, which has a link to the second element, and so on, but how do you find out if you went around the list bypassing the list? Either you put a barrier at the end of the list, or, for example, you have a field inside your list that stores the number of list items and each time you add / remove an item to the list, you increase / decrease this field and compare the number of this item before accessing the next list item. in the list with the number of items in it altogether. - StateItPrimitive
  • @VladD Yes, I wrote an explanatory comment at the same time, you were even earlier :) - StateItPrimitive
  • 2
    @zRrr, yes, with the queue sentinel looks artificial, but in the implementation of the rb-tree described here all the leaves of the tree are “sentinel” (sentinel), which greatly simplifies the code. - avp