常见数据结构

栈

栈是一个线性结构，特点是只能在某一端添加或删除数据，遵循先进后出的原则。

class Stack {
    constructor() {
        this.stack = []
    }

    push(item) {
        this.stack.push(item)
    }

    pop() {
        return this.stack.pop()
    }

    peek() {
        return this.stack[this.getCount() - 1]
    }

    getCount() {
        return this.stack.length
    }

    isEmpty() {
        return this.getCount() === 0
    }
}

队列

队列是一个线性结构，特点实在某一端添加数据在另一端删除数据，遵循先进先出的原则。

• 单链队列

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

    push(item) {
        this.queue.push(item)
    }

    shift() {
        this.queue.shift()
    }

    getHeader() {
        return this.queue[0]
    }

    getLength() {
        return this.queue.length
    }

    isEmpty() {
        return this.getLength() === 0
    }
}

因为单链队列再出列的时候需要 O[n] 的时间复杂度，所以引入了循环队列，循环队列的出队操作平均是 O[1] 的时间复杂度。