、夕月的博客

栈的顺序存储

2020/12/27

# Heading

# 顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元（数组）存放元素，同时设置一个指针（Top）指示当前栈顶元素的位置。

点击查看代码 
/**
 * 顺序栈
 */
class SqStack {
    constructor() {
        this.data = [];
        this.top = -1;
    }

    InitStack(...args) {
        this.top = -1
        args.forEach(item => this.Push(item))
    }
    StackEmpty() {
        return this.top === -1
    }
    Push(item) {
        this.data[++this.top] = item
    }
    Pop() {
        return this.StackEmpty() ? undefined : this.data[this.top--]
    }
    GetTop() {
        return this.StackEmpty() ? undefined : this.data[this.top]
    }
}

export {
    SqStack,
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置的共享空间的两端，两个栈顶向共享空间的中间延伸。

  • Top1 == -1 时，1号栈空，Top2 == MaxSize 时，2号栈空；
  • 两个栈顶指针相邻（Top2 - Top1 = 1）时，栈满；
  • 当1号栈进栈时Top1先加1再赋值，2号栈进栈时Top2先减一再赋值，出栈相反。

栈的链式存储