数据结构的javascript实现

一、数组

是有序的元素序列

二、栈

后进先出的有序集合

class Stack{
    constructor(){
        this.item = []
    }
    push(element){
        this.item.push(element)
    }
    pop(){
        return this.item.pop()
    }
    peek(){
        return this.item[this.item.length-1]
    }
    isEmpty(){
        return this.item.length === 0
    }
    clear(){
        this.item = []
    }
    size(){
        return this.item.length
    }
}

三、队列

先进先出的有序的项。

class Queue{
    constructor(){
        this.item = []
    }
    enqueue(element){
        this.item.push(element)
    }
    dequeue(){
        return this.item.shift()
    }
    front(){
        return this.item[0]
    }
    isEmpty(){
        return this.item.length === 0
    }
    size(){
        return this.item.length
    }
}

四、链表

链表是非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1. 单向链表

链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取

class Node{
    constructor(element){
        this.element = element
        this.next = null
    }
}
class LinkedList{
    constructor(){
        this.length = 0
        this.head = null
    }
    append(){
        let node = new Node(element),current
        if(this.head === null){
            this.head = node
        }else{
            current = this.head
            while(current.next){
                current = current.next
            }
            current.next = node
        }
        this.length++
    }
    insert(){}
    removeAt(){}
    remove(){}
    toString(){}
    indexOf(){}
    isEmpty(){}
    size(){}
}

2. 双向链表

每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

3. 循环链表

最后一个结点指向头结点，形成一个环。

五、集合

无序且唯一的项

class Set{
    constructor(){
        this.items = {}
    }
    has(value){
        return value in this.items
    }
    add(value){
        if(!this.has(value)){
            this.items[value]=[value]
            return true
        }
        else{
            return false
        }
    }
    remove(){
        if(this.has(value)){
            delete this.items[value]
            return true
        }
        else{
            return false
        }
    }
    clear(){
        this.items = {}
    }
    size(){
        return Object.keys(items).length
    }
}

六、字典

class Dictionary{
    constructor(){
        this.items = {}
    }
    has(key){
        return key in items
    }
    set(key,value){
        items[key] = value
    }
    delete(key){
        delete items[key]
    }
    get(key){
        return this.has(key) ? items[key]:undefined
    }
    clear(){
        this.items = {}
    }
}

七、散列表（哈希）

八、树

class Node {
    constructor(key) {
      this.key = key;
      this.left = null;
      this.right = null;
    }
}
class BinarySearchTree{
    constructor(){
        this.root = null
    }
    insert(){
        let newNode = new Node(element)
        function insertNode(node,newNode){
            if(newNode.key < node.key){
                if(node.left === null){
                    node.left = newNode
                }else{
                    insertNode(node.left,newNode)
                }
            }else{
                if(node.right === null){
                    node.right = newNode
                }else{
                    insertNode(node.right,newNode)
                }
            }
        }
        if(this.root === null){
            root = newNode
        }else{
            insertNode(root,newNode)
        }
    }
}

九、图