关于javascript:javascript学习数据结构栈队列链表双向链表

56次阅读

共计 5724 个字符，预计需要花费 15 分钟才能阅读完成。

栈

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。咱们把容许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表 因为栈具备后入先出的特点，所以任何不在栈顶的元素都无法访问。为了失去栈底的元素，必须先拿掉下面的元素。



对栈的两种次要操作是将一个元素压入栈和将一个元素弹出栈。入栈应用 push()办法，出栈应用 pop()办法，上面用代码实现栈这种数据结构

实现栈类

  1. dataStore 代表数据集

  2. top 代表栈顶坐标

    class Stack{dataStore=[]
  top=0
  constructor(){}
}

    push(): 进栈

push(element){this.dataStore[this.top++] = element
  }

pop(): 出栈

pop(){let element = this.dataStore[--this.top]
    this.dataStore.length = this.top
    return element
  }

peek(): 返回栈顶

peek(){return this.dataStore[this.top-1]
  }

length(): 数据的数量

length() {return this.top;}

clear(): 清空栈

clear() {
    this.top = 0;
    this.dataStore.length=0
  }

残缺代码

class Stack {dataStore = []
    top = 0
    constructor() {}
    push(element) {this.dataStore[this.top++] = element
    }
    pop() {let element = this.dataStore[--this.top]
        this.dataStore.length = this.top
        return element
    }
    peek() {return this.dataStore[this.top - 1]
    }
    length() {return this.top;}
    clear() {
        this.top = 0;
        this.dataStore.length = 0
    }
}

队列

队列是一种列表，一种只能在队尾插入元素，在队首删除元素的列表。队列用于存储按顺序排列的数据，先进先出队列的两种次要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。


上面用代码实现队列

实现 Queue 类

dataStore 代表数据集

class Queue {dataStore = []
    constructor() {}
}

enqueue() 办法向队尾增加一个元素

enqueue(element) {this.dataStore.push(element)
    }

dequeue() 办法删除队首的元素

dequeue() {return this.dataStore.shift()
    }

能够应用如下办法读取队首和队尾的元素

front() {return this.dataStore[0]
}
back() {return this.dataStore[this.dataStore.length - 1]
}

toString() 办法显示队列内的所有元素

toString() {return String(this.dataStore)
    }

判断队列是否为空

empty() {return this.dataStore.length == 0}

实现代码

class Queue {dataStore = []
    constructor() {}
    enqueue(element) {this.dataStore.push(element)
    }
    dequeue() {return this.dataStore.shift()
    }
    front() {return this.dataStore[0]
    }
    back() {return this.dataStore[this.dataStore.length - 1]
    }
    toString() {return String(this.dataStore)
    }
    empty() {return this.dataStore.length == 0}
}

链表

链表是由一组节点组成的汇合。每个节点都应用一个对象的援用指向它的后继。指向另一个节点的援用叫做链。标识出链表的起始节点却有点麻烦，因而在链表最后面有一个非凡节点，叫做头节点


设计的链表蕴含两个类。Node 类用来示意节点，LinkedList 类提供了插入节点、删除节点、显示列表元素的办法，以及其余一些辅助办法。

Node 类
节点蕴含数据和指针，如下图所示

  1. element 代表元素

  2. next 为指针

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

    LinkedList 类

链表创立默认给个头结点

class LinkedList {constructor(){this.head = new Node('head')
  }
}

find()查找一个节点

// 从头遍历开始查找
find(item){
    let node = this.head
    while(node&&node.element != item){node = node.next}
    return node
  }

findPrevious()查找指标前一个节点

findPrevious(item){
    let node = this.head
    while(node.next&&node.next.element != item){node = node.next}
    return node.next?node:null
  }

insert()插入新节点


插入节点是将新元素节点的指针指向指标元素指针指向的节点，再讲指标节点的指针指向新节点

insert(element,item){let node = this.find(item)
    if(node){let newNode = new Node(element)
      newNode.next =  node.next
      node.next = newNode
    }
  }

remove()删除一个节点


