Другое

Как реализовать стек и очередь в JavaScript

Узнайте, как создать стек и очередь в JavaScript для алгоритма шунтирования. Полное руководство с примерами кода и оптимизациями производительности для быстрой работы.

Авторы: НейроАгент

Как реализовать стек и очередь в JavaScript? Мне нужны эти структуры данных для реализации алгоритма shunting-yard.

Стек и очередь в JavaScript можно реализовать, используя массивы с определёнными комбинациями методов: стек использует операции push() и pop(), а очередь — либо push() с shift(), либо unshift() с pop(). Для алгоритма Шунтинг‑Йарда понадобится стек‑операции (push/pop) для операторов и очередь‑операции (enqueue/dequeue) для вывода, с правильной обработкой приоритетов и скобок.

Содержание

Основы реализации стека

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

Базовый стек на массиве

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

Альтернативная реализация стека

Согласно обсуждениям на Stack Overflow, стек можно реализовать и с помощью unshift() и pop(), хотя это реже используется из‑за проблем с производительностью unshift().

javascript
class StackAlternative {
  constructor() {
    this.items = [];
  }
  
  push(element) {
    this.items.unshift(element);
  }
  
  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }
  
  // ... остальные методы такие же, как выше
}

Основы реализации очереди

Очередь — это структура данных FIFO (First‑In‑First‑Out), где элементы добавляются в конец и удаляются с начала. В JavaScript массивы предоставляют несколько способов реализации очереди.

Базовая очередь на массиве

javascript
class Queue {
  constructor() {
    this.items = [];
  }
  
  // Добавить элемент в конец очереди
  enqueue(element) {
    this.items.push(element);
  }
  
  // Удалить и вернуть первый элемент
  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.shift();
  }
  
  // Посмотреть первый элемент без удаления
  front() {
    if (this.isEmpty()) {
      return "No elements in queue";
    }
    return this.items[0];
  }
  
  // Проверить, пуста ли очередь
  isEmpty() {
    return this.items.length === 0;
  }
  
  // Получить размер очереди
  size() {
    return this.items.length;
  }
  
  // Очистить очередь
  clear() {
    this.items = [];
  }
}

Альтернативная реализация очереди

Как упомянуто в обсуждениях на Stack Overflow, очередь можно реализовать с помощью unshift() и pop():

javascript
class QueueAlternative {
  constructor() {
    this.items = [];
  }
  
  enqueue(element) {
    this.items.unshift(element);
  }
  
  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }
  
  // ... остальные методы такие же, как выше
}

Требования к алгоритму Шунтинг‑Йарда

Алгоритм Шунтинг‑Йарда требует конкретных операций со стеком и очередью для преобразования инфиксных выражений в постфиксную нотацию. Согласно Wikipedia, алгоритм обрабатывает токены слева направо, используя стек для операторов и выводя результат в очередь.

Ключевые требования

  1. Стек для операторов: должен поддерживать операции push и pop
  2. Очередь для вывода: должна поддерживать операции enqueue
  3. Обработка приоритетов: необходимо сравнивать приоритеты операторов
  4. Управление скобками: необходимо обрабатывать открывающие и закрывающие скобки

Шаги алгоритма

Алгоритм работает следующим образом:

  1. Чтение токенов слева направо
  2. Если токен — число, помещаем его в очередь вывода
  3. Если токен — оператор:
    • Пока на вершине стека находится оператор с более высоким приоритетом, извлекаем его в очередь вывода
    • Пушим текущий оператор в стек
  4. Если токен — открывающая скобка, пушим её в стек
  5. Если токен — закрывающая скобка:
    • Извлекаем операторы из стека в очередь вывода до тех пор, пока не найдём открывающую скобку
    • Удаляем и игнорируем открывающую скобку
  6. После чтения всех токенов извлекаем оставшиеся операторы из стека в очередь вывода

Полный пример реализации

Создадим полную реализацию алгоритма Шунтинг‑Йарда, используя наши классы стека и очереди:

