一个前端小青年的学习笔记

# 数据结构

# 栈

栈是一种遵循先进后出的原则的集合，新添加的或者待删除的元素在栈的末尾称之为栈顶，另一端称之为栈底。

好比一摞书，新放上去的书在上面，就是栈顶。之前放的书压在下面，称之为栈底。如果要拿走一本书的话就必须将这本书上面的所有书都拿走才能拿走这本书

栈中需要声明的方法：

1、push(elementh) 添加元素到栈顶

2、pop() 移除栈顶元素并返回被移除的元素

3、peek() 返回栈顶元素，不会对栈做任何修改

4、isEmpty() 判断栈是否为空

5、clear() 清除栈中的所有元素

6、size() 返回栈的元素个数

代码实现

class Stack {

    constructor() {
        this.count = 0;
        this.items = {};
    }

    // 入栈
    push(element) {
         this.items[count] = element;
         this.count++
    }

    // 出栈
    pop() {
        if(this.isEmpty()){
            return undefined;
        }
        const result = this.items[this.count];
        delete this.items[this.count];
        this.count--;
        return result;
    }

    // 末位
    get peek() {
        return this.isEmpty() ? undefined : this.items[this.count]
    }

    // 是否为空栈
    get isEmpty() {
        return this.count === 0
    }

    // 尺寸
    get size() {
        return this.count;
    }

    // 清空栈
    clear() {
        this.count = 0;
        this.items = {}
    }

    // 打印栈数据
    toString() {
        if(this.isEmpty()) {
            return ''
        }
        let objString = ''
        for(let i=0; i<this.count; i++) {
            objString = objString + this.items[i] 
        }
        return objString
    }
}

module.exports=Stack

# 队列

队列与栈相反，队列是一个遵循先进先出原则的有序集合，新添加的元素在队尾，待删除的元素在队头部。

好比日常生活中的排队，先到的人站在队伍前面，后来的人在队伍后面。队伍前面的人先走。

队列中需要实现的方法

1、enqueue(element) 向队列中添加元素

2、dequeue() 移除队列中第一项，并返回该元素

3、peek() 返回队列中第一项元素

4、isEmpty() 判断队列是否为空

5、size() 返回队列长度

代码实现

class Queue {
	constructor(items) {
        this.items = items || []
    }

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

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

    front(){
        return this.items[0]
    }

    clear(){
        this.items = []
    }

    get size(){
        return this.items.length
    }

    get isEmpty(){
        return !this.items.length
    }

    print() {
        console.log(this.items.toString())
    }
}

module.exports = Queue

# 双端队列

双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列

const Queue = require('./Queue');

class Deque extends Queue {
    constructor() {
        super()
    }

    addFront(element) {
        if(this.isEmpty()){
            this.items[this.count] = element;
            this.count++;
        }else if(this.lowestCount !== 0) {
            this.lowestCount--;
            this.items[this.lowestCount] = element
        }else {
            for(let i = this.count; i>0; i--){
                this.items[i] = this.items[i-1]
            }
            this.count++;
            this.items[0] = element;
        }
    }
}

module.exports = Deque;

# 优先队列

优先队列也是队列，但与之不同的是队伍中存在优先级，比如车站买票的军人优先。队伍排队的时候军人可以直接去队伍最前面优先买票。

实现优先队列的方法：在元素插入队列的时候需要给定该元素的优先级。遍历当前队列找到第一个优先级低于待插入的元素下标，然后将待插入元素插入到该元素前面即可。

代码实现(优先队列继承普通队列，普通队列的实现方式见上文)

const Queue = require('./Queue');

class PriorityQueue extends Queue{

    constructor() {
        super()
    }

    enqueue(element, priority){
        const queueElement = { element, priority }
        if (this.isEmpty) {
            this.items[this.count] = queueElement;
            this.count++
        } else {
            let prevIndex = this.lowestCount;
            for(let i=this.lowestCount; i<this.count;i++){
                if(priority > this.items[i].priority){
                    prevIndex = i;
                    break;
                }
            }
            for(let j = this.count; j>prevIndex; j--) {
                this.items[j] = this.items[j-1]
            }
            this.items[prevIndex] = queueElement
        }
    }
}

module.exports = PriorityQueue

# 链表

链表和数组一样都是存储一组数据的，链表相对于数组的区别在于链表中的元素在内存中并不是连续存储的。链表中的每一个元素除了存储它本身之外还存储着它下一个元素的地址。

链表这种数据结构相对于数组的优点在于当链表需要插入和移除元素的时候不用像数组那样改变其他元素的位置。数组中的元素都是存储在一块联系的内存，当插入和移除元素的时候会影响到这个元素后面所有的元素。

当然链表也存在缺点。在数组中随时可以通过下标的形式访问一个元素比如 arr[1] 而链表无法做到，在链表中查找一个元素的时候必须从链表的第一个元素开始向后遍历查找到该元素才行

代码实现

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

class LinkedList {
	constructor() {
		this.head = null;
		this.length = 0;
	}

	append(element) {
		const node = new Node(element);
		if (this.head === null) {
			this.head = node
		} else {
			let current = this.head;
			while (current.next) {
				current = current.next;
			}
			current.next = node
		}
		this.length++
	}

