Является ли FIFO в очереди эквивалентно LILO? - PullRequest
Новая
       43

Является ли FIFO в очереди эквивалентно LILO?

0 голосов
/ 16 мая 2019

Я немного запутался здесь.

В статье сказано:

Очередь - это линейная структура, которая следует определенному порядку, в котором выполняются операции. Порядок «первым пришел - первым вышел» (FIFO). Хорошим примером очереди является любая очередь потребителей для ресурса, где первым обслужен потребитель, который пришел первым. Разница между стеками и очередями заключается в удалении. В стеке мы удаляем элемент, который был добавлен последним; в очереди мы удаляем элемент, наименее добавленный недавно.

Правильно ли говорить, что FIFO (первый пришел, первый вышел) такой же, как LILO (последний пришел, последний вышел)?

А для стеков: это то же самое, что LIFO (последний пришел, первый вышел) и FILO (первый пришел, последний вышел)?

Но никто никогда не использует LILO и FILO.

1 Ответ

1 голос
/ 16 мая 2019

Да, в случае как стеков, так и очередей, соглашение об именовании является технически точным.

Рассмотрим очередь размера 4. Мы ставим в очередь «o», затем ставим в очередь «x», и они помещаются в очередь в соответствующем порядке. 

     +---+---+---+---+
Back |   |   | x | o | Front
     +---+---+---+---+

Когда мы снимаем очередь, ближайший к фронту элемент удаляется из очереди, а остальная часть очереди «движется вверх», чтобы выглядеть следующим образом: 

     +---+---+---+---+
Back |   |   |   | x | Front (o dequeued)
     +---+---+---+---+

В этом абстрактном примере "o" - это первый элемент, который должен быть помещен в очередь (первый вход), и первый элемент, который должен быть снят (первый выход).

Затем мы можем снова удалить из очереди и получить x. 

     +---+---+---+---+
Back |   |   |   |   | Front (x dequeued)
     +---+---+---+---+

Теперь из этой очереди легко увидеть, что "x" - это последний элемент, который будет помещен в очередь (последний в), и последний элемент, который будет помещен в очередь (последний в).

Следовательно, FIFO и LILO являются эквивалентной терминологией.

Для краткости приведу пример для стека: 

+---+    +---+    +---+
|   |    |   |    |   |
+---+    +---+    +---+
|   |    |   |    |   |
+---+    +---+    +---+
|   |    | x |    |   |
+---+    +---+    +---+
| o |    | o |    | o |
+---+    +---+    +---+
Push o   Push x   Pop

На втором шаге «x» становится последним элементом, помещенным в стек (последним в). Затем, когда мы выскакиваем, верхний элемент стека удаляется, что по-прежнему равно «x» (последний раз).

Если бы мы всплыли во второй раз, нам бы дали «о». Этот элемент был первым и последним удаляемым элементом. Следовательно, поведение может быть описано как LIFO, так и FILO.

Что касается того, почему одно соглашение об именах используется поверх другого, - ("/) -

...