Стек

Содержание

1. Введение
2. Описание структуры данных
3. Реализация стека(массив)
4. Реализация стека(связный список)
5. Сравнение реализаций

Введение

В данной статье рассмотрим структуру данных стек(Stack), реализуем его на языке Go(Golang) и оценим сложность операций используя O-большое.

Описание структуры данных

Стек, это структура данных, которая хранит элементы в порядке их добавления, хранение организуется по принципу LIFO(Last-In-First-Out), то есть элементы добавленные последними будут извлекаться в первую очередь. Стек реализует две основные операции добавление и извлечение, может быть реализован на базе массива или с использованием связного списка, в данной статье рассмотрим оба варианта.

Реализация стека(массив)

Для реализации стека на основе массива потребуется массив и индекс указывающий на свободную ячейку доступную для добавления нового элемента.

Изображение иллюстрирует структуру стека на основе массива

Ниже приведен код объявления стека:

// Стек реализованный на базе массива, содержит два поля:
// index    - индекс указывающий на свободную ячейку доступную для добавления нового элемента
// elements - элементы стека
type Stack[T any] struct {
  index    int
  elements []T
}

Для добавления элемента необходимо поместить его в свободную ячейку:

1. Поместить новый элемент в ячейку массива elements с индексом index.

2. Увеличить значение index на единицу.


Изображение иллюстрирует добавление элемента в стек

В случае, когда значение index достигло границ массива и свободных ячеек нет, создается новый массив большего размера, а все элементы копируются. Далее приведен код реализующий добавление элемента в стек:

12345678910111213141516171819

// Кол-во элементов, которое будет выделено при достижении границы массива.
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++
}

В строках 9-14 выделяется место путем создания нового массива и копирования в него всех значений старого.

Чтобы извлечь элемент из стека, необходимо сдвинуть index влево на одну позицию. При этом, само значение не удаляется, но отсутствует возможность обращения к этой ячейке массива. Впоследствии значения находящиеся за границей индекса будут перезаписаны новыми элементами.


Изображение иллюстрирует удаление элемента из стека

Реализация операции удаления представлена ниже:

123456789101112

// Извлечение элемента из стека, возвращает элемент или выбрасывает
// ошибку, если стек пуст.
func (stack *Stack[T]) Pop() T {
  // Если указатель больше нуля, извлекаем элемент из стека
  if stack.index > 0 {
    stack.index--
    element := stack.elements[stack.index]
    return element
  }
  // Выбрасываем ошибку, если стек пуст
  panic("stack is empty")
}

Реализация стека(связный список)

Стек может быть реализован на основе связного списка, в такой реализации первый элемент списка будет его вершиной.


Изображение иллюстрирует структуру стека на основе связного списка

Ниже приведено объявление стека на основе связного списка:

12345678910111213

// Узел связного списка для хранения элементов стека.
// 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 нового узла, содержащего добавляемый элемент:

1. Создается новый узел StackNode.

2. Указатель next нового узла должен ссылаться на head.

3. Указатель head должен ссылаться на новый узел.


Изображение иллюстрирует добавление элемента в стек

Ниже представлен код, реализующий добавление элемента:

12345678

// Добавление элемента в стек.
// element - новый элемент стека, который будет добавлен на вершину стека
func (stack *Stack[T]) Push(element T) {
  // Новый элемент указывается в качестве первого узла списка, старое
  // значение указывается в качестве следующего узла списка
  node := &StackNode[T]{value: element, next: stack.head}
  stack.head = node
}

Чтобы извлечь элемент из стека, необходимо присвоить указателю head его же значение next, как показано ниже:


Изображение иллюстрирует удаление элемента из стека

Код ниже демонстрирует удаление элемента из стека:

12345678910111213

// Извлечение элемента из стека, возвращает элемент или выбрасывает
// ошибку, если стек пуст.
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.