Изменения

'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) Примером стека в реальной жизни как, например, удерживаемые пружиной стопки может являться стопка тарелок: когда мы хотим вытащить тарелку, используемые в кафетериях мы должны снять все тарелки выше. Вернемся к описанию операций стека:* <tex> \mathtt{empty} </tex> {{---}} порядок вытаскивания тарелок из стопки обратен порядку их проверка стека на наличие в неё помещениюнем элементов, и лишь (текущая) верхняя тарелка может быть извлечена.* <tex> \mathrm mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента.,* <tex> \mathrm mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.* <tex> \mathrm {empty} </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>, то стек не содержит ни одного элемента и является пустым <tex>(англ. ''empty'')</tex>. Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathrm mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается <tex>(англ. ''underflow'')</tex>, что обычно приводит к ошибке. Если значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется <tex>(англ. ''overflow'')</tex>. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

'''boolean''' empty(): '''return''' s.top == 0  '''function''' push(s, elemeentelement : '''T'''):

'''T''' pop(s): '''if''' stackEmptyempty(s)

'''boolean''' stackEmptyКак видно из псевдокода выше, все операции со стеком выполняются за <tex>O(s1): '''return''' s</tex>.top == 0

Как видно из псевдокода выше===На саморасширяющемся массиве===Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], все в результате чего появляется существенное преимущество над обычной реализацией: при операции со стеком выполняются push мы никогда не сможем выйти за <tex>O(1)</tex>границы массива, тем самым избежим ошибки исполнения.

===На списке===Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список Создадим вектор и определим операции работы стека на созданном спискенём. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции В функции <tex> \mathrm mathtt {push} </tex> будут перед головойПеред тем, как добавить новый элемент, будем проверять, сами при этом становясь новой головойне нужно ли расширить массив вдвое, а элементом для изъятия из стека с помощью в <tex> \mathrm mathtt {pop} </tex> будет текущая голова. После вызова функции <tex> \mathrm {push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий перед тем, как изъять элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathrm из массива, {{pop---}} </tex> будет получена и возвращена информация, хранящаяся в текущей головене нужно ли вдвое сузить размер вектора. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головойНиже приведён пример реализации на векторе.

* <tex>head.data\mathtt{s[0\dots n-1]}</tex> {{---}} значение старый массив, в верхушке стекакотором хранится стек,* <tex>\mathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой верхушка стека,* <tex>\mathtt{capacity}</tex> {{---}} размер массива.

'''function''' push(element: '''T'''): newHead '''if''' head = ListItem(= capacity - 1 '''T''' newStack[capacity * 2] '''for''' i = 0 '''to''' capacity - 1 newStack[i] = s[i] s = newStack capacity = capacity * 2 head, element)++ s[head ] = NewHeadelement

data temp = s[head.data] head -- '''if''' head < capacity / 4 '''T''' newStack[capacity / 2] '''for''' i = 0 '''to''' capacity / 4 - 1 newStack[i] = head.nexts[i] s = newStack capacity = capacity / 2 '''return''' datatemp

В ===На списке===Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке, кроме самих данных, хранятся указатели на следующие . Стек будем "держать" за голову. Добавляться новые элементыпосредством операции <tex> \mathtt{push} </tex> будут перед головой, которых столько же, сколько и элементов, то естьсами при этом становясь новой головой, так же а элементом для изъятия из стека с помощью <tex>n\mathtt{pop} </tex>будет текущая голова. Стоит заметитьПосле вызова функции <tex> \mathtt{push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, что, хотя общая оценка затрачиваемой памяти то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex>O(n)\mathtt{pop} </tex>будет получена и возвращена информация, хранящаяся в ней скрыта бóльшая константатекущей голове. Сама голова будет изъята из стека, и реализация на списке требует несколько больше памятиа новой головой станет элемент, который следовал за изъятой головой.

===На саморасширяющемся массиве===Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции Заведем конструктор вида <texcode> \mathrm {push} </tex> Перед тем, как добавить новый элементListItem(next : '''ListItem''', будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathrm {pop} data : '''T''')</texcode>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.

* <tex>s[0\mathtt{head..n-1]data}</tex> {{---}} старый массивзначение в верхушке стека, в котором хранится стек* <tex>newS[0..size*2-1]</tex> \mathtt{{---}} новый массив, в котором хранится стек* <tex>head</tex> {{---}.next} верхушка стека* <tex>size</tex> {{---}} размер значение следующее за верхушкой стека.

'''function''' push(element): '''ifT''' head == size - 1 newS = new int[size * 2] '''for''' i = 0 '''to''' size newS[i] = s[i] s = newS size = size * 2): head++ s[= ListItem(head] = , element)

temp data = head.data head--= head.next '''ifreturn''' head < size / 4data newS = new int[size / 2] '''for''' i = 0 '''to''' size В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</ 4 newS[i] = s[i] s = newS size = size tex>. Стоит заметить, что стек требует <tex>O(n)</ 2 '''return''' s[temp]tex> дополнительной памяти на указатели в списке.

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