传送门

一、栈结构

1、封装栈结构及方法

function Stack() {
    //栈属性
    this.items = [];

    // 入栈
    Stack.prototype.push = function(element) {}

    // 出栈
    Stack.prototype.pop = function() {}

    // 查看栈顶元素
    Stack.prototype.peek = function() {}

    // 判断栈是否为空
    Stack.prototype.isEmty = function() {}

    // 查看栈长度
    Stack.prototype.size = function() {}

    // toString 方法
    Stack.prototype.toString = function() {}
}

2、具体方法实现

• 入栈

Stack.prototype.push = function(element) {
        // 在数组的尾部压入元素
        return this.items.push(element);
    }

• 出栈

Stack.prototype.pop = function() {
        // 从数组尾部删除元素，并返回栈顶元素
        return this.items.pop();
    }

• 查看栈顶元素

Stack.prototype.peek = function() {
        // 从数组尾部查看元素
        return this.items[this.items.length - 1];
    }

• 判断栈是否为空

Stack.prototype.isEmty = function() {
        // 判断数组是否为空
        return this.items.length === 0;
    }

• 查看栈长度

Stack.prototype.size = function() {
        // 查看数组长度
        return this.items.length;
    }

• toString 方法

Stack.prototype.toString = function() {
        let resultString = '';
        // 遍历数组
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i] + ''
        }
        return resultString
    }

二、队列结构

1、封装队列结构及方法

// 队列封装
function Queue() {
    // 属性
    this.items = [];
     
    // 入队
    Queue.prototype.enqueue = function(element) {}
    
    // 出队
    Queue.prototype.inqueue = function() {}
    
    // 查看队头元素
    Queue.prototype.front = function() {}
    
    // 判断队列是否为空
    Queue.prototype.isEmpty = function() {}
    
    //查看队列长度
    Queue.prototype.size = function() {}
    
    // toString 方法
    Queue.prototype.toString = function() {}
}

2、 具体方法实现

• 入队

Queue.prototype.enqueue = function(element) {
        // 在数组的尾部添加元素
        return this.items.push(element);
    }

• 出队

Queue.prototype.inqueue = function() {
        // 从数组中删除队头元素，并返回队头元素
        return this.items.shift();
    }

• 查看队头元素

Queue.prototype.front = function() {
        // 从数组中查看数组第一个元素
        return this.items[0];
    }

• 判断队列是否为空

Queue.prototype.isEmpty = function() {
        // 判断数组是否为空
        return this.items.length === 0;
    }

• 查看队列长度

Queue.prototype.size = function() {
        // 查看数组长度
        return this.items.length;
    }

• toString 方法

Queue.prototype.toString = function() {
        let resultString = '';
        // 遍历数组
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i] + ''
        }
        return resultString
    }

三、优先级队列结构

1、 封装优先级队列结构及方法

function PriorityQueue() {
    
    // 元素包含两部分 element 数据 priority 优先级
    function QueueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }
    
    // 封装属性
    this.items = [];
    
    // 实现插入方法
    PriorityQueue.prototype.enqueue = function(element, priority){}
    
    // 其他方法跟队列的一致
}

2、具体实现

PriorityQueue.prototype.enqueue = function(element, priority) {
    // 创建 QueueElement 对象
    const queueElement = new queueElement(element, priority)
        
    // 判断队列是否为空
    if (this.items.length == 0) {
        // 为空 直接将数据插入到数组中
        this.items.push(queueElement)
    } else {
        let added = false;
        for (let i = 0; i < this.items.length; i++) {
            // 数字越小，优先级越高。
            if(queueElement.priority < this.items[i].priority) {
                // 在数组的第 i 位插入数据
                this.items.splice(i, 0, queueElement);
                added = true;
                break;
            }
        }
            
        if(!added) {
            // 优先级在数组中最低直接插入
            this.items.push(queueElement)
        }
    }
}

3、 其他方法跟队列一致

三、链表结构

1、封装链表结构及方法

