Стек

Правило LIFO:

Стек это линейная структура данных где все вставки и удаления происходят на одном конце, называемом верхом. Правило это LIFO (последний вошедший, первый вышедший): элемент добавленный совсем недавно это тот что удаляется первым.

Представь стопку обеденных тарелок в шкафу. Когда ты хватаешь тарелку, ты берёшь сверху (последнюю положенную там). Когда ты кладёшь тарелку назад, она идёт сверху. Ты никогда не хватаешь из середины или снизу. Это LIFO.

Три операции:

1. Push: Добавь элемент на верх стека. Возвращает ничего; обновляет стек на месте.
2. Pop: Удали и верни верхний элемент стека. Если стек пуст, или верни null или подними ошибку (зависит от реализации).
3. Peek (или top): Верни верхний элемент без его удаления. Позволяет тебе увидеть что там перед тем как ты обязуешься pop-нуть.

const stack = [];  // Пустой стек

// Push: добавь 10, 20, 30
stack.push(10);    // Стек: [10]
stack.push(20);    // Стек: [10, 20]
stack.push(30);    // Стек: [10, 20, 30]

// Peek: увидь верх
console.log(stack[stack.length - 1]);  // 30 (без удаления)

// Pop: удали верх
const top = stack.pop();  // Возвращает 30. Стек: [10, 20]

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

Массив естественно моделирует стек. Конец массива это верх. Push добавляет в конец; pop удаляет из конца. Оба выполняются за O(1) амортизированное время (в JavaScript язык скрывает resize массива).

class Stack {
  constructor() {
    this.items = [];
  }
  
  push(value) {
    this.items.push(value);
  }
  
  pop() {
    if (this.items.length === 0) return null;
    return this.items.pop();
  }
  
  peek() {
    if (this.items.length === 0) return null;
    return this.items[this.items.length - 1];
  }
  
  isEmpty() {
    return this.items.length === 0;
  }
}

Реализация со связным списком:

Стек может быть также подкреплён связным списком. Push и pop оба работают на голове (нет traverse нужно). Это также O(1).

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

class StackLinkedList {
  constructor() {
    this.top = null;  // Head pointer
  }
  
  push(value) {
    const newNode = new Node(value, this.top);
    this.top = newNode;
  }
  
  pop() {
    if (this.top === null) return null;
    const value = this.top.value;
    this.top = this.top.next;
    return value;
  }
  
  peek() {
    if (this.top === null) return null;
    return this.top.value;
  }
  
  isEmpty() {
    return this.top === null;
  }
}

Подробный пример: сбалансированные скобки

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

Задача: Дана строка со знаками (, ), [, ], {, }, проверь сбалансирована ли каждая открывающая скобка с соответствующей закрывающей скобкой в правильном порядке.

Пример: "({[]})" сбалансирована. "({[}])" не сбалансирована (закрывающая } закрывает неправильную скобку).

Алгоритм: Обработай строку слева направо.

1. Если ты видишь открывающую скобку ((, [, {), push её на стек.
2. Если ты видишь закрывающую скобку (), ], }), pop стек и проверь совпадает ли. Если не совпадает, возврати false. Если стек пуст, возврати false (нет открывающей скобки для сопоставления).
3. В конце, стек должен быть пуст. Если нет, есть незакрытые открывающие скобки.

Пример trace: "{[]}"

• Видишь {: push {. Стек: [{]
• Видишь [: push [. Стек: [{, []
• Видишь ]: pop [. Совпадает ли [ с ]? Да. Стек: [{]
• Видишь }: pop {. Совпадает ли { с }? Да. Стек: []
• Конец: стек пуст. Сбалансирована!

Пример trace: "{[}]"

• Видишь {: push {. Стек: [{]
• Видишь [: push [. Стек: [{, []
• Видишь }: pop [. Совпадает ли [ с }? Нет. Возврати false. Не сбалансирована.