javascript
class Stack {
  constructor() {
    this.items = [];
  }
  
  push(element) {
    this.items.push(element);
  }
  
  pop() {
    if (this.isEmpty()) {
      throw new Error("Stack underflow");
    }
    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;
  }
}

class Queue {
  constructor() {
    this.items = [];
  }
  
  enqueue(element) {
    this.items.push(element);
  }
  
  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue underflow");
    }
    return this.items.shift();
  }
  
  isEmpty() {
    return this.items.length === 0;
  }
  
  size() {
    return this.items.length;
  }
  
  toArray() {
    return [...this.items];
  }
}

class ShuntingYard {
  constructor() {
    this.operatorPrecedence = {
      '^': 4,
      '*': 3,
      '/': 3,
      '+': 2,
      '-': 2,
      '(': 1
    };
  }
  
  isOperator(token) {
    return token in this.operatorPrecedence;
  }
  
  hasHigherPrecedence(op1, op2) {
    return this.operatorPrecedence[op1] >= this.operatorPrecedence[op2];
  }
  
  tokenize(expression) {
    // Простой токенизатор — обрабатывает числа, операторы и скобки
    const tokens = [];
    let currentToken = '';
    
    for (let i = 0; i < expression.length; i++) {
      const char = expression[i];
      
      if (char === ' ') {
        continue;
      }
      
      if (/\d/.test(char) || char === '.') {
        currentToken += char;
      } else {
        if (currentToken) {
          tokens.push(currentToken);
          currentToken = '';
        }
        tokens.push(char);
      }
    }
    
    if (currentToken) {
      tokens.push(currentToken);
    }
    
    return tokens;
  }
  
  convertToPostfix(infixExpression) {
    const tokens = this.tokenize(infixExpression);
    const operatorStack = new Stack();
    const outputQueue = new Queue();
    
    for (const token of tokens) {
      if (!this.isOperator(token) && token !== '(' && token !== ')') {
        // Числа и идентификаторы сразу помещаем в вывод
        outputQueue.enqueue(token);
      } else if (token === '(') {
        // Открывающая скобка помещаем в стек
        operatorStack.push(token);
      } else if (token === ')') {
        // Закрывающая скобка — извлекаем операторы до открывающей скобки
        while (!operatorStack.isEmpty() && operatorStack.peek() !== '(') {
          outputQueue.enqueue(operatorStack.pop());
        }
        
        if (!operatorStack.isEmpty() && operatorStack.peek() === '(') {
          operatorStack.pop(); // Удаляем открывающую скобку
        } else {
          throw new Error("Mismatched parentheses");
        }
      } else if (this.isOperator(token)) {
        // Оператор — извлекаем операторы с более высоким или равным приоритетом
        while (!operatorStack.isEmpty() && 
               operatorStack.peek() !== '(' && 
               this.hasHigherPrecedence(operatorStack.peek(), token)) {
          outputQueue.enqueue(operatorStack.pop());
        }
        operatorStack.push(token);
      }
    }
    
    // Извлекаем оставшиеся операторы из стека
    while (!operatorStack.isEmpty()) {
      const op = operatorStack.pop();
      if (op === '(') {
        throw new Error("Mismatched parentheses");
      }
      outputQueue.enqueue(op);
    }
    
    return outputQueue.toArray();
  }
}

// Пример использования
const shuntingYard = new ShuntingYard();
const infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
const postfix = shuntingYard.convertToPostfix(infix);
console.log("Infix:", infix);
console.log("Postfix:", postfix.join(' '));

Обработка более сложных случаев

Для более сложных выражений с функциями и несколькими типами операторов можно расширить реализацию:

javascript
// Расширенный класс ShuntingYard с поддержкой функций
class ExtendedShuntingYard extends ShuntingYard {
  constructor() {
    super();
    this.operatorPrecedence = {
      '^': 4,
      '*': 3,
      '/': 3,
      '+': 2,
      '-': 2,
      'sin': 5,
      'cos': 5,
      'tan': 5,
      '(': 1
    };
  }
  
