什么是栈

栈(stack)是一种遵循后进先出(LIFO,Last In First Out)原则的有序集合，新添加或者待删除的保存在栈顶，另一端称作栈底。新添加的元素靠近栈顶，反之旧元素靠近栈底,只允许一端加入(push)数据和移除(pop)数据

image

比如我们常见的函数调用栈, HTML也可以理解为一种栈，一摞书等

1
2
3
4
5
<html>
    <body>
    <!--html结构上半部分相当于入栈，后半部分相当于出栈-->
    <body>
</html>

通过数组模拟栈

数组时间复杂度是O(n)

Stack类
1
2
3
4
5
6
class Stack {
    constructor(){
        this.items = []
    }
}

模拟实现push(element(s))添加元素到栈顶
1
2
3
push(element){
    this.items.push(element)
}
模拟实现pop()移除栈顶元素
1
2
3
4
pop(){
    this.items.pop()
}

模拟实现peek()返回栈顶元素

就是返回最后一个元素就可以了

1
2
3
4
peek(){
    return this.items[this.items.length-1]
}

模拟实现isEmpty()判断栈是否为空
1
2
3
4
isEmpty(){
    return this.items.length === 0
}

模拟实现clear()清空栈
1
2
3
4
clear(){
    this.items = []
}

实现size()返回栈里面的元素个数
1
2
3
4
size(){
    return this.items.length
}

通过对象模拟栈

将查找的时间复杂度降低到O(1),通过count记录长度

Stack类
1
2
3
4
5
6
7
class Stack {
    constructor(){
        this.count = 0
        this.items = {}
    }
}

模拟实现push(element)添加元素到栈顶
1
2
3
4
5
push(element){
    this.items[this.count] = element
    this.count++
}

实现size()返回栈里面的元素个数
1
2
3
4
size(){
    return this.count
}

模拟实现isEmpty()判断栈是否为空
1
2
3
4
isEmpty(){
    return this.count === 0
}

模拟实现pop()移除栈顶元素
1
2
3
4
5
6
7
8
9
10
pop(){
    if (this.isEmpty()){
        return undefined
    }
    this.count--
    const result = this.items[this.count]
    delete this.items[this.count]
    return result
}

模拟实现peek()返回栈顶元素

就是返回最后一个元素就可以了

1
2
3
4
peek(){
    return this.items[this.count-1]
}

模拟实现clear()清空栈
1
2
3
4
5
clear(){
    this.items = {}
    this.count = 0
}

栈可以解决什么问题？

比如，在线文本编辑器的后退，撤销功能

队列

和栈不同的是，队列数据结构遵循先进先出(FIFO(Firse In First Out)),尾部添加新元素，顶部移除元素

Queue类

同样，为了降低复杂度，通过对象来模拟数组，同时通过count记录长度，lowestCount记录要移除的首部元素

1
2
3
4
5
6
7
class Quene {
    constructor(){
        this.count = 0
        this.lowestCount = 0
        this.items = {}
    }
}

向队列添加新元素enqueue方法

1
2
3
4
5
6
7
enqueue(element){
    // this.items = {0:element,1:element}
    // 添加只能向元素末尾添加，count记录了最大长度
    this.items[this.count] = element
    this.count++
}

从队列移除元素dequeue方法

返回删除的元素

1
2
3
4
5
6
7
8
9
10
11
dequeue(){
    if (this.isEmpty()){
        return undefined
    }
    //获取到第一个元素，第一次删除lowestCount为0
    const result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++ // {0:element,1:element},需要++才行
    return result
}

查看队列头元素peek方法

1
2
3
4
5
6
7
peek(){
    if (this.isEmpty()){
        return undefined
    }
    return this.items[this.lowestCount]
}

检查是否为空isEmpty方法

1
2
3
4
isEmpty(){
    return this.count-this.lowestCount === 0
}

清空clear方法

1
2
3
4
5
6
7
clear(){
    this.count = 0
    this.items = {}
    this.lowestCount = 0
}


双端队列

是一种同时允许从前后删除和添加元素的特殊队列，双端队列同时遵循先进先出和后进先出原则，可以说是栈和队列的一种结合，其余方法已经在队列和栈中实现，这里只实现Deque类和addFront类

Deque类

1
2
3
4
5
6
7
8
class Deque {
    constructor(){
        this.count = 0
        this.lowestCount = 0
        this.items = {}
    }
}

双端队列前端添加元素addFront方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
addFront(element){
    if (this.isEmpty()){
        this.addBack() //等同于队列中的enqueue方法
    } else if (this.lowestCount > 0){
        // 表示删除过元素，第一位未知
        this.lowestCount--
        this.items[this.lo  westCount] = element
    } else {
        // 需要添加到队列最前面，遍历元素，向后移动
        for (let i = this.count;i>0;i--){
          this.items[i] = this.items[i-1]
        }
        this.count++
        this.lowestCount = 0
        this.items[0] = element
    }
}