Стек

Стек - динамическая структура данных, основанная на принципе LIFO (Last In - First Out) (Первым пришёл — последним ушёл).

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

Стоит помнить, что в стеке мы добавляем элемент наверх, и удаляем оттуда же.

Преимущества стека:

Гибкость размера: Стек на связанном списке позволяет динамически изменять размер стека, так как список может быть динамически расширен или сокращен при добавлении или удалении элементов.
Эффективность операций вставки и удаления: Вставка и удаление элементов в стеке на связанном списке выполняются за константное время $O (1)$ , так как операции происходят только на одном конце стека.
Нет ограничения размера: Стек на связанном списке не имеет ограничения на количество элементов, которые он может содержать, поэтому он может быть очень гибким для работы с большими объемами данных.

Недостатки:

Использование памяти: Стек на связанном списке требует дополнительной памяти для хранения указателей на следующие элементы списка. Поэтому он может потреблять больше памяти по сравнению с другими структурами данных, такими как массивы.
Ограниченная производительность доступа к произвольному элементу: В отличие от массива, доступ к произвольному элементу в стеке на связанном списке требует прохода от начала списка до нужного элемента. Это может сказаться на производительности, особенно при работе с большими стеками.

Реализация стека

Сперва нам необходимо создать структуру Node, которая представляет узел стека. Она будет иметь поля: data типа int для хранения данных (ключа) и указатель next на тип Node.

struct Node {
  int data;
  Node* next;

  Node(int data)
      : data(data),
        next(nullptr) {
  }  // Конструктор  Node  принимает значение  data  и инициализирует поле  data
     // с переданным значением, а поле  next  устанавливается в  nullptr
};

Следующим шагом создадим функцию push, которая будет добавлять новый узел в вершину стека

void push(int data) {
  Node* newNode =
      new Node(data);  // Создаем новый узел с переданным значением data
  newNode->next =
      top;  // Устанавливаем указатель next нового узла на текущую вершину стека
  top = newNode;  // Обновляем вершину стека, чтобы она указывала на новый узел
}

Теперь создадим функцию pop, которая будет удалять элемент из вершины стека.

void pop() {
  if (isEmpty()) {  // проверям, пустой ли стек, если да, то выводим сообщение
                    // "Стек пуст"
    std::cout << "Стек пуст."
              << "\n";
    return;
  }
  Node* temp =
      top;  // Создаем временный указатель и устанавливаем его на вершину стека
  top = top->next;  // Обновляем вершину стека, чтобы она указывала на следующий
                    // элемент
  delete temp;  // Удаляем временный указатель, освобождая память, где хранился
                // предыдущий верхний элемент
}

Далее создадим функцию peek и isEmpty. peek будет возвращать значение вершины стека без удаления, а функция isEmpty проверяет, пуст ли стек, и возвращает соответствующее значение.

int peek() {
  if (isEmpty()) {  // проверям, пустой ли стек, если да, то выводим сообщение
                    // "Стек пуст"
    std::cout << "Стек пуст."
              << "\n";
    return -1;
  }
  return top->data;  // Возвращаем значение данных вершины стека
}

bool isEmpty() {
  return top == nullptr;  // Возвращаем true, если вершина стека равна nullptr,
                          // иначе возвращаем false
}

Код полностью


#include <iostream>

class Stack {  // создаем класс стек, который реализует стек
 private:
  struct Node {
    int data;
    Node* next;

    Node(int data) : data(data), next(nullptr) {}
  };

  Node* top;  // Указатель на верхний элемент стека

 public:
  Stack()
      : top(nullptr) {
  }  // Конструктор класса Stack, инициализирует указатель top как nullptr

  ~Stack() {
    while (!isEmpty()) {
      pop();  // Деструктор класса Stack, освобождает память, удаляя все
              // элементы стека
    }
  }

  void push(int data) {
    Node* newNode = new Node(data);
    newNode->next = top;
    top = newNode;
  }

  void pop() {
    if (isEmpty()) {
      std::cout << "Stack is empty." << std::endl;
      return;
    }
    Node* temp = top;
    top = top->next;
    delete temp;
  }

  int peek() {
    if (isEmpty()) {
      std::cout << "Stack is empty." << std::endl;
      return -1;
    }
    return top->data;
  }

  bool isEmpty() { return top == nullptr; }
};

int main() {
  Stack stack;  // создаем экземпляр структуры
  for (int i = 0; i < 3; i++) {
    stack.push(i);  // добавляем в стек числа от 0 до 2
  }

  std::cout << "Верхний элемент: " << stack.peek() << "\n";

  stack.pop();  // извлекаем элемент
  stack.pop();  // извлекаем элемент

  std::cout << "Top element: " << stack.peek() << "\n";

  stack.pop();  // извлекаем элемент

  if (stack.isEmpty()) {  // проверяем пуст ли стек
    std::cout << "Stack is empty.";
  }
}

Примеры применения очереди:

Управление вызовами функций: Стек используется для хранения информации о вызове функций и их локальных переменных. Каждый раз, когда функция вызывается, ее контекст сохраняется в стеке, и когда функция завершается, контекст извлекается из стека. Это позволяет программе возвращаться к предыдущим точкам выполнения после завершения функции.
Обратная польская запись (Reverse Polish Notation, RPN): Стек может быть использован для вычисления выражений, записанных в обратной польской записи. Он позволяет эффективно хранить операнды и выполнять операции в правильном порядке.
История действий (Undo/Redo): Стек может использоваться для реализации функциональности отмены и повтора действий. Каждое действие сохраняется в стеке, и при отмене последнее действие извлекается из стека и отменяется.
Обработка скобочных выражений: Стек может быть использован для проверки сбалансированности скобок в выражениях. При обработке выражения каждая открывающаяся скобка помещается в стек, а при встрече закрывающейся скобки проверяется, соответствует ли она последней открывающейся скобке в стеке.
Обход деревьев: Стек может использоваться для реализации алгоритмов обхода деревьев, таких как обход в глубину (Depth-First Search, DFS). Он позволяет сохранять состояние обхода и возвращаться к предыдущим узлам при необходимости.