DS с JS - стек и очередь

Структуры данных с помощью JavaScript - Глава 3 - Стеки и очереди

❗️Все фрагменты кода, которые вы увидите ниже, являются псевдокодом. Если хотите увидеть рабочий код - нажмите здесь

Предпосылки

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

1. DS с JS - Связанные списки
2. DS с JS - Связанные списки - II

Зачем использовать связанные списки при реализации стеков и очередей?

Я нашел несколько строк по этому поводу -

… Поскольку связанные списки хранят элементы данных в линейной последовательности, их можно использовать для предоставления альтернативных реализаций стеков и очередей. Одним из преимуществ использования связанных списков является то, что нам не нужно беспокоиться о заполнении чего-то вроде массива - мы можем просто выделять ячейки столько, сколько нам нужно (если у нас не закончится память). Реализовать стек с использованием связанного списка особенно просто, потому что все обращения к стеку находятся наверху. Один конец связанного списка, начало, всегда доступен напрямую. Поэтому мы должны расположить элементы так, чтобы верхний элемент стека находился в начале связанного списка, а нижний элемент стека находился в конце связанного списка. Мы можем представить пустой стек с нулевым значением…

Другая причина заключается в том, что вы сможете практиковать связанные списки при реализации стеков и очередей, которые дадут вам понимание того, как работают стеки и очереди, и сделают вас сильными с помощью связанных списков.

полностью прочитать статью здесь ..

Давай начнем!!

Основной

⚜️ Список

1. Толкать
2. Поп
3. Подглядывать
4. Задний ход
5. Длина
6. Поиск
7. Пустой
8. Траверс

А теперь давайте напишем код…

🔅 Нажать

push( item ){
   let node = new Node( item )
   if( this.top ) {
     node.next = this.top
     this.top = node
   } else {
     this.top = node
   }
}

🔅 Поп

pop() {
  if( this.top ) {
    let itemToPop = this.top
    this.top = this.top.next
    return itemToPop.data
  } else {
    log('Stack is empty!')
    return false;
  }
}

🔅 Подглядывать

peek() {
  if( this.top ) {
   return this.top.data
  } else {
   return null
  }
}

🔅 Реверс

reverse() {
  let current = this.top
  let prev = null;
  while( current ) {
    let next = current.next
    current.next = prev
    prev = current
    current = next
  }
  this.top = prev
}

⚠️ Это то же самое, что перевернуть односвязный список

🔅 Длина, поиск и пусто

length() {
  let current = this.top
  let counter = 0
  while( current ) {
   counter++
   current = current.next
  }
  return counter
}

search( item ) {
  let current = this.top
  while( current ) {
   if( current.data === item ) return true
   current = current.next
  }
  return false
}

isEmpty() {
  return this.length > 1
}

🔅 Траверс

traverse( fn ) {
  let current = this.top
  while( current ) {
   fn( current )
   current = current.next
  }
}

Основной

⚜️ Список

1. Поставить в очередь
2. Dequeue
3. Длина
4. Подглядывать
5. Пустой
6. Траверс

🔅 Поставить в очередь

enqueue( item ) {
   let node = new Node( item )
   if( !this.head  ) {
     this.head = node
     this.tail = node
   } else {
     this.tail.next = node
     this.tail = node
   }
}

🔅 Dequeue

dequeue() {
  if( !this.head ) {
   return 'No item'
  } else {
   let itemToPop = this.head
   this.head = this.head.next
   return itemToPop
  }
}

🔅 Длина, вид и пусто

length() {
  let current, counter
  [ current, counter ] = [ this.head, 0 ]
  while( current ) {
   counter++
   current = current.next
  }
  return counter
}
peek() {
  if( this.head ) {
   return this.head.data
  } else {
   return 'Empty'
  }
}
isEmpty() {
  return this.length() < 1
}

🔅 Траверс

traverse( fn ) {
  let current = this.head
  while( current ) {
   fn( current )
   current = current.next
  }
}

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

Упражняться

• Hackerrank - Структуры данных

Последнее важное…

Об этом посте

Этот пост является третьим выпуском из серии «DS с JS». В этой серии будет больше. Следующее будет в следующий понедельник утром. Следите за обновлениями!

Это оно

Удачного кодирования !!

🎧 Прослушивание Touch - Matia Cupelli. Печаль, разбитое сердце, фортепиано и мечты ... не хватает только этой музыки ...

Если вам понравилась эта статья, пожалуйста, похлопайте по ней 👏 и поделитесь ею! Если вам не нравится этот пост или у вас есть какие-либо вопросы относительно всего, что я упомянул в этом посте. Не стесняйтесь спрашивать меня. Просто опубликуйте вопрос в моем разделе Спроси меня о чем угодно, нажав здесь.

Если это так, подписывайтесь на меня на Medium или Twitter. Чтобы задать вопрос, перейдите по этой ссылке. Подробнее обо мне на моем сайте.