简单手写栈、队列、链表实现

简单手写栈、队列、链表实现

栈

//栈LIFO 先进后出
// push 添加元素
// pop 移除栈顶的元素
// peek 获取栈顶的元素
// isEmpty 是否为空
// clean 清空栈
// size 返回栈的长度
let Stack = (function () {
    const _items = new WeakMap()
    return class Stack {
        constructor() {
            _items.set(this, [])
        }
        push(element) {
            _items.get(this).push(element)
        }
        pop() {
            return _items.get(this).pop()
        }
        peek() {
            return _items.get(this)[this.size() - 1]
        }
        isEmpty() {
            return _items.get(this).length === 0
        }
        clean() {
            _items.set(this, [])
        }
        size() {
            return _items.get(this).length
        }
        toString() {
            return _items.get(this).toString()
        }
    }
})()
var a = new Stack()
a.push(1)
a.push(2)
a.push(3)
a.push(4)
a.pop()
console.log(a.isEmpty())
console.log(a.peek())
console.log(a.size())
console.log(a.toString())
/** 进制转换就可以用到栈
 *  比如转二进制，以10为例，转成二进制就是1010
 *  转换过程：rem为余数
 *  10/2 = 5 , rem = 0
 *  5/2 = 2, rem = 1
 *  2/2 = 1, rem = 0
 *  1/2 = 0, rem = 1 
 *  从上到下，就是 1010，就是10转二进制的结果
 *  由此可见，符合栈的先进后出
 */
function divide(num, base = 2) {
    var remStack = new Stack();
    var rem,
        res = "",
        digits = "0123456789abcdef"; // 16进制大于9的时候转化成字母
    while (num > 0) {
        rem = num % base;
        remStack.push(rem);
        num = parseInt(num / base);
    }
    while (!remStack.isEmpty()) {
        res += digits[remStack.pop()]
    }
    return res
}
console.log(divide(1000, 16));

队列

// 队列Queue FIFO 先进先出
// enqueue 进入队列
// dequeue 退出队列
// front 队列第一位
// isEmpty 是否为空
// size 队列长度
// toString 输出队列
let Queue = (function () {
    const _items = new WeakMap()
    return class Queue {
        constructor() {
            _items.set(this, [])
        }
        enqueue(element) {
            _items.get(this).push(element)
        }
        dequeue() {
            return _items.get(this).shift()
        }
        front() {
            return _items.get(this)[0]
        }
        isEmpty() {
            return this.size === 0
        }
        size() {
            return _items.get(this).length
        }
        toString() {
            return _items.get(this).toString()
        }
    }
})()
var a = new Queue()
a.enqueue(1)
a.enqueue(2)
a.enqueue(3)
a.enqueue(4)
a.enqueue(5)
a.dequeue()
console.log(a.front())
console.log(a.isEmpty())
console.log(a.size())
console.log(a.toString())
// 优先队列
let Queue = (function () {
    const _items = new WeakMap()
    // 优先队列元素
    class QueueElement {
        constructor(element, priority) {
            this.element = element;
            this.priority = priority;
        }
    }
    return class Queue {
        constructor() {
            _items.set(this, [])
        }
        enqueue(element, priority) {
            let queueElement = new QueueElement(element, priority)
            let added = false
            for (var i = 0; i < this.size(); i++) {
                if (queueElement.priority < _items.get(this)[i].priority) {
                    _items.get(this).splice(i, 0, queueElement);
                    added = true
                    break
                }
            }
            if (!added) {
                _items.get(this).push(queueElement)
            }
        }
        dequeue() {
            return _items.get(this).shift()
        }
        front() {
            return _items.get(this)[0]
        }
        isEmpty() {
            return this.size === 0
        }
        size() {
            return _items.get(this).length
        }
        toString() {
            return _items.get(this)
        }
    }
})()
var a = new Queue()
a.enqueue("张三", 1)
a.enqueue("李四", 2)
a.enqueue("赵六", 3)
a.enqueue("熊七", 4)
a.enqueue("赵八", 2)
// a.dequeue()
console.log(a.front())
console.log(a.isEmpty())
console.log(a.size())
console.dir(a.toString())

链表

单向链表

// 链表
class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}
class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    getNode(index) {
        if (index < 0 || index >= this.size) {
            throw new Error("out of range")
        }
        let current = this.head
        for (var i = 0; i < index; i++) {
            current = current.next
        }
        return current
    }
    append(element) {
        let node = new Node(element)
        if (this.head === null) {
            this.head = node
        } else {
            let current = this.getNode(this.size - 1)
            current.next = node;
        }
        this.size++
    }
    appendAt(element, position) {
        let node = new Node(element)
        if (position === 0) {
            node.next = this.head
            this.head = node
        } else {
            let pre = this.getNode(position - 1);
            node.next = pre.next
            pre.next = node;
        }
        this.size++
    }
    indexOf(element) {
        let current = this.head
        for (var i = 0; i < index; i++) {
            if (current.element === element) {
                return i
            }
            current = current.next
        }
        return -1
    }
    removeAt(position) {
        let current = this.head
        if (position === 0) {
            this.head = current.head
        } else {
            let pre = this.getNode(position - 1)
            current = pre.next
            pre.next = current.next
        }
        this.size--
    }
}
let ll = new LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.appendAt(4, 1)
ll.removeAt(2)
console.dir(ll, {
    depth: 1000
})