Что значит последовательный участок памяти?

Question

[NoMoneyException]

наткнулся на вот такое вот утверждение

Кроме того, и в стеке, и в очереди используется один последовательный участок памяти

Насколько я понял, здесь имеется ввиду в отличие от списков. Но если я реализую стек через список, разве это не будет противоречить сказанному? Объясните пожалуйста.

Answer 1

[Mercury13]

Один последовательный участок памяти — это значит «последовательные адреса памяти». Таковыми будут массив простой и динамический, строка традиционного устройства, и все структуры памяти, что на них основаны. В том числе простейший стек и кольцевая очередь.

Для чего это нужно?
1. Это ближе к железу: проще код, лучше работает кэш, а значит, быстрее.
2. Некоторые функции, особенно нешаблонные, для своей работы требуют именно последовательных ячеек памяти.

Но если я реализую стек через список, разве это не будет противоречить сказанному?

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

Comments

[NoMoneyException]

То есть настоящий стек - сделан на массиве, а если делать по-другому - это уже эмуляция стека?

[Mercury13]

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

[Mercury13]

У каждого потока стек вызовов свой (переключаясь между потоками, ядро переключается и между стеками). Для основного потока ёмкость стека задаётся при запуске загрузчиком, для остальных — при создании потока.

[Mercury13]

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

[NoMoneyException]

Mercury13: понятно, спасибо :)

[Mercury13]

В x86 регистр ESP — вершина стека. Также зачастую задействован регистр EBP — начало стекового фрейма.

[maaGames]

Mercury13: Не нужно путать стек и стек.)
Есть аппаратный стек, а есть "алгоритмический", который std::stack и аналоги. С аппаратным, кроме названия, ничего общего не имеющий, по большому счёту. Даже принцип работы с ними разный, у аппаратного можно к любому элементу стека доступ получать, а в алгоритмическом только к тому, который на вершине.

Answer 2

[Олег Цилюрик]

наткнулся на вот такое вот утверждение

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

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