删除节点是将指标节点的上一个节点指向指标节点的下一个节点

remove(item){let node = this.findPrevious(item)
    if(node){node.next = node.next.next}
  }

display()打印链表

display(){
    let node = this.head
    while(node){console.log(node.element)
      node = node.next
    }
  }

残缺代码

class Node {constructor(element) {
        this.element = element
        this.next = null
    }
}
class LinkedList {constructor() {this.head = new Node('head')
    }
    find(item) {
        let node = this.head
        while (node && node.element != item) {node = node.next}
        return node
    }
    findPrevious(item) {
        let node = this.head
        while (node.next && node.next.element != item) {node = node.next}
        return node.next ? node : null
    }
    insert(element, item) {let node = this.find(item)
        if (node) {let newNode = new Node(element)
            newNode.next = node.next
            node.next = newNode
        }
    }
    remove(item) {let node = this.findPrevious(item)
        if (node) {node.next = node.next.next}

    }
    display() {
        let node = this.head
        while (node) {console.log(node.element)
            node = node.next
        }
    }
}

双向链表

只管从链表的头节点遍历到尾节点很简略，但反过来，从后向前遍历则没那么简略。通过给 Node 对象减少一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链表插入一个节点须要更多的工作，咱们须要指出该节点正确的前驱和后继。然而在从链表中删除节点时，效率进步了，不须要再查找待删除节点的前驱节点了

Node 类

双向链表的节点比单向链表的节点多了一个前驱指针 previous

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

}

实现双向链表

class DoubleLink{constructor(){this.head = new Node('head')
  }
}

查找一个元素

find(item){
    let node = this.head
    while(node&&node.element != item){node = node.next}
    return node
  }

查找前一个元素

findPrevious(item){
    let node = this.head
    while(node.next&&node.next.element != item){node = node.next}
    return node.next?node:null
  }

查找最初一个元素

findLast(){
    let node = this.head
    while(node.next){node = node.next}
    return node
  }

插入一个元素


插入节点，除了和单向链表一样的操作外，后一个节点的前驱指针得指向要插入的节点，插入的节点的前驱指针须要指向前一个节点

insert(element,item){let node = this.find(item)
    if(node){let newNode = new Node(element)
      newNode.previous = node
      if(node.next){node.next.previous = newNode}
      newNode.next =  node.next
      node.next = newNode
    }
  }

删除一个元素

remove(item){let node = this.findPrevious(item)
    if(node){if(node.next.next){node.next.next.previous = node}
      node.next = node.next.next
    }

  }

打印元素

display(){
    let node = this.head
    while(node){console.log(node.element)
      node = node.next
    }
  }

逆向打印链表

dispReverse(){let node = this.findLast()
    while(node){console.log(node.element)
      node = node.previous
    }
  }

残缺代码

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

class DoubleLink {constructor() {this.head = new Node('head')
    }
    find(item) {
        let node = this.head
        while (node && node.element != item) {node = node.next}
        return node
    }
    findPrevious(item) {
        let node = this.head
        while (node.next && node.next.element != item) {node = node.next}
        return node.next ? node : null
    }
    findLast() {
        let node = this.head
        while (node.next) {node = node.next}
        return node
    }
    insert(element, item) {let node = this.find(item)
        if (node) {let newNode = new Node(element)
            newNode.previous = node
            if (node.next) {node.next.previous = newNode}
            newNode.next = node.next
            node.next = newNode
        }
    }
    remove(item) {let node = this.findPrevious(item)
        if (node) {if (node.next.next) {node.next.next.previous = node}
            node.next = node.next.next
        }
    }
    display() {
        let node = this.head
        while (node) {console.log(node.element)
            node = node.next
        }
    }
    dispReverse() {let node = this.findLast()
        while (node) {console.log(node.element)
            node = node.previous
        }
    }
}

正文完
javascript
发表至： javascript
2021-12-16
 0
面试
关于javascript:函数柯里化
关于javascript:HTML元素的heightoffsetHeightclientHeightscrollTop等梳理
关于javascript:javascript高级程序设计学习笔记-1091011函数内部