  isFunction(token) {
    return ['sin', 'cos', 'tan'].includes(token);
  }
  
  convertToPostfix(infixExpression) {
    const tokens = this.tokenize(infixExpression);
    const operatorStack = new Stack();
    const outputQueue = new Queue();
    
    for (const token of tokens) {
      if (!this.isOperator(token) && !this.isFunction(token) && 
          token !== '(' && token !== ')' && token !== ',') {
        // Числа и идентификаторы сразу помещаем в вывод
        outputQueue.enqueue(token);
      } else if (this.isFunction(token)) {
        // Функции помещаем в стек
        operatorStack.push(token);
      } else if (token === '(') {
        // Открывающая скобка помещаем в стек
        operatorStack.push(token);
      } else if (token === ')') {
        // Закрывающая скобка — извлекаем операторы до открывающей скобки
        while (!operatorStack.isEmpty() && operatorStack.peek() !== '(') {
          outputQueue.enqueue(operatorStack.pop());
        }
        
        if (!operatorStack.isEmpty() && operatorStack.peek() === '(') {
          operatorStack.pop(); // Удаляем открывающую скобку
          
          // Проверяем, является ли следующий элемент функцией
          if (!operatorStack.isEmpty() && this.isFunction(operatorStack.peek())) {
            outputQueue.enqueue(operatorStack.pop());
          }
        } else {
          throw new Error("Mismatched parentheses");
        }
      } else if (token === ',') {
        // Разделитель аргументов функции — извлекаем операторы до открывающей скобки
        while (!operatorStack.isEmpty() && operatorStack.peek() !== '(') {
          outputQueue.enqueue(operatorStack.pop());
        }
      } else if (this.isOperator(token)) {
        // Оператор — извлекаем операторы с более высоким или равным приоритетом
        while (!operatorStack.isEmpty() && 
               operatorStack.peek() !== '(' && 
               this.hasHigherPrecedence(operatorStack.peek(), token)) {
          outputQueue.enqueue(operatorStack.pop());
        }
        operatorStack.push(token);
      }
    }
    
    // Извлекаем оставшиеся операторы из стека
    while (!operatorStack.isEmpty()) {
      const op = operatorStack.pop();
      if (op === '(') {
        throw new Error("Mismatched parentheses");
      }
      outputQueue.enqueue(op);
    }
    
    return outputQueue.toArray();
  }
}

Проблемы производительности

При реализации стеков и очередей для алгоритма Шунтинг‑Йарда стоит учитывать следующие аспекты производительности:

Производительность массивов

  • Операции со стеком: push() и pop() — O(1) в массивах JavaScript
  • Операции с очередью: push() и shift() — O(n) из‑за переиндексации массива
  • Альтернативная очередь: unshift() и pop() также O(n)

Техники оптимизации

Для более эффективной работы с большими выражениями:

javascript
// Оптимизированная очередь, использующая два стека
class OptimizedQueue {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }
  
  enqueue(element) {
    this.stack1.push(element);
  }
  
  dequeue() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop();
  }
  
  isEmpty() {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }
  
  size() {
    return this.stack1.length + this.stack2.length;
  }
}

Память

  • Память стека: обычно не растёт слишком сильно
  • Память очереди: растёт линейно с размером входа
  • Токенизация: предварительная токенизация выражений помогает избежать повторной обработки

Расширенные возможности

Обработка ошибок

javascript
class ShuntingYardWithValidation extends ShuntingYard {
  validateExpression(expression) {
    // Проверка сбалансированных скобок
    let parenCount = 0;
    for (const char of expression) {
      if (char === '(') parenCount++;
      if (char === ')') parenCount--;
      if (parenCount < 0) return false;
    }
    if (parenCount !== 0) return false;
    
    // Проверка допустимых операторов и операндов
    const validTokens = /[\d\+\-\*\/\^\(\)\s]+/;
    if (!validTokens.test(expression.replace(/sin|cos|tan/g, ''))) {
      return false;
    }
    
    return true;
  }
  
