Стек
Определение
Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Примером стека в реальной жизни может являться стопка тарелок : когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:
- — проверка стека на наличие в нем элементов,
- (запись в стек) — операция вставки нового элемента,
- (снятие со стека) — операция удаления нового элемента.
Реализации
Для стека с элементами требуется памяти, так как она нужна лишь для хранения самих элементов.
На массиве
Перед реализацией стека выделим ключевые поля:
- — массив, с помощью которого реализуется стек, способный вместить не более элементов,
- — индекс последнего помещенного в стек элемента.
Стек состоит из элементов , где — элемент на дне стека, а — элемент на его вершине. Если , то стек не содержит ни одного элемента и является пустым (англ. empty). Протестировать стек на наличие в нем элементов можно с помощью операции — запроса . Если элемент снимается с пустого стека, говорят, что он опустошается (англ. underflow), что обычно приводит к ошибке. Если значение больше , то стек переполняется (англ. overflow). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
boolean empty(): return s.top == 0
function push(element : T): s.top = s.top + 1 s[s.top] = element
T pop():
if empty()
return error "underflow"
else
s.top = s.top - 1
return s[s.top + 1]
Как видно из псевдокода выше, все операции со стеком выполняются за .
На саморасширяющемся массиве
Возможна реализация стека на динамическом массиве, в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.
Создадим вектор и определим операции стека на нём. В функции Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в , перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
Ключевые поля:
- — старый массив, в котором хранится стек,
- — временный массив, где хранятся элементы после перекопирования,
- — верхушка стека,
- — размер массива.
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 / 2]
for i = 0 to capacity / 4 - 1
newStack[i] = s[i]
s = newStack
capacity = capacity / 2
return temp
На списке
Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью будет текущая голова. После вызова функции текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
Заведем конструктор вида ListItem(next : ListItem, data : T)
Ключевые поля:
- — значение в верхушке стека,
- — значение следующее за верхушкой стека.
function push(element : T): head = ListItem(head, element)
T pop(): data = head.data head = head.next return data
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же . Стоит заметить, что стек требует дополнительной памяти на указатели в списке.
См. также
Источники информации
- Википедия — Стек
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
- Динамические структуры данных: стеки
