Что такое стек ?

← →
Top Gun (2003-04-07 19:42) [0]

Собственно говоря, сабж.
Очень часто используется это слово, значение которого для меня непонятно. Пытаюсь освоить вещи, где нужно знать, что это такое. Буду очень рад за разъяснения или за линки на соответствующую литературу

P.S. Не совсем в тему: если локальные переменные хранятся в стеке, то где хранятся глобальные переменные?

← →
Anatoly Podgoretsky (2003-04-07 19:44) [1]

Стек это стопка, типа стопки бумаги, сверху ложишь, в обратном порядке снимаешь.

← →
malkolinge(fp) (2003-04-07 20:04) [2]

стек - это такая коробка из которой достаешь что положил :))). Если дно запечатано, то первым достаешь то что положил последним, если доставать через дно то что запихал первым, то первым и достанешь
(C)
MikeGoblin

← →
malkolinge(fp) (2003-04-07 20:09) [3]

А еще справку посмотри по Tstack Делфийскому...Если что не ясно...заходи в аську поговорим

← →
MAN-IN-RED (2003-04-07 20:27) [4]

Стек, это почти тоже самое, что и комб (гитарный усилитель), только голова и кабинеты в разных ящиках, и он на колесиках…

← →
MAN-In-RED (2003-04-07 20:29) [5]

Упс, а по-моему это не с той оперы… :)

← →
shane54 (2003-04-07 20:58) [6]

Я бы еще добавил, что если есть представление, что такое FIFO и LIFO, то стек - это FIFO.

P.S. FIFO - Firs In First Out, LIFO - Last In First Out.

← →
Плохой человек (2003-04-07 21:29) [7]

Да в Windows о стеке лучше не знать.

← →
Top Gun (2003-04-07 21:59) [8]

А можно поподробнее, а то мне легкче что-то не стало ;((

← →
Иван Шихалев (2003-04-07 22:08) [9]

> Я бы еще добавил, что если есть представление, что такое
> FIFO и LIFO, то стек - это FIFO.

Это очередь - FIFO, а стек - как раз LIFO.

← →
Иван Шихалев (2003-04-07 22:09) [10]

to Top Gun

Настоятельно советую почитать что-нибудь по основам программирования. С такой базой далеко не уедешь.

← →
nikkie (2003-04-08 13:37) [11]

Во-первых, действительно надо бы тебе почитать про разные структуры данных. Это достаточно просто - вопрос общих концепций и общепринятой терминологии. Поищи в инете "стек, дек, очередь, список, LIFO, FIFO" - наверняка найдешь учебные материалы.

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

stack
A region of reserved memory in which applications store status data such as procedure and function call addresses, passed parameters, and sometimes local variables.
(Честно говоря, объяснить почему sometimes не могу. Могу предположить, что компилятор для языка, не поддерживающего рекурсию может хранить локальные переменные не в стеке.)

Each thread stores the data unique to it in an area of memory called a stack.
(Имеется ввиду служебная информация потока - см. предыдущую цитату. Сам поток может аллокировать память где угодно - в куче, в стеке, в TLS.)

В си память в стеке аллокируется функцией _alloca. Освобождать память аллокированную в стеке не надо, она будет освобождена автоматически при выходе из функции. Как это сделать в дельфи я не знаю и не страдаю, поскольку знаю этому только одно специфичное применение, связанное с использованием макросов.

Размер стека задается параметрами компиляции (в Дельфи - Project/Options, закладка Linker). Если, например, запустить бесконечную рекурсию, то стек будет переполнен - выскакивает сообщение stack overflow.

>где хранятся глобальные переменные
Не в стеке :)
Стек - некоторый специальный кусок адресного пространства данных процесса. Вроде никакого специального названия для неспециального куска адресного пространства данных нет :)

← →
Wild Wizard (2003-04-08 13:59) [12]

algolist.manual.ru -> структуры дынных....

← →
D (2003-04-08 14:10) [13]

Структура данных стек характеризуется тем, что доступен там только последний поступивший в стек элемент. Про этот элемент говорят, что он на вершине стека (top). Над стеком определены такие операции: инициализация, добавление эл-та на вершину стека, взятие элемента с вершины стека (то есть последнего поступившего, который как бы "закрывает" предыдущие эл-ты). Представьте себе обычную детскую игрушку - пирамидку. Надели мы первое кольцо, затем второе, третье. Третье теперь на вершине, оно закрывает все остальные. И взять мы можем только 3-е. Вот Вам аналог стека на пальцах. Именно поэтому для такого метода хранения/учета используют аббревиатуру LIFO - как уже писали - последний пришел (в стек) - первый ушел (из стека).

← →
Top Gun (2003-04-08 18:38) [14]

nikkie, спасибо !

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

← →
nikkie (2003-04-08 19:27) [15]

>А почему стек и рекурсия так связаны ?
Потому что при рекурсивном вызове функции существует столько копий локальных переменных и параметров функций, сколько раз эта функция была вызвана (сколько раз она присутствует в стеке вызовов - его можно в дельфи посмотреть через View / Debug Windows / Call Stack - здесь слово "стек" имеет смысл "пирамидки").

