Изменения

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

Перед реализацией стека выделим ключевые поля:* <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Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(S1)</tex>. 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[S.top i] = s[i] s = newStack capacity = capacity * 2 head++ 1 s[head]= element

Как видно из псевдокода выше, все операции со стеком выполняются за $O '''T''' pop(1)$. Память требуется только для хранения самих элементов, т.е. необходимо $O(n)$ памяти.: 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> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой. Заведем конструктор вида <code>ListItem(next : '''ListItem''', data : '''T''')</code>

struct ListItemКлючевые поля: int data ListItem* next ListItem() <tex>\mathtt{head.data = }</tex> {{-1 next = NULL struct Stack ListItem* head Stack() head = new ListItem() void push(int element) ListItem* NewHead = new ListItem() ListItem* OldHead = new ListItem() OldHead = head; NewHead->data = element NewHead->next = OldHead}} значение в верхушке стека, head = NewHead; pop() int element = head-* <tex>data \mathtt{head = head->.next return element}</wikitextex>{{---}} значение следующее за верхушкой стека.

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