Структура на данните на опашката

Част 2: Внедряване на опашка с помощта на единично свързан списък

Опашката е структура от данни, която следва принципа First-In/First-Out (популярно известен като FIFO), което означава, че първият добавен елемент ще бъде първият премахнат.

Създаване на нов възел

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

Създаване на клас на опашка

class Queue {
  constructor(value){
    const newNode = new Node(value)
    this.first = newNode
    this.last = newNode
    this.length = 1
  }
}

//creating new instance of Queue class
let q1 = new Queue(10)

Добавяне на възел към края на списъка

//PROCESS:
    //create new Node using Node class
  
    //if list is empty:
      //set the first and last to equal to new Node
    //else
      //add Node to the end of list

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

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

Премахване на първия възел от списъка

 //PROCESS:
  
    //if list is empty:
      // return undefined
  
    //create pointer variable and set it to first Node in list
  
    //if list has 1 Node:
      // set the first and last to point to null
    //else
      //set the second node in list as the head
      //remove the first node in the list

    //reduce length by 1
    //return the Node that was deleted
  

  dequeue(){
    if(this.length === 0) return undefined
    
    const temp = this.first

    if(this.length === 1){
      this.first = null
      this.last = null
    } else {   
      this.first = this.first.next
      temp.next = null
    }

    this.length--
    return temp
  }

Как изглежда всичко заедно

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

class Queue {
  constructor(value){
    const newNode = new Node(value)
    this.first = newNode
    this.last = newNode
    this.length = 1
  }

  
  //ADDING NODE TO END OF LIST
  enqueue(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.first = newNode
      this.last = newNode
    } else {
      this.last.next = newNode
      this.last = newNode
    }
    this.length++
    return this
  }
  
  //REMOVING NODE FROM BEGINNING OF LIST
  dequeue(){
    if(this.length === 0) return undefined
    
    const temp = this.first

    if(this.length === 1){
      this.first = null
      this.last = null
    } else {   
      this.first = this.first.next
      temp.next = null
    }

    this.length--
    return temp
  }
}

//creating new instance of Queue class
let q1 = new Queue(10)

//adding node at the end of list
q1.enqueue(20)

//removing node at the beginning of list
q1.dequeue()

Вижте част 1: Имплементиране на опашка с помощта на масиви

Цитиране