Stack (Стек)

Stack — линейная структура данных, работающая по принципу LIFO (Last In, First Out): последний добавленный элемент извлекается первым. Как стопка тарелок.

Зачем нужно

Стек — одна из самых важных структур в программировании. Call stack управляет вызовами функций, undo/redo используют стек, парсинг скобок, вычисление выражений, навигация «назад» — всё это стек.

Где используется

  • Call stack (стек вызовов JavaScript)
  • Undo/Redo в редакторах
  • Навигация «назад/вперёд» в браузере
  • Парсинг и проверка скобок ({})
  • Вычисление математических выражений (постфиксная нотация)
  • DFS (обход графов в глубину)
  • Управление состоянием (React reconciler)

Предпосылки

Принцип LIFO

Push 1: [1]
Push 2: [1, 2]
Push 3: [1, 2, 3]     ← вершина (top)
Pop:    [1, 2] → 3     ← извлекли последний
Pop:    [1]    → 2
Peek:   [1]    → 1     ← посмотрели, не извлекая

Операции стека

Операция Описание Сложность
push(item) Добавить на вершину O(1)
pop Извлечь с вершины O(1)
peek / top Посмотреть вершину O(1)
isEmpty Проверка пустоты O(1)
size Количество элементов O(1)

Реализация в JavaScript

На основе массива

class Stack {
  #items = ;

  push(item) {
    this.#items.push(item);
  }

  pop {
    if (this.isEmpty) {
      throw new Error('Stack is empty');
    }
    return this.#items.pop();
  }

  peek {
    if (this.isEmpty) {
      throw new Error('Stack is empty');
    }
    return this.#items[this.#items.length - 1];
  }

  isEmpty {
    return this.#items.length === 0;
  }

  size {
    return this.#items.length;
  }

  clear {
    this.#items = ;
  }

  toArray {
    return [...this.#items];
  }
}

// Использование
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek);  // 30
console.log(stack.pop());   // 30
console.log(stack.size);  // 2

На основе связного списка

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

class LinkedStack {
  #top = null;
  #size = 0;

  push(value) {
    this.#top = new StackNode(value, this.#top);
    this.#size++;
  }

  pop {
    if (!this.#top) throw new Error('Stack is empty');
    const value = this.#top.value;
    this.#top = this.#top.next();
    this.#size--;
    return value;
  }

  peek {
    if (!this.#top) throw new Error('Stack is empty');
    return this.#top.value;
  }

  isEmpty { return this.#size === 0; }
  size { return this.#size; }
}

Call Stack — стек вызовов

JavaScript использует стек для управления вызовами функций:

function a() {
  console.log('a start');
  b;
  console.log('a end');
}

function b() {
  console.log('b start');
  c;
  console.log('b end');
}

function c() {
  console.log('c');
}

a;

// Стек вызовов:
// a → push a
// a → b → push b
// b → c → push c
// c завершилась → pop c
// b продолжилась → pop b
// a продолжилась → pop a

// Вывод: a start → b start → c → b end → a end

Практические примеры

Проверка скобок

function isBalanced(str) {
  const stack = ;
  const pairs = { '(': ')', '[': ']', '{': '}' };

  for (const char of str) {
    if (pairs[char]) {
      // Открывающая скобка — в стек
      stack.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      // Закрывающая — проверяем пару
      const last = stack.pop();
      if (pairs[last] !== char) return false;
    }
  }

  return stack.length === 0;
}

console.log(isBalanced('({})')); // true
console.log(isBalanced('({[)]})')); // false
console.log(isBalanced('(('));     // false

Undo/Redo

class UndoRedo {
  #undoStack = ;
  #redoStack = ;
  #current;

  constructor(initialState) {
    this.#current = initialState;
  }

  execute(newState) {
    this.#undoStack.push(this.#current);
    this.#current = newState;
    this.#redoStack = ; // новое действие сбрасывает redo
  }

  undo {
    if (this.#undoStack.length === 0) return;
    this.#redoStack.push(this.#current);
    this.#current = this.#undoStack.pop();
  }

  redo {
    if (this.#redoStack.length === 0) return;
    this.#undoStack.push(this.#current);
    this.#current = this.#redoStack.pop();
  }

  get state { return this.#current; }
}

const editor = new UndoRedo('');
editor.execute('H');
editor.execute('He');
editor.execute('Hel');
console.log(editor.state); // "Hel"
editor.undo;
console.log(editor.state); // "He"
editor.redo;
console.log(editor.state); // "Hel"

Обратная польская нотация (RPN)

function evalRPN(tokens) {
  const stack = ;
  const ops = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),
  };

  for (const token of tokens) {
    if (ops[token]) {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(ops[token](a, b));
    } else {
      stack.push(Number(token));
    }
  }

  return stack.pop();
}

// (2 + 3) * 4 = 20
console.log(evalRPN(['2', '3', '+', '4', '*'])); // 20

Частые ошибки

  1. Pop из пустого стека. Всегда проверяйте isEmpty перед pop
  2. Путать стек и очередь. Stack — LIFO (последний первым), Queue — FIFO (первый первым)
  3. Использовать shift вместо pop. shift — O(n), это не стек, а очередь
  4. Переполнение call stack. Глубокая рекурсия без базового случая

Практика

  1. Реализуйте Stack-класс с min — получение минимума за O(1)
  2. Реализуйте проверку корректности HTML-тегов: <div><p></p></div> — ok, <div><p></div> — нет
  3. Реализуйте reverseString(str) используя стек
  4. Реализуйте конвертацию из десятичной в двоичную систему с помощью стека

Связанные темы

Ресурсы

  • visualgo.net/en/list — визуализация стека
  • JavaScript Call Stack (MDN)
  • Grokking Algorithms (Aditya Bhargava)