Как реализуешь стек?

Как реализовать структуру данных Стек (Stack)

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

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

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

Реализация 1: На основе массива

Самый простой и практичный способ — использовать встроенный массив JavaScript.

class Stack {
  constructor() {
    this.items = [];
  }
  
  // Добавить элемент
  push(element) {
    this.items.push(element);
  }
  
  // Удалить и вернуть верхний элемент
  pop() {
    if (this.items.length === 0) {
      return undefined;
    }
    return this.items.pop();
  }
  
  // Посмотреть верхний элемент
  peek() {
    if (this.items.length === 0) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }
  
  // Проверить, пуст ли стек
  isEmpty() {
    return this.items.length === 0;
  }
  
  // Получить размер
  size() {
    return this.items.length;
  }
  
  // Очистить стек
  clear() {
    this.items = [];
  }
  
  // Вывести все элементы
  print() {
    console.log(this.items.toString());
  }
}

Использование

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
console.log(stack.isEmpty()); // false

stack.print(); // 10,20

Реализация 2: На основе объекта (оптимальнее)

Для лучшей производительности можно использовать объект вместо массива.

class Stack {
  constructor() {
    this.items = {};
    this.count = 0; // Индекс последнего элемента
  }
  
  push(element) {
    this.items[this.count] = element;
    this.count++;
  }
  
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.count - 1];
    delete this.items[this.count - 1];
    this.count--;
    return result;
  }
  
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }
  
  isEmpty() {
    return this.count === 0;
  }
  
  size() {
    return this.count;
  }
  
  clear() {
    this.items = {};
    this.count = 0;
  }
}

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

Пример 1: Проверка скобок

Проверить, правильно ли расставлены скобки в выражении.

function isBalanced(str) {
  const stack = new Stack();
  const pairs = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (let char of str) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else if (char === ')' || char === '}' || char === ']') {
      if (stack.isEmpty() || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }
  
  return stack.isEmpty();
}

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

Пример 2: Система отмены/повтора (Undo/Redo)

class TextEditor {
  constructor() {
    this.undoStack = new Stack();
    this.redoStack = new Stack();
    this.text = '';
  }
  
  type(char) {
    this.undoStack.push(this.text);
    this.text += char;
    this.redoStack.clear(); // Очистить redo при новом вводе
  }
  
  undo() {
    if (!this.undoStack.isEmpty()) {
      this.redoStack.push(this.text);
      this.text = this.undoStack.pop();
    }
  }
  
  redo() {
    if (!this.redoStack.isEmpty()) {
      this.undoStack.push(this.text);
      this.text = this.redoStack.pop();
    }
  }
  
  getText() {
    return this.text;
  }
}

const editor = new TextEditor();
editor.type('H');
editor.type('e');
editor.type('y');
console.log(editor.getText()); // Hey

editor.undo();
console.log(editor.getText()); // He

editor.redo();
console.log(editor.getText()); // Hey

Пример 3: Вычисление постфиксного выражения

Оценить выражение вида: 5 3 + 2 *

function evaluatePostfix(expression) {
  const stack = new Stack();
  const tokens = expression.split(' ');
  
  for (let token of tokens) {
    if (!isNaN(token)) {
      // Это число
      stack.push(parseInt(token));
    } else {
      // Это оператор
      const b = stack.pop();
      const a = stack.pop();
      
      let result;
      switch (token) {
        case '+':
          result = a + b;
          break;
        case '-':
          result = a - b;
          break;
        case '*':
          result = a * b;
          break;
        case '/':
          result = a / b;
          break;
      }
      
      stack.push(result);
    }
  }
  
  return stack.peek();
}

console.log(evaluatePostfix('5 3 + 2 *')); // 16 (5+3)*2
console.log(evaluatePostfix('10 5 / 2 *')); // 4 (10/5)*2

Пример 4: Обход в глубину (DFS)

function depthFirstSearch(graph, start) {
  const stack = new Stack();
  const visited = new Set();
  
  stack.push(start);
  
  while (!stack.isEmpty()) {
    const vertex = stack.pop();
    
    if (!visited.has(vertex)) {
      console.log(vertex);
      visited.add(vertex);
      
      // Добавляем соседей в стек
      for (let neighbor of graph[vertex]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

depthFirstSearch(graph, 'A'); // A, C, B, D

Сложность операций

В React/TypeScript

interface StackItem<T> {
  value: T;
  next?: StackItem<T>;
}

class GenericStack<T> {
  private top?: StackItem<T>;
  private count: number = 0;
  
  push(value: T): void {
    this.top = { value, next: this.top };
    this.count++;
  }
  
  pop(): T | undefined {
    if (!this.top) return undefined;
    const value = this.top.value;
    this.top = this.top.next;
    this.count--;
    return value;
  }
  
  peek(): T | undefined {
    return this.top?.value;
  }
  
  isEmpty(): boolean {
    return this.count === 0;
  }
  
  size(): number {
    return this.count;
  }
}

Когда использовать Стек

• Проверка скобок в компиляторах
• История браузера (back button)
• Отмена/повтор в редакторах
• Обход графов в глубину
• Вычисление выражений (постфиксная нотация)
• Вызовы функций (call stack)

Заключение

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