Аффирмация дня: Я знаю, что могу реализовать свои желания 🌟

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

Стеки:

Аналогия.Представьте, что у вас есть банка с тремя теннисными мячами. Вы не можете достать первый теннисный мяч, который положили в банку, не вынув второй теннисный мяч. Точно так же вы не можете достать второй теннисный мяч, не убрав третий теннисный мяч. Таким образом, чтобы убрать первый теннисный мяч, вам нужно сначала убрать третий теннисный мяч, затем второй теннисный мяч, а затем третий (последним пришел первым вышел).

Стеки допускают операции только на одном конце, то есть вставка или удаление элемента может выполняться только в верхней части стека (ниже мы увидим, почему). Как упоминалось выше, стеки основаны на принципе «последним пришел — первым ушел» (LIFO, если кто-то входит последним, тот уходит первым).

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

Распространенным способом реализации стека является массив. На самом деле стеки лучше всего реализуются с помощью массивов, потому что код короче, а его производительность (сложность по времени) лучше, чем реализация со связанным списком в JavaScript. Почему? Потому что…

  1. Когда вы что-то добавляете в конец массива или удаляете, это 0(1).
  2. Когда вы добавляете или удаляете что-то в начало массива, вам нужно все переиндексировать, чтобы получилось 0(n).

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

ГЛАВНЫЙ СОВЕТ: мы извлекаем что-то из стека или помещаем что-то в стек (это делается наверху). Эти два метода используются для удаления и добавления элемента в конец массива! Следовательно, извлечение и удаление элементов из вершины стека равно 0(1).

Давайте реализуем стек с массивом!

A: Мы создаем наш новый массив

let stack = [];

B: Мы создаем наш метод push, чтобы получить элемент в качестве аргумента и добавить элемент в наш массив стека.

const push = (item) => stack.push(item);

C: Мы создаем метод pop для удаления последнего элемента стека. Поскольку мы не знаем, какой элемент является последним, эта функция не имеет аргумента.

const pop = () => stack.pop();

Давайте реализуем стек со связанным списком!

Как упоминалось выше, вставка или удаление в стеке выполняется сверху (в начале). В связанном списке это происходит потому, что когда вы удаляете элемент из конца связанного списка, это 0 (n), а чтобы добавить его обратно в конец, это 0 (1). Однако в начале связанного списка удалить и добавить 0(1) операций.

Стек: нажать()

push(value){
const newNode = new Node (value
if(this.length === 0){
this.top = newNode;
} else{
      newNode.next = this.top;
      this.top = newNode
  }
this.length++ //we increment the length
return this // returning the entire stack 
}

//we make an if statement for when the stack is empty and if it's not empty we do the else statement

Стек: Поп()

pop(){
if(this.length === 0) return undefined //empty stack
let temp = this.top //we need a variable to point to the item we're going to return
this.top = this.top.next //this line moves the top down
temp.next = null // breaks the element off from the rest of the stack
this.length-- //we decrement the length
return temp //we're returning this node that we popped off from the stack
}

Очередь:

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

Давайте реализуем очередь с помощью массива!

A: Мы создаем наш новый массив

let stack [];

B: Мы создаем нашу функцию, чтобы добавить элемент в нашу очередь

const enqueue = (item) => queue.push(item);

C: Мы создаем функцию для удаления первого элемента из нашей очереди

const dequeue = () => queue.shift();

Давайте реализуем очередь, используя связанный список!

Поскольку мы реализуем очереди со связанными списками, лучше ставить в очередь (добавлять) с конца, так как это 0(1), и исключать из очереди (удалять) с начала 0(1).

Очередь: Очередь

NB: хотя мы добавляем новый узел, мы не используем метод с именем push, мы используем enqueue. Но enqueue во многом заимствует метод push из связанного списка.

enqueue(value){
const newNode = new Node (value)
if (this.length === 0) {
this.first = newNode
this.last = newNode //this if statement is for an empty queue
  } else{
      this.last.next = newNode //moves the 'last' variable to the node we want to add that's at the end
       this.last = newNode
  }
  this.length++
return this //returning the entire queue
}

Очередь: Dequeue (удаление элемента)

deqeue(){
if (this.length === 0) return undefined //no items in the queue
let temp = this.first //if there are items, we need to create a variable to point at the item we're going to return
if(this.length === 1){
this.first = null
this.last = null //this if statement is for if the queue has only one item
 } else{
      this.first = this.first.next //moves first over to the second node in the queue (the next node)
      temp.next = null //this breaks off the node we want to remove from the queue
 }
this.length-- //we decrement the queue
return temp //we return the node that was removed
}