Стек
Содержание
- Введение
- Описание структуры данных
- Реализация стека(массив)
- Реализация стека(связный список)
- Сравнение реализаций
Введение
В данной статье рассмотрим структуру данных стек(Stack), реализуем его на языке Go(Golang) и оценим сложность операций используя O-большое.Описание структуры данных
Стек, это структура данных, которая хранит элементы в порядке их добавления, хранение организуется по принципу LIFO(Last-In-First-Out), то есть элементы добавленные последними будут извлекаться в первую очередь. Стек реализует две основные операции добавление и извлечение, может быть реализован на базе массива или с использованием связного списка, в данной статье рассмотрим оба варианта.
Реализация стека(массив)
Для реализации стека на основе массива потребуется массив и индекс указывающий на свободную ячейку доступную для добавления нового элемента.
// Стек реализованный на базе массива, содержит два поля:
// index - индекс указывающий на свободную ячейку доступную для добавления нового элемента
// elements - элементы стека
type Stack[T any] struct {
index int
elements []T
}
Поместить новый элемент в ячейку массива elements с индексом index.
Увеличить значение index на единицу.
В случае, когда значение index достигло границ массива и свободных ячеек нет, создается новый массив большего размера, а все элементы копируются. Далее приведен код реализующий добавление элемента в стек:
// Кол-во элементов, которое будет выделено при достижении границы массива.
const ALLOCATE_SIZE = 10
// Добавление элемента в стек.
// element - новый элемент стека, который будет добавлен на вершину стека
func (stack *Stack[T]) Push(element T) {
// Если указатель добрался до границ массива, необходимо выделить место
// для новых элементов размером ALLOCATE_SIZE
if stack.index >= len(stack.elements)-1 {
allocated := make([]T, len(stack.elements)+ALLOCATE_SIZE)
copy(allocated, stack.elements)
stack.elements = allocated
}
// Добавление нового элемента в массив и сдвиг указателя
stack.elements[stack.index] = element
stack.index++
}
Чтобы извлечь элемент из стека, необходимо сдвинуть index влево на одну позицию. При этом, само значение не удаляется, но отсутствует возможность обращения к этой ячейке массива. Впоследствии значения находящиеся за границей индекса будут перезаписаны новыми элементами.
// Извлечение элемента из стека, возвращает элемент или выбрасывает
// ошибку, если стек пуст.
func (stack *Stack[T]) Pop() T {
// Если указатель больше нуля, извлекаем элемент из стека
if stack.index > 0 {
stack.index--
element := stack.elements[stack.index]
return element
}
// Выбрасываем ошибку, если стек пуст
panic("stack is empty")
}
Реализация стека(связный список)
Стек может быть реализован на основе связного списка, в такой реализации первый элемент списка будет его вершиной.
// Узел связного списка для хранения элементов стека.
// value - хранимое значение
// next - указатель на следующий узел списка
type StackNode[T any] struct {
value T
next *StackNode[T]
}
// Стек реализованный на базе связного списка.
// head - указатель на вершину стека
type Stack[T any] struct {
head *StackNode[T]
}
StackNode - узел связного списка хранящий данные в поле value и указатель на следующий элемент next.
Stack - стек на основе связного списка, head указатель на вершину стека.
Добавление элемента происходит через присвоение указателю head нового узла, содержащего добавляемый элемент:
Создается новый узел StackNode.
Указатель next нового узла должен ссылаться на head.
Указатель head должен ссылаться на новый узел.
// Добавление элемента в стек.
// element - новый элемент стека, который будет добавлен на вершину стека
func (stack *Stack[T]) Push(element T) {
// Новый элемент указывается в качестве первого узла списка, старое
// значение указывается в качестве следующего узла списка
node := &StackNode[T]{value: element, next: stack.head}
stack.head = node
}
Чтобы извлечь элемент из стека, необходимо присвоить указателю head его же значение next, как показано ниже:
// Извлечение элемента из стека, возвращает элемент или выбрасывает
// ошибку, если стек пуст.
func (stack *Stack[T]) Pop() T {
// Если указатель содержит узел связного списка, то возвращаем
// значение и указываем следующий узел в качестве первого узла
if stack.head != nil {
element := stack.head.value
stack.head = stack.head.next
return element
}
// Выбрасываем ошибку, если стек пуст
panic("stack is empty")
}
Сравнение реализаций
Сложность всех представленных операций стека в обеих реализациях принято считать за O(1) или иначе говоря за константное время, исключая редкий сценарий полного заполнения массива. В таком сценарии добавление элемента происходит за время O(n), так как, приходится копировать все элементы стека в новый массив.
Главным преимуществом стека на основе связного списка является простота реализации и отсутствие необходимости копировать все элементы при исчерпании места для вставки, как в случае с массивом, но при этом требуется больше памяти для хранения элементов.Массив требует меньше памяти для хранения и благодаря своей структуре позволяет реализовать сценарии с доступом к элементу стека по индексу.Весь исходный код примеров к данной статье вы можете найти на GitHub.