Изменения

Перейти к: навигация, поиск

Стек

7081 байт добавлено, 19:07, 4 сентября 2022
м
rollbackEdits.php mass rollback
== Определение ==
[[Файл: 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>. ==Графическое представление=На саморасширяющемся массиве===Возможна реализация стека на [[ФайлСаморасширяющийся_массив| динамическом массиве]], в результате чего появляется существенное преимущество над обычной реализацией: lifoпри операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения. Создадим вектор и определим операции стека на нём.pngВ функции <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 '''T''' newStack[capacity * 2] '''for''' i = 0 '''to''' capacity - 1 newStack[i] = s[i] s = newStack capacity = capacity * 2 head++ s[head] = element  '''T''' pop(): temp = s[head] head-- '''if''' head < capacity / 4 '''T''' newStack[capacity / 2] '''for''' i = 0 '''to''' capacity / 4 - 1 newStack[i] = s[i] s = newStack capacity = capacity / 2 '''return''' temp ===На списке===Стек можно реализовать и на [[Список |trumb|300px|Простое представление стекасписке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <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)  '''T''' pop(): data = head.data head = head.next '''return''' data В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(n)</tex> дополнительной памяти на указатели в списке.
== См. также ==
* [[Очередь]]
* [[Персистентный стек]]
== Ссылки Источники информации ==* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1* [http://rucomp-science.wikipedianarod.orgru/wikiProgr/СтекStack.htm Динамические структуры данных: стеки][[Категория:Дискретная математика и алгоритмы]][[Категория:Амортизационный анализ]][[Категория:Структуры данных]]
1632
правки

Навигация