	insert(position, element) {
		const node = new Node(element);
		if (position > -1 && position <= this.length) {
			if (position === 0) {
				node.next = this.head;
				this.head = node;
			} else {
				let current = this.head;
				let currentIndex = 0;
				while (currentIndex < position - 1) {
					currentIndex++;
					current = current.next;
				}
				let currentNext = current.next;
				node.next = currentNext;
				current.next = node
			}
			this.length++
			return true;
		} else {
			return false
		}
	}

	removeAt(position) {
		let previous = this.head;
		let currentIndex = 0;
		let current = previous.next;
		if (position > -1 && position < this.length) {
			if (position === 0) {
				this.head = this.head.next
			} else {
				while (currentIndex < position) {
					currentIndex++;
					previous = previous.next;
					current = current.next;
				}
				previous.next = current.next;
			}
			this.length--;
			return current.element
		} else {
			return null
		}
	}

	findIndex(element) {
		let current = this.head;
		let currentIndex = 0;
		while (current) {
			if (current.element === element) {
				return currentIndex
			} else {
				current = current.next;
				currentIndex++;
			}
		}
		return -1;
	}

	remove(element) {
		const index = this.findIndex(element)
		this.removeAt(index)
	}

	isEmpty() {
		return !this.length;
	}

	size() {
		return this.length;
	}

	toString() {
		let current = this.head;
		let result = ''
		while (current) {
			result += `${current.element} `;
			current = current.next
		}
		return result
	}
}

module.exports = LinkedList;

# 双向链表

双向链表和普通链表的区别在于双向链表每个节点不仅有个标识指向其下一个元素还有一个标识将指向其前一个元素

const { Node, LinkedList } = require('./LinkedList')
class DocbleNode extends Node {
    constructor(element) {
        super(element);
        this.prev = null
    }
}

class DoubleLinkedList extends LinkedList {
    constructor() {
        super()
        this.tail = null;
    }

    append(element) {
        const node = new DocbleNode(element);
        if(!this.length) {
            this.head = node;
        }else if(this.length === 1){
            this.head.next = node;
            node.prev = this.head;
            this.tail = node;
        }else {
            const prev = this.tail;
            prev.next = node;
            node.prev = prev;
            this.tail = node;
        }
        this.length++;
    }

    insert(position, element) {
        if(position >=0 && position<=this.length) {
            const node = new DocbleNode(element)
            if(position === 0){
                const next = this.head;
                next.prev = node;
                node.next = next;
                this.head = node
            }else if(position === this.length) {
                const prev = this.tail;
                prev.next = node;
                node.prev = prev;
                this.tail = node
            }else {
                let current = this.head;
                let currentIndex = 0;
                while(currentIndex < position) {
                    current = current.next;
                    currentIndex++;
                }
                const prev = current.prev;
                prev.next = node;
                node.prev = prev;
                node.next = current;
                current.prev = node
            }
            this.length++;
            return true;
        }else {
            return false;
        }
    }

    removeAt(position) {
        if(position >= 0 && position < this.length){
            let current = this.head;
            let currentIndex = 0;
            if(position === 0) {
                this.head = this.head.next;
                this.head.prev = null;
                if(this.length === 1){
                    this.tail = null;
                }
            }else if(position === this.length-1) {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }else {
                while(currentIndex < position){
                    current = current.next;
                    currentIndex++
                }
                current.prev.next = current.next;
                current.next.prev = current.prev
            }
            this.length--;
            return current.element;
        }else {
            return null;
        }
    }
}

module.exports = DoubleLinkedList;

# 循环链表

循环和普通链表的区别在于循环链表的最后一个元素的next不再指向null而是指向这个链表头部的元素即haed

const { Node, LinkedList} = require('./LinkedList')

class CircleLinkedList extends LinkedList {
    constructor() {
        super()
    }

    append(element){
        const node = new Node(element);
        if(!this.length){
            node.next = node;
            this.head = node;
        }else {
            let current = this.head;
            while(current.next !== this.head) {
                current = current.next;
            }
            current.next = node;
            node.next = this.head;
        }
        this.length++;
    }

    insert(position, element){
        const node = new Node(element);
        if(position >= 0 && position <= this.length) {
            if(position !== 0 && position !== this.length){
                let current = this.head;
                let currentindex = 0;
                while(currentindex < position-1) {
                    current = current.next;
                    currentindex++;
                }
                node.next = current.next;
                current.next = node;
            }else {
                let currentTail = this.head;
                while(currentTail.next !== this.head) {
                    currentTail = currentTail.next
                }
                currentTail.next = node;
                node.next = this.head;
                if(position === 0){
                    this.head = node;
                }
            }
        }else {
            return false;
        }
    }

    removeAt(position){
        let current = this.head
        if(position >= 0 && position < this.length){
            if(position === 0) {
                let currentTail = this.head;
                while(currentTail.next !== this.head) {
                    currentTail = currentTail.next
                }
                this.head = this.head.next;
                this.currentTail = this.head;
            }else {
                let currentIndex = 0;
                while(currentIndex < position-1) {
                    current = current.next;
                    currentIndex++;
                }
                current.next = current.next.next;
            }
            this.length --;
            return current;
        }else {
            return null;
        }
    }

	toString() {
		let current = this.head.next;
		let result = `${this.head.element} `
		while (current != this.head) {
			result += `${current.element} `;
			current = current.next
		}
		return result
	}
}

module.exports = CircleLinkedList;

← 算法 →