Изменения

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

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

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

Стек состоит из элементов <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'')$. Протестировать стек на наличие в нем элементов можно с помощью операции{{---}} запроса $Stack$_$Empty$<tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается $(англ. ''underflow'')$, что обычно приводит к ошибке. Если значение $S<tex>\mathtt{s.top$ }</tex> больше $<tex>\mathtt{n$}</tex>, то стек переполняется $(англ. ''overflow'')$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

Stack_Empty(S) if S.top == 0=На саморасширяющемся массиве=== return trueВозможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения. else return false Создадим вектор и определим операции стека на нём. В функции <tex> \mathtt {push(S} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathtt {pop} </tex>, перед тем, как изъять элемент из массива,x) S{{---}} не нужно ли вдвое сузить размер вектора.top = SНиже приведён пример реализации на векторе.top +  Ключевые поля:* <tex>\mathtt{s[0\dots n-1]}</tex> {{---}} старый массив, в котором хранится стек, S* <tex>\mathtt{newStack[S0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,* <tex>\mathtt{head}</tex> {{---}} верхушка стека,* <tex>\mathtt{capacity}</tex> {{---}} размер массива.top] = x pop'''function''' push(Selement : '''T'''): '''if Stack_Empty(S)''' head == capacity - 1 return error "underflow" '''T''' newStack[capacity * 2] else S.top '''for''' i = S.top 0 '''to''' capacity - 1 return S newStack[i] = s[S.top i] s = newStack capacity = capacity * 2 head++ 1 s[head]= element

Как видно из псевдокода выше, все операции со стеком выполняются за $O '''T''' pop(1)$.: 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 /wikitex>2 '''return''' temp

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

pushЗаведем конструктор вида <code>ListItem(elementnext : '''ListItem''', data : '''T''') OldHead = head NewHead.data = element NewHead.next = OldHead head = NewHead</code>

pop()Ключевые поля: int element = * <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека, head = * <tex>\mathtt{head.next return element}</tex> {{---}} значение следующее за верхушкой стека.

В реализации на списке '''function''' push(element : '''T'''): head = ListItem(head, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов.</wikitex>element)

'''T''' pop(): data =head.data head ==На саморасширяющемся массиве===head.next<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции $push$ Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в $pop$, перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе. '''return''' data

struct vector int sizeВ реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n int* v int* w vector() size = 1 n = 0 v = new int[1] pop() int r = *(v + n) n-- if (n }< size / 4) w = new int[size / 2] for i = 0tex>..size / 4 w[i] = v[i] delete[] v v = w size = size / 2 return r push(e) if Стоит заметить, что стек требует <tex>O(n == s - 1) w = new int[s * 2] for i = 0..s w[i] = v[i] delete[] v v = w s = s * 2 n++ v[n] = e</wikitextex>дополнительной памяти на указатели в списке.

== Ссылки Источники информации ==*Википедия**[http[wikipedia://ru.wikipedia.org/wiki/:Стек |Википедия {{---}} Стек]]