  convertToPostfix(infixExpression) {
    if (!this.validateExpression(infixExpression)) {
      throw new Error("Invalid expression");
    }
    return super.convertToPostfix(infixExpression);
  }
}

Поддержка многозначных чисел

javascript
class AdvancedShuntingYard extends ShuntingYard {
  tokenize(expression) {
    const tokens = [];
    let currentToken = '';
    
    for (let i = 0; i < expression.length; i++) {
      const char = expression[i];
      
      if (char === ' ') {
        continue;
      }
      
      // Обработка многозначных чисел и десятичных дробей
      if (/\d/.test(char) || char === '.') {
        currentToken += char;
      } else {
        if (currentToken) {
          tokens.push(currentToken);
          currentToken = '';
        }
        tokens.push(char);
      }
    }
    
    if (currentToken) {
      tokens.push(currentToken);
    }
    
    return tokens;
  }
}

Поддержка переменных

javascript
class VariableSupportShuntingYard extends ShuntingYard {
  constructor() {
    super();
    this.variables = new Map();
  }
  
  setVariable(name, value) {
    this.variables.set(name, value);
  }
  
  tokenize(expression) {
    // Расширенный токенизатор, обрабатывающий переменные
    const tokens = [];
    let currentToken = '';
    
    for (let i = 0; i < expression.length; i++) {
      const char = expression[i];
      
      if (char === ' ') {
        continue;
      }
      
      // Переменные могут содержать буквы и цифры
      if (/[a-zA-Z]/.test(char)) {
        currentToken += char;
      } else if (/\d/.test(char) || char === '.') {
        currentToken += char;
      } else {
        if (currentToken) {
          tokens.push(currentToken);
          currentToken = '';
        }
        tokens.push(char);
      }
    }
    
    if (currentToken) {
      tokens.push(currentToken);
    }
    
    return tokens;
  }
}

Заключение

Реализация стеков и очередей в JavaScript для алгоритма Шунтинг‑Йарда проста благодаря методам массивов. Ключевые выводы:

  • Стек использует push() и pop() для LIFO‑поведения
  • Очередь использует push() и shift() для FIFO‑поведения
  • Алгоритм Шунтинг‑Йарда требует корректной обработки приоритетов операторов и скобок
  • Проблемы производительности включают выбор подходящей реализации очереди
  • Расширенные возможности: проверка ошибок, поддержка переменных, многозначных чисел и функций

Для продакшн‑использования рекомендуется реализовать надёжную обработку ошибок, полноценную токенизацию и валидацию входных выражений. Алгоритм Шунтинг‑Йарда работает за O(n) времени, что делает его эффективным для парсинга математических выражений.

Источники

  1. Implementing Stack and Queue in JavaScript - Stack Overflow
  2. Shunting Yard Algorithm - Wikipedia
  3. Shunting Yard Algorithm in JavaScript - InspirNathan
  4. Implementing Shunting Yard Algorithm in JavaScript - Stack Overflow
  5. Parsing/Shunting-yard algorithm - Rosetta Code
  6. Shunting Yard Algorithm - Brilliant Math & Science Wiki
  7. How can you implement a Stack and a Queue in JavaScript? - LambdaTest Community
  8. Implementing Stack and Queue in JavaScript for the Shunting-Yard Algorithm - LambdaTest Community
Авторы
НейроАгент
Автор
Проверено модерацией
НейроОтветы
Модерация
Какие различия в производительности между разными реализациями очередей в JavaScript?
Как алгоритм шунтирования обрабатывает приоритет операторов и ассоциативность?
Можно ли реализовать стек с помощью связанного списка в JavaScript?
Какие распространённые ошибки при реализации алгоритма шунтирования и как их избежать?
Как расширить алгоритм шунтирования для обработки вызовов функций и переменных?
Каковы временные и пространственные сложности операций со стеком и очередью в JavaScript?
Как реализовать стек и очередь в JavaScript