== Определение ==
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:
* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,
* <tex> \mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,
* <tex> \mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.
'''Стек''' ==Реализации==Для стека с <tex>n</tex> элементами требуется <tex>O(англ. stack — стопкаn) — структура данных с методом доступа к элементам ''LIFO'' (англ. Last In — First Out</tex> памяти, «последним пришёл — первым вышел»)так как она нужна лишь для хранения самих элементов. Чаще всего принцип работы ===На массиве===Перед реализацией стека сравнивают со стопкой тарелоквыделим ключевые поля: чтобы взять вторую сверху* <tex>\mathtt{s[1\dots n]} </tex> {{---}} массив, нужно снять верхнююс помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов,* <tex>\mathtt{s.top}</tex> {{---}} индекс последнего помещенного в стек элемента.
Добавление Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.Если <tex>\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента, называемое также проталкиванием и является пустым (pushангл. ''empty''), возможно только . Протестировать стек на наличие в вершину нем элементов можно с помощью операции {{---}} запроса <tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека , говорят, что он опустошается (добавленный элемент становится первым сверхуангл. ''underflow''), что обычно приводит к ошибке.Удаление элементаЕсли значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, называемое также выталкивание то стек переполняется (popангл. ''overflow''), возможно также только из вершины стека, при этом, второй сверху элемент становится верхним.(В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Стеки широко применяются Каждую операцию над стеком можно легко реализовать несколькими строками кода: '''boolean''' empty(): '''return''' s.top == 0 '''function''' push(element : '''T'''): s.top = s.top + 1 s[s.top] = element '''T''' pop(): '''if''' empty() '''return''' error "underflow" '''else''' s.top = s.top - 1 '''return''' s[s.top + 1] Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>. ===На саморасширяющемся массиве===Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], в вычислительной технике — результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения. Создадим вектор и определим операции стека на нём. В функции <tex> \mathtt {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в частности<tex> \mathtt {pop} </tex>, для отслеживания точек возврата перед тем, как изъять элемент из подпрограмм используется стек вызововмассива, который является неотъемлемой частью архитектуры большинства современных процессоров{{---}} не нужно ли вдвое сузить размер вектора. Язык программирования высокого уровня также используют стек вызовов для передачи параметров при вызове процедурНиже приведён пример реализации на векторе.
Арифметические сопроцессорыКлючевые поля:* <tex>\mathtt{s[0\dots n-1]}</tex> {{---}} старый массив, программируемые микрокалькуляторы используют стековую модель вычисленийв котором хранится стек,* <tex>\mathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,* <tex>\mathtt{head}</tex> {{---}} верхушка стека,* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
'''function''' push(element : '''T'''): '''if''' head ==Работа стека==capacity - 1<wikitex>[ '''T''' newStack[Файл: lifo.png|thumb|right|200px|Стекcapacity * 2]]Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [ '''for''' i = 0 '''to''' capacity - 1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S newStack[1..S.topi]$, где $S= s[1i]$ — элемент на дне стека, а $S s = newStack capacity = capacity * 2 head++ s[S.tophead]$ — элемент на его вершине. = element
Если $S.top '''T''' pop(): temp = s[head] head-- '''if''' head < capacity / 4 '''T''' newStack[capacity / 2] '''for''' i = 0$, то стек не содержит ни одного элемента и является пустым $(empty)$. Протестировать стек на наличие в нем элементов можно с помощью операции'''to''' capacity / 4 -запроса $Stack$_$Empty$. Если элемент снимается с пустого стека, говорят, что он опустошается $(underflow)$, что обычно приводит к ошибке. Если значение $S.top$ больше $n$, то стек переполняется $(overflow)$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.) 1 newStack[i] = s[i] s = newStack capacity = capacity / 2 '''return''' temp
Каждую операцию над стеком ===На списке===Стек можно легко реализовать несколькими строками кодаи на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathtt{push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathtt{pop} </tex> будет текущая голова. После вызова функции <tex> \mathtt{push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathtt{pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой. Заведем конструктор вида <code>ListItem(next :'''ListItem''', data : '''T''')</code> Ключевые поля:* <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека,* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека. '''function''' push(element : '''T'''): head = ListItem(head, element)
Stack_Empty(S) { if S.top == 0 return true; else return false; } push'''T''' pop(S,x): { S.top data = S.top + 1; S[Shead.top] = x; } pop(S) { if Stack_Empty(S)data return error "underflow"; else { S.top head = Shead.top - 1;next '''return S[S.top + 1]; }''' data
Как видно из псевдокода вышеВ реализации на списке, все операции со стеком выполняются за $кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(1n)$.</wikitextex>дополнительной памяти на указатели в списке.
== См. также ==
* [[Персистентный стек]]
== Ссылки Источники информации ==*Википедия**[http[wikipedia://ru.wikipedia.org/wiki/:Стек |Википедия {{---}} Стек]]
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
* [http://comp-science.narod.ru/Progr/Stack.htm Динамические структуры данных: стеки]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Амортизационный анализ]]
[[Категория:Структуры данных]]
