Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Стек (от англ. stack — стопка) — это структура данных, в которой элементы организованы в упорядоченный набор по принципу «последним вошел — первым вышел» ("last-in, first-out" — LIFO). Элементы добавляются и удаляются из стека только с одного конца, который называют "верхушкой" (top).

---

Сферы применения

Обратный порядок выполнения

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

Обратный порядок символов

Стек помогает разворачивать строки и выражения. Например, для поиска палиндрома или разворачивания строки.

Парсинг выражений

Стек используется в парсерах для обработки математических выражений, таких как преобразование инфиксных выражений в постфиксные (обратная польская нотация).

Отмена действий

Во многих текстовых редакторах и графических приложениях используется стек для реализации функций отмены и повтора (undo/redo).

---

Основные операции

1. Операция добавления (push) — добавление элемента на вершину стека. Вычислительная сложность: $O(1)$, пространственная сложность: $O(1)$.
2. Операция удаления (pop) — удаление верхнего элемента стека. Вычислительная сложность: $O(1)$, пространственная сложность: $O(1)$.
3. Операция просмотра (peek/top) — просмотр верхнего элемента стека без его удаления. Вычислительная сложность: $O(1)$, пространственная сложность: $O(1)$.
4. Операция проверки на пустоту (is_empty/empty) — проверка, пуст ли стек. Вычислительная сложность: $O(1)$, пространственная сложность: $O(1)$.

Добавление

Операция добавления (push) добавляет новый элемент на вершину стека. Новый элемент становится вершиной стека, смещая предыдущий элемент.

Если стек пуст, добавленный элемент становится первым и единственным.

Переполнение стека

Переполнение стека (Stack Overflow) происходит, когда стек достигает своего максимального размера, и дальнейшие попытки добавить элементы вызывают ошибку. Это может произойти в стеках с фиксированным размером или из-за слишком глубокой рекурсии, когда каждый новый вызов функции добавляется в стек вызовов. Для предотвращения переполнения рекомендуется проверять размер стека перед добавлением элементов, использовать динамическое увеличение размера стека или контролировать глубину рекурсии.

Вычислительная сложность

Добавление элемента в стек происходит за постоянное время - $O(1)$, так как операция не зависит от количества элементов в стеке.

Пространственная сложность

Операция удаления требует постоянного объема памяти для добавления одного элемента в стек, поэтому сложность - $O(1)$.

Псевдокод

Функция Push(стек, элемент):
    если стек заполнен:
        вывести "Стек переполнен"
        вернуть

    увеличить верхушку стека на 1
    стек[верхушка] = элемент

---

Реализация на Python

Аннотация:
push - функция, которая добавляет элемент в стек
data - значение, которое будет присваиваться элементу
new_node - новый элемент
Node - класс для представления элемента стека
self._top - первый элемент стека
next - ссылка на следующий элемент
self._size - размер стека

def push(self, data):
    new_node = Node(data)
    new_node.next = self._top
    self._top = new_node
    self._size += 1

---

Олимпиадная реализация на C++

Аннотация:
stack - стек
push - Функция добавления нового значения в стек

