当前位置: 首页 > Web前端 > JavaScript

Javascript学习数据结构(栈、队列、链表、双向链表)

时间:2023-03-27 14:21:23 JavaScript

栈(stack)是一种线性表,仅限于在表尾进行插入和删除操作。我们称允许插入和删除的一端为栈顶,另一端为栈底,没有任何数据元素的栈称为空栈。堆栈也称为后进先出线性列表。由于栈具有后进先出的特点,任何不在栈顶的元素都不能被访问。要想得到栈底的元素,必须先移除栈顶的元素。堆栈上的两个主要操作是将一个元素压入堆栈和从堆栈弹出一个元素。push()方法用于入栈,pop()方法用于出栈。下面的代码用于实现栈的数据结构。栈类dataStore表示数据集top表示栈顶坐标Stack{dataStore=[]top=0constructor(){}}push():入栈push(element){this.dataStore[this.top++]=element}pop():出栈pop(){letelement=this.dataStore[--this.top]this.dataStore.length=this.top返回元素}peek():返回栈顶peek(){returnthis.dataStore[this.top-1]}length():数据个数length(){return这个.top;}clear():清除堆栈clear(){this.top=0;this.dataStore.length=0}完整代码classStack{dataStore=[]top=0constructor(){}push(element){this.dataStore[this.top++]=element}pop(){letelement=this.dataStore[--this.top]this.dataStore.length=this.top返回元素}peek(){returnthis.dataStore[this.top-1]}length(){returnthis.top;}clear(){this.top=0;this.dataStore.length=0}}Queue队列是一种列表,只能在队尾插入元素,先移除元素的列表。队列用于存储按顺序排列的数据。先进先出队列的两个主要操作是:向队列中插入新元素和删除队列中的元素。插入操作也称为入队,删除操作也称为出队。入队操作在队尾插入新元素,出队操作删除队头元素。以下代码用于实现队列,实现Queue类dataStore代表数据集类Queue{dataStore=[]constructor(){}}enqueue()方法向队列尾部添加一个元素enqueue(element){这。()方法删除队头元素dataStore[0]}back(){returnthis.dataStore[this.dataStore.length-1]}toString()方法显示队列中的所有元素toString(){returnString(this.dataStore)}判断队列是否是emptyempty(){返回this.dataStore。length==0}完整代码返回this.dataStore[0]}back(){returnthis.dataStore[this.dataStore.length-1]}toString(){returnString(this.dataStore)}empty(){returnthis.dataStore.length==0}}链表链表是一组节点。每个节点都使用一个对象引用来指向其后继节点。指向另一个节点的引用称为链。链表起始节点的识别有点麻烦,所以在链表的最前面有一个特殊的节点,称为头节点。设计的链表包含两个类。Node类用于表示节点,LinkedList类提供了插入节点、删除节点、显示列表元素等辅助方法。Node类节点包含数据和指针,如下图,element表示元素next是一个指针类Node{constructor(element){this.element=elementthis.next=null}}LinkedList类链表创建默认到一个头节点classLinkedList{constructor(){this.head=newNode('head')}}find()找到一个节点//从头遍历找到find(item){letnode=this.headwhile(node&&node.element!=item){node=node.next}returnnode}findPrevious()找到目标的前一个节点findPrevious(item){letnode=this.headwhile(node.next&&node.next.element!=item){node=node.next}returnnode.next?node:null}insert()插入一个新节点插入一个节点就是将新元素节点的指针指向目标元素指针所指向的节点,然后说目标节点的指针指向新节点insert(element,item){letnode=this.find(item)if(node){letnewNode=newNode(element)newNode.next=node.nextnode.next=newNode}}remove()删除一个节点删除一个节点就是将目标节点的前一个节点指向目标节点的下一个节点remove(item){letnode=this.findPrevious(item)if(node){node.next=node.next.next}}display()打印链表display(){letnode=this.headwhile(node){console.log(node.element)node=node.next}}完整代码classNode{constructor(element){this.element=elementthis.next=null}}classLinkedList{constructor(){this.head=newNode('head')}find(item){letnode=this.headwhile(node&&node.element!=item){node=node.next}returnnode}findPrevious(item){letnode=this.headwhile(node.next&&node.next.element!=item){node=node.next}返回node.next?node:null}insert(element,item){letnode=this.find(item)if(node){让newNode=newNode(element)newNode.next=node.nextnode.next=newNode}}remove(item){letnode=this.findPrevious(item)if(node){node.next=node.next.next}}display(){letnode=this.headwhile(node){console.log(node.element)node=node.next}}}双向链表虽然从链表的头节点遍历到尾节点很简单,但是反过来,从后面到前面的遍历就不是那么简单了。通过向Node对象添加一个属性来存储到前任节点的链接会容易得多。这时候往链表中插入一个结点就需要做更多的工作了,我们需要指出该结点的正确前驱和后继。但是从链表中删除一个节点时,提高了效率,不需要再去寻找要删除节点的前驱节点。Node类双向链表的节点比单向链表的节点多了一个前驱指针。previousclassNode{constructor(element){this.element=elementthis.next=nullthis.previous=null}}实现一个双向链表classDoubleLink{constructor(){this.head=newNode('head')}}找到一个元素find(item){letnode=this.headwhile(node&&node.element!=item){node=node.next}returnnode}找到前一个元素findPrevious(item){letnode=this.headwhile(node.next&&node.next.element!=item){node=node.next}returnnode.next?node:null}找到最后一个元素findLast(){letnode=this.headwhile(node.next){node=node.next}returnnode}插入一个元素Node,除了跟单向链表操作一样,后一个节点的前驱指针必须指向要插入的节点,插入节点的前驱指针需要指向到前一个节点insert(element,item){letnode=this.find(item)if(node){letnewNode=newNode(element)newNode.previous=nodeif(node.next){node.next.previous=新节点}新节点.next=下一个节点下一个节点=newNode}}删除一个元素remove(item){letnode=this.findPrevious(item)if(node){if(node.next.next){node.next.next.previous=node}node.next=node.next.next}}打印元素display(){letnode=this.headwhile(node){console.log(node.element)node=node.next}}逆向打印链接显示dispReverse(){letnode=this.findLast()while(node){console.log(node.element)node=node.previous}}完整代码classNode{constructor(element){this.element=elementthis.next=nullthis.previous=null}}classDoubleLink{constructor(){this.head=newNode('head')}find(item){letnode=this.headwhile(node&&node.element!=item){node=node.next}返回节点}findPrevious(item){letnode=this.headwhile(node.next&&node.next.element!=item){node=node.next返回node.next?node:null}findLast(){letnode=this.headwhile(node.next){node=node.next}returnnode}insert(element,item){letnode=this.find(item)if(node)复制代码{letnewNode=newNode(element)newNode.previous=nodeif(node.next){node.next.previous=newNode}newNode.next=node.nextnode.next=newNode}}remove(item){letnode=this.findPrevious(item)if(node){if(node.next.next){node.next.next.previous=node}node.next=node.next.next}}display(){让节点=this.headwhile(node){console.log(node.element)node=node.next}}dispReverse(){letnode=this.findLast()while(node){console.log(node.element)node=node.previous}}}