В JavaScript очереди и стеки — это фундаментальные структуры данных, используемые для управления и организации данных. В то время как очереди следуют принципу «первым пришел — первым обслужен» (FIFO), стеки придерживаются принципа «последним пришел — первым обслужен» (LIFO). Однако можно реализовать очередь с помощью стеков. В этой статье мы рассмотрим несколько способов достижения этой цели, приведя попутно примеры кода.

Метод 1: подход с двумя стеками
Одним из распространенных методов реализации очереди с использованием стеков является использование двух стеков: одного для операций постановки в очередь, а другого для операций удаления из очереди.

class Queue {
  constructor() {
    this.enqueueStack = [];
    this.dequeueStack = [];
  }
  enqueue(value) {
    this.enqueueStack.push(value);
  }
  dequeue() {
    if (this.dequeueStack.length === 0) {
      if (this.enqueueStack.length === 0) {
        return "Queue is empty";
      }
      while (this.enqueueStack.length > 0) {
        const element = this.enqueueStack.pop();
        this.dequeueStack.push(element);
      }
    }
    return this.dequeueStack.pop();
  }
  isEmpty() {
    return this.enqueueStack.length === 0 && this.dequeueStack.length === 0;
  }
}

Метод 2: эффективный подход к удалению из очереди
В предыдущем методе операция удаления из очереди имеет временную сложность O(n) в худшем случае. Однако мы можем оптимизировать операцию удаления из очереди, перемещая элементы между стеками только при необходимости.

class Queue {
  constructor() {
    this.enqueueStack = [];
    this.dequeueStack = [];
  }
  enqueue(value) {
    this.enqueueStack.push(value);
  }
  dequeue() {
    if (this.dequeueStack.length === 0) {
      if (this.enqueueStack.length === 0) {
        return "Queue is empty";
      }
      while (this.enqueueStack.length > 0) {
        const element = this.enqueueStack.pop();
        this.dequeueStack.push(element);
      }
    }
    return this.dequeueStack.pop();
  }
  isEmpty() {
    return this.enqueueStack.length === 0 && this.dequeueStack.length === 0;
  }
}

Метод 3: подход с одним стеком
Также можно реализовать очередь, используя один стек. В этом подходе элементы в стеке меняются местами, чтобы имитировать поведение FIFO.

class Queue {
  constructor() {
    this.stack = [];
  }
  enqueue(value) {
    this.stack.push(value);
  }
  dequeue() {
    if (this.stack.length === 0) {
      return "Queue is empty";
    }
    const poppedItem = this.stack.shift();
    if (this.stack.length > 0) {
      const dequeuedItem = this.dequeue();
      this.stack.unshift(poppedItem);
      return dequeuedItem;
    }
    return poppedItem;
  }
  isEmpty() {
    return this.stack.length === 0;
  }
}

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