Как работает массив в виде стека?

Массивы как стеки в JavaScript

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

Что такое стек

Стек похож на стопку тарелок: можешь добавлять тарелку сверху (push) и брать тарелку сверху (pop). То, что добавил последним, доступно первым.

Визуально:
Добавление:          Удаление:
push(1)  [1]         pop() -> 3   [1, 2]
push(2)  [1, 2]      pop() -> 2   [1]
push(3)  [1, 2, 3]   pop() -> 1   []

Основные методы стека

// Создание стека (обычный массив)
const stack = [];

// PUSH — добавить элемент в конец (вверх стека)
stack.push(10);  // [10]
stack.push(20);  // [10, 20]
stack.push(30);  // [10, 20, 30]

// POP — удалить и вернуть последний элемент
const top = stack.pop(); // вернёт 30, стек: [10, 20]
console.log(top); // 30

// PEEK — посмотреть верхний элемент без удаления
const peek = stack[stack.length - 1]; // 20
console.log(peek); // 20

// SIZE — размер стека
console.log(stack.length); // 2

// CLEAR — очистить стек
stack.length = 0; // или stack = []

// IS EMPTY — проверить пустой ли стек
const isEmpty = stack.length === 0;

Класс Stack для более удобной работы

// Простая реализация Stack
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];
  }

  // Размер стека
  size() {
    return this.items.length;
  }

  // Проверить пуст ли
  isEmpty() {
    return this.items.length === 0;
  }

  // Очистить
  clear() {
    this.items = [];
  }

  // Вывести все элементы
  print() {
    console.log(this.items.toString());
  }
}

// Использование:
const myStack = new Stack();
myStack.push("a");
myStack.push("b");
myStack.push("c");
console.log(myStack.pop()); // "c"
console.log(myStack.peek()); // "b"

Практические примеры использования стека

// ПРИМЕР 1: Проверка сбалансированности скобок
function isBalancedBrackets(str) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };

  for (let char of str) {
    if (char === "(" || char === "[" || char === "{") {
      // Открывающая скобка — добавляем в стек
      stack.push(char);
    } else if (char === ")" || char === "]" || char === "}") {
      // Закрывающая скобка — проверяем с последней открывающей
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  return stack.length === 0; // если стек пуст — скобки сбалансированы
}

console.log(isBalancedBrackets("([{}])"))  // true
console.log(isBalancedBrackets("([)]"))   // false

ПРИМЕР 2: Обратный порядок строки

function reverseString(str) {
  const stack = [];

  // Добавляем все символы в стек
  for (let char of str) {
    stack.push(char);
  }

  // Извлекаем символы в обратном порядке
  let reversed = "";
  while (stack.length > 0) {
    reversed += stack.pop();
  }

  return reversed;
}

console.log(reverseString("hello")); // "olleh"

ПРИМЕР 3: История навигации (как в браузере Back)

class BrowserHistory {
  constructor() {
    this.stack = [];
  }

  visit(url) {
    this.stack.push(url);
    console.log("Посетил:", url);
  }

  back() {
    if (this.stack.length > 1) {
      this.stack.pop(); // удаляем текущую страницу
      return this.stack[this.stack.length - 1]; // показываем предыдущую
    }
    return null;
  }
}

const browser = new BrowserHistory();
browser.visit("google.com");
browser.visit("github.com");
browser.visit("stackoverflow.com");

console.log(browser.back()); // github.com

ПРИМЕР 4: Вычисление выражений (Обратная польская нотация)

function evaluateRPN(tokens) {
  const stack = [];

  for (let token of tokens) {
    if (token === "+" || token === "-" || token === "*" || token === "/") {
      // Это оператор — берём два элемента из стека
      const b = stack.pop();
      const a = stack.pop();

      let result;
      if (token === "+") result = a + b;
      else if (token === "-") result = a - b;
      else if (token === "*") result = a * b;
      else if (token === "/") result = Math.floor(a / b);

      stack.push(result);
    } else {
      // Это число — добавляем в стек
      stack.push(parseInt(token));
    }
  }

  return stack[0]; // результат
}

console.log(evaluateRPN(["2", "1", "+", "3", "*"])); // (2 + 1) * 3 = 9

ПРИМЕР 5: Undo/Redo в текстовом редакторе

class TextEditor {
  constructor() {
    this.undoStack = [];
    this.redoStack = [];
    this.currentText = "";
  }

  type(text) {
    // Сохраняем текущее состояние перед изменением
    this.undoStack.push(this.currentText);
    this.redoStack = []; // очищаем redo при новом действии
    this.currentText += text;
  }

  undo() {
    if (this.undoStack.length > 0) {
      this.redoStack.push(this.currentText);
      this.currentText = this.undoStack.pop();
    }
  }

  redo() {
    if (this.redoStack.length > 0) {
      this.undoStack.push(this.currentText);
      this.currentText = this.redoStack.pop();
    }
  }
}

const editor = new TextEditor();
editor.type("Hello");
editor.type(" World");
console.log(editor.currentText); // "Hello World"

editor.undo();
console.log(editor.currentText); // "Hello"

editor.redo();
console.log(editor.currentText); // "Hello World"

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

Операция | Сложность | Примечание
---------|-----------|--------------------
Push     | O(1)      | Амортизированная O(1)
Pop      | O(1)      | Быстро удалить сверху
Peek     | O(1)      | Просмотр сверху
Search   | O(n)      | Требует перебора всех

Итого

Массив как стек в JavaScript:

1. LIFO принцип — последний вошёл, первый вышел
2. Push/Pop методы — добавить и удалить с конца
3. Операции O(1) — очень быстрые
4. Применение — проверка скобок, undo/redo, история навигации, вычисления выражений
5. Реализация — используй массив или создай класс Stack

Стек — одна из самых полезных структур данных в программировании.