Очередь с двумя стеками - PullRequest
Новая
       29

Очередь с двумя стеками

0 голосов
/ 06 октября 2018

Я реализовал очередь с двумя стеками, например, так: 

class QueueTwoStacks {
  constructor() {
    this.stack1 = []
    this.stack2 = []
  }
  enqueue(item) {
    this.stack1.push(item)
    const lastItem = this.stack1.pop()
    this.stack2.push(lastItem)
    const lastItem2 = this.stack2.pop()
    this.stack1.push(lastItem2)
  }

  dequeue() {
    if(this.stack1.length === 0) throw Error
    return this.stack1.shift();
  }
}

Курс, на который я следую, дал ответ: 

class QueueTwoStacks {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

  enqueue(item) {
    this.inStack.push(item);
  }

  dequeue() {
    if (this.outStack.length === 0) {

      // Move items from inStack to outStack, reversing order
      while (this.inStack.length > 0) {
        const newestInStackItem = this.inStack.pop();
        this.outStack.push(newestInStackItem);
      }

      // If outStack is still empty, raise an error
      if (this.outStack.length === 0) {
        throw new Error("Can't dequeue from empty queue!");
      }
    }
    return this.outStack.pop();
  }
}

Один лучше другого,и если да, то почему?Я чувствую, что мое решение лучше, потому что вам не нужно зацикливаться, но, возможно, вы не должны выполнять всю операцию в методе enqueue?

1 Ответ

0 голосов
/ 07 октября 2018

Проблема в том, что ваша реализация имеет O (n) сложность времени для dequeue КАЖДОГО времени, потому что вы звоните shift.С другой стороны, pop является операцией O (1).Для более подробной информации, вы можете проверить этот вопрос .

Обратите внимание, что в вашей реализации вы можете в значительной степени избавиться от stack2 в целом, и он все равно будет работать (конечно, с тем же недостатком, что у вас будет O (n) dequeue): 

class QueueTwoStacks {
  constructor() {
    this.stack1 = []
    // this.stack2 = []
  }
  enqueue(item) {
    this.stack1.push(item)
    // const lastItem = this.stack1.pop()
    // this.stack2.push(lastItem)
    // const lastItem2 = this.stack2.pop()
    // this.stack1.push(lastItem2)
  }

  dequeue() {
    if(this.stack1.length === 0) throw Error
    return this.stack1.shift();
  }
}

Вторая реализация, однако, только изредка перемещает элементы в outStack (т.е. только когда он пуст) и использует pop для своей операции dequeue.Таким образом, хотя наихудшим случаем по-прежнему является O (n), в среднем случае dequeue в этой реализации должно быть O (1), что значительно лучше, чем O (n), особенно если вы собираетесь его вызыватьмного раз.

...