function LinkedList() {
    //内部类： 节点类
    function Node(data){
        this.data = data;
        this.next = null;
    }
    
    //属性
    this.head = null;
    this.length = 0;
    
    // 向列表添加一个新的项
    LinkedList.prototype.append = function(data) {}
    
    // 向列表的特定位置插入一个新的项
    LinkedList.prototype.insert = function(position, data) {}
    
    // 获取对应位置的元素
    LinkedList.prototype.get = function(position) {}
    
    // 返回元素在列表中的索引，如果列表中没有该元素则返回 -1
    LinkedList.prototype.indexOf = function(data) {}
    
    // 修改某个位置的元素
    LinkedList.prototype.update = function(position, newData) {}
    
    // 从列表的特定位置移除一项
    LinkedList.prototype.removeAt = function(position) {}
    
    // 从列表中移除一项
    LinkedList.prototype.remove = function(data) {}
    
    // 如果链表中不包含任何元素，返回 true
    LinkedList.prototype.isEmpty = function() {}
    
    // 返回链表包含的元素个数
    LinkedList.prototype.size = function() {}
    
    // toString 方法
    LinkedList.prototype.toString = function() {}

2、具体方法实现

• 向列表添加一个新的项

LinkedList.prototype.append = function(data) {
        const newNode = new Node(data);
        // 判断是否为第一个节点
        if (this.length == 0) {
            // 将头部指向第一结点
            this.head = newNode;
        } else {
             // 在链表中找到最后一个结点插入节点
             let current = this.head
             while (current.next) { // 下一个结点不为空
                 current = current.next
             }
             // 最后节点的 next 指向新的节点
             current.next = newNode;
        }
        // 更新链表长度
        this.length += 1;
    }

• 向列表的特定位置插入一个新的项
  
  
  
  
  
  
  
  

LinkedList.prototype.insert = function(position, data) {
        // 对 position 进行越界判断
        if (position < 0 || position > this.length) return false;
        
        // 创建 newNode
        const newNode = new Node(data);
        
        // 判断插入的位置是否是第一个位置
        if (position == 0) {
            newNode.next = head; 
            this.head = newNode;
        } else {
           // 找到指定位置
           let index = 0;
           let current = this.head;
           // 前一个节点
           let previous = null;
           while (index++ < position) {
               previous = current;
               current = current.next;
           }
           newNode.next = current;
           previous.next = newNode;
        }
        // 更新长度
        this.length += 1
        return true;
    }

• 获取对应位置的元素

LinkedList.prototype.get = function(position) {
        // 对 position 进行越界判断
        if (position < 0 || position >= this.length) return null;
        let current = this.head
        let index = 0;
        while (index++ < position) {
            current = current.next;
        }
        return current.data;
    }

• 返回元素在列表中的索引，如果列表中没有该元素则返回 -1

LinkedList.prototype.indexOf = function(data) {
        let current = this.head;
        let index = 0;
        while(current) {
            if (current.data === data) {
                return index;
            }
            index += 1;
            current = current.next;
        }
        return -1;
    }

• 修改某个位置的元素

LinkedList.prototype.update = function(position, newData) {
    // 对 position 进行越界判断
    if (position < 0 || position >= this.length) return false;
    let current = this.head;
    let index = 0;
    while (index++ < position) {
        current = current.next;
    }   
    current.data = newData;
    return true;

• 从列表的特定位置移除一项

LinkedList.prototype.removeAt = function(position) {
        // 对 position 进行越界判断
        if (position < 0 || position >= this.length) return null;
        let current = this.head;
        
        // 判断是否删除第一个节点
        if (position === 0) {
            this.head = this.head.next;
        } else {
            let index = 0;
            let previous = null;
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            // 前者指向后者的后者
            previous.next = current.next;
            
            // 更新长度
            this.length -= 1;
            
            return current.data;
        }

• 其他方法

// 从列表中移除一项
    LinkedList.prototype.remove = function(data) {
        // 根据 data 获取位置
        let position = this.indexOf(data);
        //根据位置信息，删除节点
        return this.removeAt(position); 
    }
    
    // 如果链表中不包含任何元素，返回 true
    LinkedList.prototype.isEmpty = function() {
        return this.length === 0;
    }
    
    // 返回链表包含的元素个数
    LinkedList.prototype.size = function() {
        return this.length;
    }
    
    // toString 方法
    LinkedList.prototype.toString = function() {
        let listString = '';
        let current = this.head;
        
        //循环获取节点
        while (current) {
            listString += current.data + " ";
            current = current.next;
        }
        return listString;
    }

四、双向链表结构

1、封装链表结构及其方法

function DoublyLinkedList() {
    // 属性
    this.head = null;
    this.tail = null;
    this.length = 0;

    //内部类
    function Node(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }

    // 向双向链表添加一个新的项
    DoublyLinkedList.prototype.append = function(data) {}

    // 向双向链表的特定位置插入一个新的项
    DoublyLinkedList.prototype.insert = function(position, data) {}

    // 获取对应位置的元素
    DoublyLinkedList.prototype.get = function() {}

    // 返回元素在列表中的索引，如果列表中没有该元素则返回 -1
    DoublyLinkedList.prototype.indexOf = function(data) {}

    // 修改某个位置的元素
    DoublyLinkedList.prototype.update = function(position, newData) {}

    // 从双向链表的特定位置移除一项
    DoublyLinkedList.prototype.removeAt = function(position) {}

    // 从双向链表移除一项
    DoublyLinkedList.prototype.remove = function(data) {}

    // 如果双向链表中不包含任何元素，返回 true
    DoublyLinkedList.prototype.isEmpty = function() {}

    // 返回双向链表包含的元素个数
    DoublyLinkedList.prototype.size = function() {}
    
    // 获取双向链表的第一个元素
    DoublyLinkedList.prototype.getHead = function() {}
    
    // 获取双向链表的最后一个元素
    DoublyLinkedList.prototype.getTail = function() {}

    // toString 方法
    DoublyLinkedList.prototype.toString = function() {}

    // 返回正向遍历的节点字符串形式
    DoublyLinkedList.prototype.forwordString = function() {}

    // 返回反向遍历的节点字符串形式
    DoublyLinkedList.prototype.backwordString = function() {}
}

2、具体方法实现

• 向双向链表添加一个新的项
  
  
  
  
  

DoublyLinkedList.prototype.append = function(data) {
        const newNode = new Node(data);

        // 判断是否添加的是第一个结点
        if (this.length === 0) {
            this.head = newNode;
        } else {
            // 找到链表的最后一个结点
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            // 最后一个结点指向下一个结点
            current.next = newNode;
            // 新的结点指向上一个结点
            newNode.prev = current;
        }
        // 更新指向最后一个结点
        this.tail = newNode;
        // 更新长度
        this.length += 1;
    }

• 向双向链表的特定位置插入一个新的项
  
  
  
  
  
  
  
  
  
  
  

DoublyLinkedList.prototype.insert = function(position, data) {
        // 越界判断
        if (position < 0 || position > this.length) return false;

        // 判断原来链表是否为空
        if (this.length == 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            // 判断 position 是否为 0
            if (position == 0) {
                this.head.prev = newNode;
                newNode.next = this.head;
                this.head = newNode;
            } else if (position == this.length) {
                newNode.prev = this.tail;
                this.tail.next = newNode;
                this.tail = newNode;
            } else {
                let current = this.head;
                let index = 0;
                while (index++ < position) {
                    current = current.next;
                }
                newNode.next = current;
                newNode.prev = current.prev;
                current.prev.next = newNode;
                current.prev = newNode;
            }
            this.length += 1;
            return true;
        }
    }

• 获取对应位置的元素

DoublyLinkedList.prototype.get = function() {
        // 越界判断
        if (position < 0 || position >= this.length) return false;
        let current = this.head;
        let index = 0;
        while (index++ < position) {
            current = current.next;
        }
        return current.data;
    }

• 返回元素在列表中的索引，如果列表中没有该元素则返回 -1

DoublyLinkedList.prototype.indexOf = function(data) {
        let current = this.head;
        let index = 0;
        while (current) {
            if (current.data == data) {
                return index;
            }
            current = current.next;
            index += 1;
        }
        return -1;
    }

• 修改某个位置的元素

DoublyLinkedList.prototype.update = function(position, newData) {
        // 越界判断
        if (position < 0 || position >= this.length) return false;
        let current = this.head;
        let index = 0;
        while (index++ < position) {
            current = current.next;
        }
        current.data = newData;
        return true;
    }

• 返回正反向遍历的节点字符串形式

// 返回正向遍历的节点字符串形式
DoublyLinkedList.prototype.forwordString = function() {
    let current = this.head;
    let resultString = "";
    while (current) {
        resultString += current.data + " ";
        current = current.next;
    }
    return resultString;
}

// 返回反向遍历的节点字符串形式
DoublyLinkedList.prototype.backwordString = function() {
    let current = this.tail;
    let resultString = "";
    while (current) {
        resultString += current.data + " ";
        current = current.prev;
    }
    return resultString;
}
// toString 方法
DoublyLinkedList.prototype.toString = function() {
    this.forwordString();
}

• 从双向链表的特定位置移除一项
  
  
  
  
  
  
  
  
  
  
  

DoublyLinkedList.prototype.removeAt = function(position) {
        // 越界判断
        if (position < 0 || position >= this.length) return null;
        let current = this.head;
        if (this.length == 1) {
            // 只存在一个结点
            this.head = null;
            this.tail = null;
        } else {
            // postion 为 0
            if (position == 0) {
                this.head.next.prev = null;
                this.head = this.head.next;
            } else if (position == this.length - 1) {
                // postion 为 this.length
                current = this.tail;
                this.tail.prev.next = null;
                this.tail = this.tail.prev;
            } else {
                // postion 为 任意值
                let index = 0;
                while (index++ < position) {
                    current = current.next;
                }
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
        }
        this.length -= 1;
        return current.data;
    }

• 其他方法

// 从列表移除一项
DoublyLinkedList.prototype.remove = function(data) {
    let postion = this.indexOf(data);
    return this.removeAt(postion);
}

// 如果链表中不包含任何元素，返回 true
DoublyLinkedList.prototype.isEmpty = function() {
    return this.length == 0;
}

// 返回链表包含的元素个数
DoublyLinkedList.prototype.size = function() {
    return this.length;
}
    
// 获取链表的第一个元素
DoublyLinkedList.prototype.getHead = function() {
    return this.head.data;
}
    
// 获取链表的最后一个元素
DoublyLinkedList.prototype.getTail = function() {
    return this.tail.data;
}

源码下载