#include <iostream>
#include <stack>
using namespace std;
int main() {
  stack<int> stack;
  stack.push(21);
  stack.push(22);
  stack.push(24);
  stack.push(25);
  int num = 0;
  stack.push(num);
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
push - функция добавления элемента в стек
data - значение элемента стека
new_element - новый элемент стека
Node - структура отдельного узла стека
next - следующий элемент стека
top - вершина стека
count - количество элементов в стеке

template <typename T>
void Stack<T>::push(T data) {
  Node<T>* new_element = new Node<T>(data);
  new_element->next = top;
  top = new_element;
  count++;
}

---

Удаление

Операция удаления (pop) удаляет верхний элемент стека и возвращает его значение. Если стек пуст, самые распространенные значения вывода: $-1$, $False$ или ошибка. Удаление элемента происходит путем сохранения значения текущей "верхушки", для последующего вывода, и ссылки на элемент, который идёт за верхушкой, чтобы сделать его новым верхним элементом.

Вычислительная сложность

Удаление верхнего элемента не требует обхода всего стека и выполняется за постоянное время - $O(1)$.

Пространственная сложность

Операция удаления не требует дополнительной памяти, кроме хранения самого элемента, который удаляется, следовательно сложность - $O(1)$.

Псевдокод

Функция Pop(стек):
    если стек пуст:
        вывести "Стек пуст"
        вернуть пустое значение

    сохранить элемент = стек[верхушка]
    уменьшить верхушку стека на 1
    вернуть элемент

---

Реализация на Python

Аннотация:
pop - функция, которая удаляет первый элемент и возвращающая его в переменную
is_empty - функция проверки пустой стек или нет
popped_node - удаляемый элемент
self._top - вершина стека
self._top.next - следующий элемент после верхнего
self._size - размер стека
data - значение, которое присвоено элементу

def pop(self):
    if self.is_empty():
        return -1
            
    popped_node = self.top
    self._top = self._top.next
    self._size -= 1
    return popped_node.data 

---

Олимпиадная реализация на C++

Аннотация:
stack - стек
pop - Функция удаления верхнего элемента стека

#include <iostream>
#include <stack>
using namespace std;
int main() {
  stack<int> stack;
  stack.push(21);
  stack.push(22);
  stack.pop();
  stack.pop();
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
Stack - класс стека, где будут храниться все узлы
pop - функция, которая удаляет элемент из стека
is_empty - функция, которая определяет пустой стек или нет
Node - структура отдельного узла стека
front_element - первый элемент стека
top - вершина стека
next - следующий элемент стека
count - количество элементов в стеке
data - значение элемента стека

template <typename T>
T Stack<T>::pop() {
  if (is_empty()) return -1;

  Node<T>* front_element = top;
  top = front_element->next;
  count--;
  return front_element->data;
}

---

Просмотр верхнего элемента

Операция просмотра верхнего элемента (peek/top) возвращает элемент на верхушке стека, но не удаляет его. Полезно, когда нужно узнать, какой элемент находится на верхушке, без его удаления.

Вычислительная сложность

Просмотр верхнего элемента требует только доступа к указателю вершины, что выполняется за постоянное время - $O(1)$.

Пространственная сложность

Операция просмотра верхнего элемента не требует дополнительной памяти, следовательно сложность - $O(1)$.

Псевдокод

Функция Peek(стек):
    если стек пуст:
        вывести "Стек пуст"
        вернуть пустое значение

    вернуть стек[верхушка]

---

Реализация на Python

Аннотация:
peek - функция, которая возвращает верхушку стека
is_empty - функция проверки пустой стек или нет
self._top - первый элемент стека
data - значение элемента

def peek(self):  
    if self.is_empty():  
        return False 
            
    return self._top.data

---

Олимпиадная реализация на C++

Аннотация:
stack - стек
push - Функция добавления нового значения в стек
top - функция, которая возвращает верхушку стека

#include <iostream>
#include <stack>
using namespace std;
int main() {
  stack<int> stack;
  stack.push(21);
  stack.push(22);
  cout << stack.top() << " ";
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
Stack - класс стека, где будут храниться все узлы
peek - функция, которая возвращает верхушку стека
is_empty - функция, которая определяет пустой стек или нет
top - вершина стека
data - значение элемента стека

template <typename T>
T Stack<T>::peek() const {
  if (is_empty()) return false;

  return top->data;
}

---

Проверка на пустоту

Операция проверки на пустоту (is_empty/empty) проверяет, содержит ли стек элементы. Если стек пуст, возвращает $True$, иначе $False$.

Вычислительная сложность

Проверка выполняется за постоянное время - $O(1)$, так как она лишь проверяет значение индекса вершины стека.

Пространственная сложность

Операция не требует дополнительной памяти, следовательно сложность - $O(1)$.

Псевдокод

Функция is_empty(стек):
    если верх = пустота:
        вернуть True
        
    иначе:
        вернуть False

---

Реализация на Python

Аннотация:
is_empty - функция проверки пустой стек или нет
self._top - первый элемент стека

def is_empty(self):
    return self._top is None

---

Олимпиадная реализация на C++

Аннотация:
stack - стек
push - Функция добавления нового значения в стек
empty - Функция проверки на пустоту
top - функция, которая возвращает верхушку стека

#include <iostream>
#include <stack>
using namespace std;
int main() {
  stack<int> stack;
  stack.push(21);
  stack.push(22);
  if (!stack.empty()) {
    cout << stack.top() << " ";
  }
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
Stack - класс стека, где будут храниться все узлы
is_empty - функция, которая определяет пустой стек или нет
top - вершина стека

template <typename T>
bool Stack<T>::is_empty() {
  if (top == nullptr) return true;

  return false;
}

---

Вычислительная сложность

Вычислительная сложность всех операций стека имеет постоянную сложность $O(1)$.

---

Пространственная сложность

Пространственная сложность стека составляет $O(n)$, где $n$ — количество элементов. В случае реализации на массиве используется только память для элементов, а при использовании связанного списка требуется дополнительная память на указатели.

---

Особенности стека

• Простота: стек легко реализуется и используется в программировании.
• Эффективность: операции добавления и удаления выполняются за постоянное время $O(1)$, что делает стек очень быстрым для этих операций.
• Универсальность: стек находит применение во многих задачах, от обработки выражений до управления памятью.
• Ограниченность: доступ к элементам стека возможен только с его верхушки, что ограничивает его применение в задачах, где требуется доступ к произвольному элементу.
• Фиксированный размер (в некоторых реализациях): в некоторых реализациях стека (например, на основе массива) размер стека фиксирован и не может быть увеличен динамически без создания нового массива, что может стать ограничением при большом количестве элементов.

---

Реализация

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

На массиве

В этой реализации стек реализован на основе массива фиксированного размера. Такой стек имеет ограничение на количество элементов, которое может быть добавлено.

---

Псевдокод

Класс СтекНаФиксированномМассиве:
    Метод инициализация(размер=100):
        Создать массив из элементов None размером размер
        Установить емкость массива равной размер
        Установить индекс_вершины равным -1

    Метод добавить(данные):
        Если индекс_вершины равен емкость - 1:
            Выбросить исключение "Переполнение стека"
            
        Увеличить индекс_вершины на 1
        Записать данные в массив[индекс_вершины]

    Метод удалить():
        Если стек пуст:
            Выбросить исключение "Стек пуст"
            
        Сохранить данные из массив[индекс_вершины]
        Уменьшить индекс_вершины на 1
        Вернуть сохраненные данные

    Метод верхушка():
        Если стек пуст:
            Выбросить исключение "Стек пуст"
            
        Вернуть массив[индекс_вершины]

    Метод пустой():
        Вернуть истину, если индекс_вершины равен -1, иначе ложь

    Метод размер():
        Вернуть индекс_вершины + 1

---

Реализация на Python

Аннотация:
fixed_array_stack - реализация стека, с помощью массива фиксированной длины
size - размер стека
arr - массив фиксированного размера для хранения элементов стека
capacity - вместимость стека
top_index - индекс верхнего элемента в стеке
push - функция, которая добавляет элемент в стек
data - элемент, который добавляем
pop - функция, которая удаляет первый элемент и возвращающая его в переменную
is_empty - функция проверки пустой массив или нет
peek - функция, которая возвращает верхушку стека
size - функция, которая возвращает размер списка

class fixed_array_stack:
    def __init__(self, size=100):
        self.arr = [None] * size
        self.capacity = size
        self.top_index = -1

    def push(self, data):
        if self.top_index == self.capacity - 1:
            raise Exception("Stack overflow")
            
        self.top_index += 1
        self.arr[self.top_index] = data

    def pop(self):
        if self.is_empty():
            raise Exception("Stack underflow")
            
        data = self.arr[self.top_index]
        self.top_index -= 1
        return data

    def peek(self):
        if self.is_empty():
            raise Exception("Stack is empty")
            
        return self.arr[self.top_index]

    def is_empty(self):
        return self.top_index == -1

    def size(self):
        return self.top_index + 1

---

Олимпиадная реализация на C++

Аннотация:
FixedArrayStack - реализация стека, с помощью массива фиксированной длины
arr - массив фиксированного размера для хранения элементов стека
ti - индекс верхнего элемента в стеке
ms - максимальный размер стека
s - размер стека
push - функция, которая добавляет элемент в стек
d - элемент, который добавляем
pop - функция, которая удаляет первый элемент и возвращающая его в переменную
peek - функция, которая возвращает верхушку стека
empty - функция проверки пустой стек или нет
size - функция, которая возвращает размер стека

class FixedArrayStack {
 private:
  int* arr;
  int ti;
  int ms;

 public:
  FixedArrayStack(int s = 100000) {
    arr = new int[s];
    ti = -1;
    ms = s;
  }
  
  ~FixedArrayStack() { delete[] arr; }
  
  void push(int d) {
    if (ti >= ms - 1) {
      std::cerr << "Stack overflow\n";
      return;
    }
    arr[++ti] = d;
  }

  int pop() {
    if (ti < 0) {
      std::cerr << "Stack underflow\n";
      return -1;
    }
    return arr[ti--];
  }

  int peek() const {
    if (ti < 0) {
      std::cerr << "Stack is empty\n";
      return -1;
    }
    return arr[ti];
  }

  bool empty() const { return ti < 0; }

  int size() const { return ti + 1; }
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
FixedArrayStack - реализация стека, с помощью массива фиксированной длины
arr - массив фиксированного размера для хранения элементов стека
capacity - вместимость стека
topIndex - индекс верхнего элемента в стеке
size - размер стека
push - функция, которая добавляет элемент в стек
data - элемент, который добавляем
pop - функция, которая удаляет первый элемент и возвращающая его в переменную
isEmpty - функция проверки пустой стек или нет
peek - функция, которая возвращает верхушку стека
size - функция, которая возвращает размер стека

template <typename T>
class FixedArrayStack {
 private:
  T* arr;
  int capacity;
  int topIndex;

 public:
  FixedArrayStack(int size = 100) {
    capacity = size;
    arr = new T[capacity];
    topIndex = -1;
  }

  ~FixedArrayStack() { delete[] arr; }

  void push(T data);
  T pop();
  T peek() const;
  bool isEmpty() const;
  int size() const;
};

template <typename T>
void FixedArrayStack<T>::push(T data) {
  if (topIndex == capacity - 1) {
    std::cerr << "Stack overflow\n";
    return;
  }

  arr[++topIndex] = data;
}

template <typename T>
T FixedArrayStack<T>::pop() {
  if (isEmpty()) {
    std::cerr << "Stack underflow\n";
    return T();
  }

  return arr[topIndex--];
}

template <typename T>
T FixedArrayStack<T>::peek() const {
  if (isEmpty()) {
    std::cerr << "Stack is empty\n";
    return T();
  }

  return arr[top_index];
}

template <typename T>
bool FixedArrayStack<T>::isEmpty() const {
  return topIndex == -1;
}

template <typename T>
int FixedArrayStack<T>::size() const {
  return topIndex + 1;
}

---

На списке

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

---

Псевдокод

Класс Узел(данные, следующий элемент <- пустота)
    данные
    следующий элемент

Класс Стек()
    количество = 0
    верх = пустота

    Метод Проверка на пустоту()
        если верх = пустота
            вернуть Правда
            
        иначе
            вернуть Ложь

    Метод Добавление элемента(данные)
        новый элемент = новый Узел(данные)
        новый элемент.следующий элемент = верх
        верх = новый элемент
        количество += 1

    Метод Удаление элемента()
        если Проверка на пустоту()
            вернуть -1
            
        передний элемент = верх
        верх = передний элемент.следующий элемент
        количество -= 1
        вернуть передний элемент.данные

    Метод верхушка():
        Если стек не пустой:
            Сохраняем последний элемент, который был на вершине стека
            Возвращаем данные последнего элемента
            
        Иначе вернуть данные "конца"

    Метод Узнать размер()
        вернуть количество

---

Реализация на Python

Аннотация:
Node - класс для представления элемента стека
data - значение, которое будет присваиваться элементу
next - ссылка на следующий элемент
Stack - класс, представляющий сам стек
self._end - последний элемент стека
self._top - первый элемент стека
self._size - размер стека
push - функция, которая добавляет элемент в стек
new_node - новый элемент
popped_node - элемент, который удаляем
self._top.next - следующий элемент после верхнего
pop - функция, которая удаляет первый элемент и возвращающая его в переменную
is_empty - функция проверки пустой стек или нет
peek - функция, которая возвращает верхушку стека
size - функция, которая возвращает размер стека

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self._top = None
        self._size = 0

    def push(self, data):
        new_node = Node(data)
        new_node.next = self._top
        self._top = new_node
        self._size += 1

    def pop(self):
        if self.is_empty():
            return -1
            
        popped_node = self._top
        self._top = self._top.next
        self._size -= 1
        return popped_node.data

    def peek(self):
        if self.is_empty():
            return False
            
        return self._top.data

    def is_empty(self):
        return self._top is None

    def size(self):
        return self._size

---

Олимпиадная реализация на C++

Аннотация:
stack - стек
push - Функция добавления нового значения в стек
pop - Функция удаления верхнего элемента стека
empty - Функция проверки на пустоту
top - функция, которая возвращает верхушку стека

#include <iostream>
#include <stack>
using namespace std;
int main() {
  stack<int> stack;
  stack.push(21);
  stack.push(22);
  stack.push(24);
  stack.push(25);
  int num = 0;
  stack.push(num);
  stack.pop();
  stack.pop();
  stack.pop();
  while (!stack.empty()) {
    cout << stack.top() << " ";
    stack.pop();
  }
}

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
Node - структура отдельного узла стека
data - значение элемента стека
next - следующий элемент стека
newData - новое значение
Stack - класс стека, где будут храниться все узлы
top - вершина стека
count - количество элементов в стеке
Stack() - конструктор инициализации
~Stack - деструктор для очистки памяти
push - функция добавления элемента в стек
pop - функция, которая удаляет элемент из стека
peek - функция, которая возвращает верхушку стека
isEmpty - функция, которая определяет пустой стек или нет
size - функция, которая возвращает размер стека
newElement - новый элемент стека
nodeToDelete - удаляемый элемент

template <typename T>
struct Node {
  T data;
  Node* next = nullptr;

  Node(T newData) { data = newData; }
};

template <typename T>
class Stack {
 private:
  Node<T>* top;
  int count;

 public:
  Stack() : top(nullptr), count(0) {}

  ~Stack() {
    while (!isEmpty()) pop();
  }

  void push(T data);
  T pop();
  T peek() const;
  bool isEmpty() const;
  int size() const;
};

template <typename T>
void Stack<T>::push(T data) {
  Node<T>* newElement = new Node<T>(data);
  newElement->next = top;
  top = newElement;
  count++;
}

template <typename T>
T Stack<T>::pop() {
  if (isEmpty()) return -1;

  Node<T>* nodeToDelete = top;
  T data = top->data;
  top = top->next;
  delete nodeToDelete;
  count--;
  return data;
}

template <typename T>
T Stack<T>::peek() const {
  if (isEmpty()) return false;

  return top->data;
}

template <typename T>
bool Stack<T>::isEmpty() const {
  return top == nullptr;
}

template <typename T>
int Stack<T>::size() const {
  return count;
}