(или магазин) — структура данных в программировании, работающая по принципу магазина с патронами: последний помещеннный в него объект, обрабатывается первым.
Приработе со стекам часто приходится сталкиваться с двумя типичными ошибками: переполненем стека и опустошением стека.
Переполнение стека (stack overflow) — одна из типичных ошибок при работе со стеком, состоящая в попытке добавить в стек элемент, когда память, отведенная для хранения стека полностью занята.
В случае, если стек моделируется на базе массива, добавляемое значение может быть записано за пределы отведенного для хранения стека памяти, что приведет к повреждению другие данных, обрабатываемых программой. Это нередко приводит к трудно выявляемым ошибками типа "порчи памяти". Поэтому при реализации стека на основе массива необходимо перед каждой операцией добавления элемента проверять, не переполнен ли стек.
Если стек моделируется на связанном списке, то переполнение стека обычно возникает только при исчерпании доступной для программы оперативной памяти. В этом случае программа завершается с диагностикой "Недостаточно памяти".
Причиной переполнения стека обычно является зацикливание на участке программы, где количество операций добавления в стек превышает количество операций извлечения из стека. Другая причина переполнения стека — слишком большая глубина рекурсивных вызовов подпрограмм, что может говорить о неудачно выбранном алгоритме решения задачи.
Опустошение стека (stack underflow) — другая типичная ошибка при работе со стеком, состоящая в попытке извлечь значение пустого стека.
В случае, если стек моделируется на базе массива, то при его опустошении в качестве результата операции может быть возвращено случайное ("мусорное") значение из области памяти, не отведенной для хранения стека. Это скорее всего приведет к неверной работе программы. Кроме того, при попытке пополнить стек после его ошибочного опустошения, данные могут быть записаны в постороннюю область памяти, что приведет к тем же непредсказуемым последствиям, что и переполнение стека.
Если стек моделируется на связанном списке, то ошибка опустошения стека выражается в попытке обращения по недействительному указателю. Обычно это немедленно приводит к завершению программы с диагностикой "защита памяти".
Причиной опустошения стека обычно является зацикливание на участке программы, где количество операций извлечения из стека превышает количество операций добавления в стек. Другая причина переполнения стека — несогласованность операций пополнения и извлечения из стека. Например, если подпрограмма ожидает получить больше параметров, чем ей передается при вызове через стек.
Чтобы избегать ошибок при работе со стеком нужно следовать двум правилам.
1. При реализации операций со стеком всегда проверять, не приведет ли затребованное действие к переполнению или опустошению стека. Если нарушение обнаружено, то выдавать соответствующую диагностику и отказывать в выполнении операции.
2. При каждой операции использования стека проверять успешность ее, выполнения и в случае возникновения ошибки принимать соответствующие меры.
Описанные правила безопасности приводят к тому, что программный код оказывается перегружен проверками. По этой причине более эффективным методом является уведомление об ошибках в работе со стеком при помощи механизма исключений или прерываний (например, конструкция try ... throw в языке С++).
Дополнительно в базе данных Генона:
Ссылки по теме:
- — реализация стека на С++ с использованием исключений
- — Википедия: Переполнение буфера
- — рассматривается уязвимость Windows за счет использования переполнения стека
- — статья «Переполнения стека»
- — статья «Переполнение буфера в стеке», Хакер, №2, 2003