Для чего используется stack?

Stack (Стек) в программировании

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

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

class Stack<T> {
  private items: T[] = [];
  
  // push() — добавить элемент
  push(item: T): void {
    this.items.push(item);
  }
  
  // pop() — удалить и вернуть элемент
  pop(): T | undefined {
    return this.items.pop();
  }
  
  // peek() — посмотреть верхний элемент без удаления
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }
  
  // isEmpty() — проверить пусто ли
  isEmpty(): boolean {
    return this.items.length === 0;
  }
  
  // size() — размер
  size(): number {
    return this.items.length;
  }
}

const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop());  // 3
console.log(stack.pop());  // 2
console.log(stack.pop());  // 1

Stack в Node.js

1. Call Stack — выполнение функций

Когда функция вызывает другую функцию:

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 start
// b start
// c
// b end
// a end

Call Stack (стек вызовов):

┌─────┐
│  c  │  ← Текущая функция
├─────┤
│  b  │  ← Вызвавшая c
├─────┤
│  a  │  ← Вызвавшая b
├─────┤
│global│ ← Глобальный контекст
└─────┘

Stack Overflow — когда стек переполняется:

function recursion() {
  return recursion(); // Бесконечная рекурсия
}

recursion();
// RangeError: Maximum call stack size exceeded

2. Browser DevTools — видно Call Stack

Когда приложение падает или вы ставите breakpoint, DevTools показывает:

Call Stack:
├─ handleClick (index.js:45)
├─ processData (utils.js:12)
├─ fetchData (api.js:8)
└─ (anonymous) (index.js:1)

Это помогает понять откуда ошибка.

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

1. Проверка сбалансированности скобок

function isBalanced(str: string): boolean {
  const stack = new Stack<string>();
  const pairs: { [key: string]: string } = {
    ')': '(',
    ']': '[',
    '}': '{'
  };
  
  for (const 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
console.log(isBalanced('((([]))'));   // true

2. Undo/Redo функционал

class Editor {
  private undoStack = new Stack<string>();
  private redoStack = new Stack<string>();
  private text = '';
  
  type(char: string) {
    this.undoStack.push(this.text);
    this.redoStack.clear();
    this.text += char;
  }
  
  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()!;
    }
  }
}

3. DFS (Depth-First Search) в графах

function dfs(graph: { [key: string]: string[] }, start: string) {
  const stack = new Stack<string>();
  const visited = new Set<string>();
  
  stack.push(start);
  visited.add(start);
  
  while (!stack.isEmpty()) {
    const node = stack.pop()!;
    console.log(node);
    
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
}

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

dfs(graph, 'A'); // A, C, E, B, D

4. Обратная нотация (RPN)

function evaluateRPN(tokens: string[]): number {
  const stack = new Stack<number>();
  
  for (const token of tokens) {
    if (token === '+' || token === '-' || token === '*' || token === '/') {
      const b = stack.pop()!;
      const a = stack.pop()!;
      
      let result: number;
      switch (token) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = Math.trunc(a / b); break;
      }
      stack.push(result);
    } else {
      stack.push(parseInt(token));
    }
  }
  
  return stack.pop()!;
}

evaluateRPN(['2', '1', '+', '3', '*']); // ((2+1)*3) = 9

Stack vs Queue

Временная и пространственная сложность

// Stack операции всегда O(1)
push(item)      // O(1)
pop()           // O(1)
peek()          // O(1)
isEmpty()       // O(1)
size()          // O(1)

// Space complexity: O(n) где n количество элементов

Stack trace (трассировка стека)

Когда ошибка, видно весь stack trace:

Error: Something went wrong
  at processOrder (order.js:45)
  at handleRequest (api.js:23)
  at handler (express.js:12)
  at Layer.handle (router.js:8)

Это показывает цепочку вызовов от ошибки до точки входа.

Заключение

Stack — это фундаментальная структура данных в программировании. Она используется в:

• Выполнении функций (Call Stack)
• Навигации (Back button)
• Undo/Redo
• Проверке скобок
• Поиске в глубину (DFS)
• Обработке выражений

Понимание стека критично для отладки и оптимизации кода.