По какому принципу работает стек

Принцип работы стека в программировании

Стек — это абстрактный тип данных (АТД), работающий по принципу LIFO (Last In, First Out), что переводится как «последним пришёл — первым вышел». Это означает, что элемент, добавленный в стек последним, будет извлечён из него первым. Визуально стек можно представить как стопку тарелок: новую тарелку кладут сверху, и снять можно также только верхнюю.

Ключевые операции со стеком

Основные операции, которые определяют поведение стека:

• push (добавление) — помещает новый элемент на вершину стека.
• pop (извлечение) — удаляет и возвращает элемент с вершины стека.
• peek (или top) — возвращает элемент с вершины стека без его удаления.
• isEmpty — проверяет, пуст ли стек.
• size — возвращает текущее количество элементов в стеке.

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

Стек можно реализовать на основе различных структур данных. Наиболее распространены две:

1. Реализация на основе массива (или списка с динамическим размером)

В этой реализации массив служит хранилищем, а отдельная переменная (например, topIndex) отслеживает индекс текущей вершины стека.

class StackArray {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element);
    }

    pop() {
        if (this.isEmpty()) {
            return 'Стек пуст';
        }
        return this.items.pop();
    }

    peek() {
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

// Пример использования
const stack = new StackArray();
stack.push(10); // Стек: [10]
stack.push(20); // Стек: [10, 20]
console.log(stack.peek()); // 20
console.log(stack.pop());  // 20 (удалён). Стек: [10]

2. Реализация на основе односвязного списка

В этой реализации каждый элемент стека (Node) хранит данные и ссылку на следующий элемент. Вершиной стека становится голова списка, так как операции добавления и удаления с головы выполняются за O(1).

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class StackLinkedList {
    constructor() {
        this.top = null;
        this.length = 0;
    }

    push(value) {
        const newNode = new Node(value);
        newNode.next = this.top; // Новый узел ссылается на старую вершину
        this.top = newNode;      // Новый узел становится новой вершиной
        this.length++;
    }

    pop() {
        if (this.isEmpty()) {
            return 'Стек пуст';
        }
        const poppedValue = this.top.value;
        this.top = this.top.next; // Вершиной становится следующий узел
        this.length--;
        return poppedValue;
    }

    peek() {
        return this.top ? this.top.value : null;
    }

    isEmpty() {
        return this.top === null;
    }

    size() {
        return this.length;
    }
}

Внутреннее устройство и управление памятью

При вызове функции в программе (например, на JavaScript или C++) стек вызовов (call stack) — это специализированный стек, управляемый средой выполнения. Он хранит фреймы вызовов (call frames), которые содержат локальные переменные функции, параметры и адрес возврата. Когда функция вызывается, её фрейм помещается в стек (push); когда выполнение завершается, фрейм извлекается (pop). Это обеспечивает правильный порядок возврата управления и изоляцию данных между функциями.

function first() {
    console.log('Вход в first');
    second(); // Вызов second добавляет новый фрейм в стек
    console.log('Выход из first');
}

function second() {
    console.log('Вход в second');
    third(); // Вызов third добавляет новый фрейм в стек
    console.log('Выход из second');
}

function third() {
    console.log('Вход в third');
    // В этот момент стек вызовов: [first, second, third]
    console.log('Выход из third');
    // Завершение third -> фрейм удаляется (pop)
}

first(); // Инициирует весь процесс
// Порядок вывода: "Вход в first", "Вход в second", "Вход в third",
// "Выход из third", "Выход из second", "Вход в first".

Практическое применение стека

Стек — фундаментальная структура с широким спектром применения:

• Стек вызовов (Call Stack): Основа выполнения любого рекурсивного или итеративного кода.
• Алгоритмы обхода графов и деревьев: Например, поиск в глубину (DFS).
• Отмена действий (Undo): В текстовых редакторах или графических программах последовательность действий хранится в стеке.
• Парсинг и вычисление выражений: Проверка сбалансированности скобок или конвертация инфиксной записи в постфиксную (польскую нотацию).
• Навигация по истории: Кнопка «Назад» в браузере часто реализована на основе двух стеков (для перехода вперёд и назад).

Сравнение реализации на массиве и списке

• Массив (динамический): Доступ по индексу быстрый, но может потребоваться расширение (реаллокация) при превышении capacity.
• Односвязный список: Каждая операция push и pop выполняется за O(1) без необходимости реаллокации, но требует дополнительной памяти для хранения ссылок.

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