Часть 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: Как реализовать стек с использованием массивов
Цитирование