Итерация по стекам и очередям?

Итерация по стекам и очередям?
Итерация по стекам и очередям? - markusspiske @ Unsplash

Можно ли концептуально итерировать стеки и очереди?

По какой-то причине это "кажется неправильным", но я не могу придумать причину, почему было бы плохо просматривать все, что сложено в стек/очередь. Очевидно, что нельзя вынуть элемент оттуда или вставить новый где-то между ними.

Мне кажется, или существует хорошее объяснение того, почему вам следует или не следует разрешать итерацию содержимого стека/очереди только для чтения?

"Стек" и "очередь" - это термины, которые иногда используются для обозначения двух разных вещей, логических и физических.

В строгом смысле, это логические понятия, и по определению доступ к ним осуществляется только определенным образом, либо путем чтения головы или хвоста потока FIFO или LIFO.

В практическом смысле это физические структуры данных. Например, в c# существуют классы Stack<T> и Queue<T> (наряду с дружественными к параллельным вычислениям версиями). Для практических целей эти классы имеют перечислители, позволяющие видеть все содержимое, а также свойства индексатора, позволяющие произвольный доступ к любому элементу в любом порядке.

Есть некоторые ситуации, когда этого делать не следует. Например, допустим, вы изобрели новый язык, оптимизированный для чтения баз данных. Набор результатов может быть представлен в виде очереди, доступной только для чтения, которая итерируется по курсору на стороне базы данных. В этом случае произвольный доступ к элементам очереди будет серьезной проблемой, потому что вы не сможете переместить курсор со стороны базы данных назад.

Другой пример - стек вызовов процессора. Это структура LIFO, к которой буквально невозможно получить произвольный доступ, потому что каждый элемент в стеке имеет свой размер, и нет способа выяснить его размер без обратной разработки каждой подпрограммы. Код способен эффективно использовать этот стек только потому, что каждая подпрограмма знает, как деаллоцировать свой собственный кадр стека.

Так что на логическом уровне вы правы - очереди и стеки читаются определенным образом, по определению. На физическом уровне иногда хорошо использовать случайный доступ, но иногда это не хорошо, а иногда это невозможно.


LetsCodeIt, 5 января 2023 г., 17:02

Похожие посты

Каково большое O этого алгоритма?Почему счетчик не используется для того, чтобы избежать вложенных циклов for для операций, основанных на индексах?Докажите, что выражение может создавать дубликатыЕсть ли название для функции, которая выводит больше данных, чем было в нее заложено?Рассчитать время работы и время установки или себестоимость на основе переменного набора параметров. Шаблон проектирования?Как B-дерево используется в СУБД, если условие WHERE может быть любым?Требуется помощь в выборе правильной структуры данных для более быстрого поиска данныхПочему так много стандартов для форматов ответов JSON API содержат свойство "success" в теле ответа вместо того, чтобы просто использовать коды состояния HTTP?Почему в C++ нет Hashmap, как в Java?Класс данных: распределить кодовую таблицу для каждой базы данных по нескольким копиям класса или усложнить исходный класс?