215
правок
Изменения
Стек
,→На массиве
Для стека с <tex>n</tex> элементами требуется <tex>O(n)</tex> памяти, так как она нужна лишь для хранения самих элементов.
===На массиве===
Операция вставки нового элемента применительно к стекам часто называется <tex> \mathrm {push} </tex> (запись в стек), а операция удаления {{---}} <tex> \mathrm {pop} </tex> (снятие со стека). Стек, способный вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>S s [1..n]</tex>. Этот массив обладает атрибутом <tex>Ss.top</tex>, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов <tex>Ss[1..Ss.top]</tex>, где <tex>Ss[1]</tex> {{---}} элемент на дне стека, а <tex>Ss[Ss.top]</tex> {{---}} элемент на его вершине.
Если <tex>Ss.top = 0</tex>, то стек не содержит ни одного элемента и является пустым <tex>(empty)</tex>. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}}запроса <tex> \mathrm {stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается <tex>(underflow)</tex>, что обычно приводит к ошибке. Если значение <tex>Ss.top</tex> больше <tex>n</tex>, то стек переполняется <tex>(overflow)</tex>. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
'''boolean''' stackEmpty(Ss): '''if''' Ss.top == 0
'''return''' '''true'''
'''else'''
'''return''' '''false'''
'''function''' push(Ss, x): Ss.top = Ss.top + 1 Ss[Ss.top] = x
'''T''' pop(Ss): '''if''' stackEmpty(Ss)
'''return''' error "underflow"
'''else'''
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
===На списке===
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathrm {push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathrm {pop} </tex> будет текущая голова. После вызова функции <tex> \mathrm {push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathrm {pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
