Порядок хранения данных в стеке - PullRequest
0 голосов
/ 14 июня 2010

Говоря о стеке в вычислительной или "реальной" жизни, мы обычно подразумеваем функциональность типа "сначала включен, последний выключен".

Поскольку идея стека основана на чем-то физическоммир, имеет ли значение, как хранятся данные в стеке?

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

В качестве парадигмы, имеет ли значение, в каком порядке данные хранятся в стеке, покакак работа стека действует как положено?

Ответы [ 3 ]

0 голосов
/ 14 июня 2010

Неважно, как вы храните ваши данные в памяти, если функциональность и производительность соответствуют ожиданиям.

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

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

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

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

0 голосов
/ 14 июня 2010

Как парадигма, нет, не совсем.Что касается низкоуровневой реализации, стек, который растет вниз, имеет небольшое преимущество в том, что элементы, уже находящиеся в стеке, могут быть адресованы из текущего указателя стека с использованием положительного смещения (например, это может быть полезно для некоторых архитектур ЦП).

0 голосов
/ 14 июня 2010

Не совсем. Однако, поскольку нет вычислительного преимущества (как правило) для перемещения перемещаемых элементов в любую другую позицию, линейная структура (которая может обеспечить быстрый доступ к текущей «вершине» стека) работает так же, как и все остальное. Массив отвечает требованиям структуры стека с точки зрения производительности и компактности, поэтому он обычно является лучшим / очевидным выбором.

...