栈

如何实现一个栈？

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作 顺序栈，用链表实现的栈，我们叫作 链式栈。

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

type ArrayStack struct {
    //数据
    data []interface{}
    //栈顶指针
    top int
}

func NewArrayStack() *ArrayStack {
    return &ArrayStack{
        data: make([]interface{}, 0, 32),
        top:  -1,
    }
}

func (this *ArrayStack) IsEmpty() bool {
    if this.top < 0 {
        return true
    }
    return false
}

func (this *ArrayStack) Push(v interface{}) {
    if this.top < 0 {
        this.top = 0
    } else {
        this.top++
    }

    if this.top > len(this.data)-1 {
        this.data = append(this.data, v)
    } else {
        this.data[this.top] = v
    }
}

func (this *ArrayStack) Pop() interface{} {
    if this.IsEmpty() {
        return nil
    }
    v := this.data[this.top]
    this.top--
    return v
}

func (this *ArrayStack) Top() interface{} {
    if this.IsEmpty() {
        return nil
    }
    return this.data[this.top]
}

func (this *ArrayStack) Flush() {
    this.top = -1
}

func (this *ArrayStack) Print() {
    if this.IsEmpty() {
        fmt.Println("empty statck")
    } else {
        for i := this.top; i >= 0; i-- {
            fmt.Println(this.data[i])
        }
    }
}

空间复杂度： 存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

• 这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

如何实现浏览器的前进和后退功能？

当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。但是，如果你后退到页面 b 后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。

我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

比如你顺序查看了 a，b，c 三个页面，我们就依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：

[ ]          [ ]
[c]<top      [ ]
[b]          [ ]
[a]          [ ]
 X            Y

当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，我们就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。这个时候，两个栈的数据就是这个样子：

[ ]          [ ]
[ ]          [ ]
[ ]          [b]
[a]<top      [c]
 X            Y

这个时候你又想看页面 b，于是你又点击前进按钮回到 b 页面，我们就把 b 再从栈 Y 中出栈，放入栈 X 中。此时两个栈的数据是这个样子：

[ ]          [ ]
[ ]          [ ]
[b]<top      [ ]
[a]          [c]
 X            Y

这个时候，你通过页面 b 又跳转到新的页面 d 了，页面 c 就无法再通过前进、后退按钮重复查看了，所以需要清空栈 Y。此时两个栈的数据这个样子：

[ ]          [ ]
[d]          [ ]
[b]          [ ]
[a]<top      [ ]
 X            Y

上一篇 « 链表 下一篇 » 队列