Изменения

'''Стек''' (от англ. ''stack '' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) Примером стека в реальной жизни как, например, удерживаемые пружиной стопки может являться стопка тарелок: когда мы хотим вытащить тарелку, используемые в кафетериях, мы должны снять все тарелки выше. Вернемся к описанию операций стека:* <tex> \mathtt{empty} </tex> {{---}} порядок вытаскивания (проверка стека на наличие в нем элементов,* <mathtex> \mathrm mathtt{poppush} </mathtex>(запись в стек) тарелок из стопки обратен порядку их в неё помещению ({{---}} операция вставки нового элемента,* <mathtex> \mathrm mathtt{pushpop} </mathtex>), и лишь (текущаяснятие со стека) верхняя тарелка может быть извлечена{{---}} операция удаления нового элемента.

<wikitex>Для стека с $<tex>n$ </tex> элементами требуется $<tex>O(n)$ </tex> памяти, так как она нужна лишь для хранения самих элементов.</wikitex>

Перед реализацией стека выделим ключевые поля:* <wikitex>Операция вставки нового элемента применительно к стекам часто называется <mathtex> \mathrm mathtt{pushs[1\dots n]} </mathtex> (запись в стек), а операция удаления {{---}} <math> \mathrm {pop} </math> (снятие со стека). Стекмассив, с помощью которого реализуется стек, способный вместить не более $<tex>n$ </tex> элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S* <tex>\mathtt{s.top]$, где $S[1]$ {{---}} элемент на дне стека, а $S[S.top]$ </tex> {{---}} элемент на его вершинеиндекс последнего помещенного в стек элемента.

Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.Если $S<tex>\mathtt{s.top = 0$}</tex>, то стек не содержит ни одного элемента и является пустым $(англ. ''empty'')$. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}}запроса <mathtex> \mathrm mathtt{stackEmpty} </mathtex>. Если элемент снимается с пустого стека, говорят, что он опустошается $(англ. ''underflow'')$, что обычно приводит к ошибке. Если значение $S<tex>\mathtt{s.top$ }</tex> больше $<tex>\mathtt{n$}</tex>, то стек переполняется $(англ. ''overflow'')$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

'''booleanfunction''' stackEmptypush(S)element : '''if''' S.top == 0 '''return''' 'T''true''' '''else''' '''return''' '''false''' '''function''' push(S, x): Ss.top = Ss.top + 1 Ss[Ss.top] = xelement '''T''' pop(S): '''if''' stackEmptyempty(S)

Ss.top = Ss.top - 1 '''return''' Ss[Ss.top + 1] Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.

Как видно из псевдокода выше===На саморасширяющемся массиве===Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], все в результате чего появляется существенное преимущество над обычной реализацией: при операции со стеком выполняются push мы никогда не сможем выйти за $Oграницы массива, тем самым избежим ошибки исполнения. Создадим вектор и определим операции стека на нём. В функции <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 /wikitex>2] '''for''' i = 0 '''to''' capacity / 4 - 1 newStack[i] = s[i] s = newStack capacity = capacity / 2 '''return''' temp

<wikitex>Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <mathtex> \mathrm mathtt{push} </mathtex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <mathtex> \mathrm mathtt{pop} </mathtex> будет текущая голова. После вызова функции <mathtex> \mathrm mathtt{push} </mathtex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <mathtex> \mathrm mathtt{pop} </mathtex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.Заведем конструктор вида ListItem(ListItem next, T data)

Заведем конструктор вида <code>ListItem(next : '''ListItem''', data : '''T''')</code> Ключевые поля:* <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека,* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека.  '''function''' push(element: '''T'''): newHead head = ListItem(head, element) head = NewHead

В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же $n$. Стоит заметить, что, хотя общая оценка затрачиваемой памяти $O(n)$, в ней скрыта бóльшая константа, и реализация на списке требует несколько больше памяти.</wikitex> ===На саморасширяющемся массиве===<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции <mathtex> \mathrm mathtt{pushn} </mathtex> Перед тем. Стоит заметить, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в что стек требует <mathtex> \mathrm {pop} </math>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.  '''function''' pushO(e): '''if''' n == s - 1 w = new int[s * 2] '''for''' i = 0 '''to''' s w[i] = v[i] v = w s = s * 2 n++ v[n] = e  '''T''' pop(): r = n n-- '''if''' n < size / 4 w = new int[size / 2] '''for''' i = 0 '''to''' size / 4 w[i] = v[i] v = w size = size / 2 '''return''' v[r]</wikitextex>дополнительной памяти на указатели в списке.

== Ссылки Источники информации ==