>Почему, если сделать бесконечную рекурсию стек переполнится ?
Потому что если даже локальных переменных и параметров у функции нет, все равно для каждого вызова надо хранить адрес возврата. Рано или поздно память кончится.

← →
Top Gun (2003-04-08 20:42) [16]

Сделал процедуру Loop, которая вызывает сама себя

При запуске из под Дельфе сама Дельфя зависла. При запуске просто exe"шника никаких сообщений - просто программа закрывается.

Никаких сообщений stack overflow

← →
D (2003-04-09 10:24) [17]

Наверное, она сама себя вызывает бесконечно!

← →
Top Gun (2003-04-09 18:43) [18]

Ну да, так и есть, но вроде из слов nikkie следует, что должно вылезти сообщение stack overflow...

← →
Top Gun (2003-04-12 16:44) [19]

но вроде из слов nikkie следует, что должно вылезти сообщение stack overflow, а оно не вылезает !

← →
Top Gun (2003-04-18 00:04) [20]

Удалено модератором
Примечание: Ты слишком много создаешь пустых сообщений

← →
Vlad Oshin (2003-04-18 08:34) [21]

> ?

!

код будет?

← →
Юрий Зотов (2003-04-18 08:54) [22]

Сделайте так (только в опциях проекта на вкладке Compiler отключите птичку оптимизации):

procedure Loop;
var
A: array[0..1023] of byte;
i: integer;
begin
Aplication.ProcessMessages;
for i := 0 to 1023 do A[i] := i div 4;
Loop
end;

Здесь при КАЖДОМ вызове процедуры Loop ее локальные переменные A и i будут размещены в создаваемой компилятором специальной области памяти (в стеке), причем при каждом вызове в одном и том же стеке будут размещены новые экземпляры этих переменных. Таким образом, при каждом вызове Loop от стека "отъедается" чуть больше килобайта, а поскольку стек всего один и его размер фиксирован (см. директиву компилятора $M), то рано или поздно отведенная под стек память закончится и мы получим то самое "stack overflow".

Строка Aplication.ProcessMessages заставляет программу не только заниматься арифметикой, но и обрабатывать поступающие ее окнам сообщения (то есть, окна будут перерисовываться, реагировать на мышь, клавиатуру и т.д.). Это устраняет кажущийся эффект "зависания" программы.

← →
Top Gun (2003-04-19 11:52) [23]

Ага. А "stack overflow" это исключение или как ? Никак не пойму, вроде исключение, но бороться с ним невозможно. То есть программа "умирает" и инчего не поделаешь. Как же бороться с переполнением ?

И чем это грозит, если размер стека сделать очень большим ?

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

← →
JibSkeart (2003-04-19 13:21) [24]

Прочитай книжки по ассемблеру
там обычно все хорошо на эту тему написанно

← →
Юрий Зотов (2003-04-19 13:52) [25]

1. "Stack overflow" - это фатальное исключение, при котором программа далее нормально работать не может. Бороться с ним можно так:
- увеличить размер стека директивой $M;
- аккуратно писать код (например, стремиться обходиться без рекурсий - особенно, если их глубина вложенности может оказаться непредсказуемо большой);
- использовать минимальное число параметров процедур и функций, а в них самих использовать компактные локальные переменные (например, указатели на большие структуры вместо самих структур с динамическим созданием/уничтожением этих структур в самой процедуре - такие структуры будут храниться в куче (heap), а не в стеке).
- любые другие способы, приводящие к сокращению памяти под размещаемые в стеке локальные данные процедур/функций и к уменьшению глубины вложенности вызовов процедур/функций.

2. Память под стек распределяется из общей памяти, отводимой программе. Поэтому, если его размер сделать очень большим, то может не хватить памяти для чего-то другого. В DOS такая опасность была бы довольно реальной, но из-за особенностей адресации размер стека в DOS в принципе не мог превышать 64 Кб (разве что заводить несколько стековых сегментов и переключать их ручками - но это неплохая головная боль для программиста). А вот в Win32 такая опасность практически исключена (потому что довольно трудно представить себе программу, которой бы не хватило бы 2-4 Гб памяти).

3. Динамически увеличивать размер стека не так-то просто. Это связано с перераспределением памяти, изменением значений адресов в самой программе, регистров процессора и прочими премудростями. Еще сложнее написать компилятор, который создавал бы программы с динамическим стеком. Но если даже это и сделать, то итоге эффективность программы будет существенно снижена - а ради чего? Ведь вероятность переполнения стека все же достаточно мала, а если оно все же происходит, то для того и существует директива $M. Да и потом - предположим, программист допустил ошибку и написал бесконечную рекурсию. Что произойдет, если размер стека будет динамически увеличиваться? Правильно, закончится отведенная программе память. Вот только когда - через час, сутки, или через месяц? А при ограниченном и (достаточно малом) размере стека ошибка вывалится практически сразу - и программист получит сигнал, что у него что-то не в порядке.

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

Что такое стек ? Найти похожие ветки