Структура данных стека

Часть 2.Реализация стека с использованием односвязного списка

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

Создание нового узла

class Node {
  constructor(value){
    this.value = value
    this.next = null
  }
}

Создание класса стека

//PROCESS: 
  //create new Node using the Node class
  //set the new Node as the top item
  //increase the length by 1
  
class Stack {
  constructor(value){
    const newNode = new Node(value)
    this.top = newNode
    this.length = 1
  }
  
}

//creating new instance of Stack class
let stack1 = new Stack(10)

Добавление элементов в список

Более эффективно добавлять и удалять элементы в начале связанного списка, поскольку временная сложность обеих операций будет O(1). В противном случае временная сложность становится O(n) при удалении элемента в конце списка. Это связано с тем, что для этой операции требуется сначала просмотреть список, чтобы удалить последний узел.

//PROCESS:
    //create new Node using the Node class

    //if stack is empty:
      //set the new Node as the top
    //else
      //set the new Node to point to the first Node in list
      //set the new Node as the first Node in list

    //increase length by 1
    //return enire list
    
  addNode(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.top = newNode
    } else {    
      newNode.next = this.top
      this.top = newNode
    }
    this.length++
    return this  
  }

Удаление узла из списка

  //PROCESS:
    //create a variable that points to the first Node in list

    //if stack is empty:  
      //return undefined
  
    //else
      //remove return Node from list 
      //reduce length of list by 1
     // return the Node that was deleted

  
  removeNode(){
    let temp = this.top;
    
    if(this.length === 0){
      return undefined
    }
    //removes node from list
    this.top = this.top.next
    temp.next = null
    
    this.length--
    return temp
  }

Как это все выглядит вместе

class Node {
  constructor(value){
    this.value = value
    this.next = null
  }
}

class Stack {
  constructor(value){
    const newNode = new Node(value)
    this.top = newNode
    this.length = 1
  }

    //ADDING NEW NODE TO LIST
  addNode(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.top = newNode
    } else {    
      newNode.next = this.top
      this.top = newNode
    }
    this.length++
    return this  
  }

  //REMOVING NODE FROM LIST
  removeNode(){
    let temp = this.top;
    
    if(this.length === 0){
      return undefined
    }
    //removes node from list
    this.top = this.top.next
    temp.next = null
    
    this.length--
    return temp
  }
}

//creating new instance of Stack class
let stack1 = new Stack(10)

//adding new node to the 'stack1' instance
stack1.addNode(20)

Ознакомьтесь с частью 1: Как реализовать стек с использованием массивов

Цитирование