golang定义栈的数据结构

发表于 更新于
东风夜放花千树，更吹落，星如雨。

简述

栈是一种操作受限制的线性表，将允许进行插入、删除的一端称为栈顶，另一端称为栈底。看到这里你可能会觉得有点绕，其实数据结构很多的定义都很抽象，这是很正常的，下面我将类比一个生活中的常见实例帮助大家理解。

我们在日常生活中洗盘子的时候，摞起来的盘子就是一个典型的栈结构。不管取还是放，总是要放在盘子堆的最上面操作。如果你想从一堆盘子的中间强行取一个盘子，那就有可能酿成大祸。

定义

我们在日常生活中，一摞盘子肯定有很多个而且是连续的，所以我们首先需要一个切片，并且我们日常生活中的盘子是不能无限的摞的，这点在计算机里也是同样的，计算机里也会有 Stack Overflow 的问题。 所以我们还需要一个容量的限制元素。 并且我们还需要频繁的对栈顶元素进行操作，所以我们还需要一个标记位 top 来标记栈顶元素的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

type Stack struct {
    // 用来装元素的切片
    container []int
    // 栈顶标记位
    top int
    // 容量限制
    size int
}

// 初始化时，要传入容量限制
func NewStack(size int) *Stack {
    return &Stack{
        container: make([]int,size),
        // 栈顶指针初始可以指向-1，也可以指向0，想一想为什么。
        top:       0,
        size:      size,
    }
}

初始化时要注意，我们这里返回的是一个 Stack 的指针，引用传递在系统中的开销比较小

栈的基本操作

对于一个栈来说，其基本操作分为以下四种。

  • Push(e E) , 将一个数据类型为 E 的元素 e 放到栈顶。
  • Pop() , 将栈顶元素取出。
  • IsFul() , 栈是否满了。
  • IsEmpty() , 栈是否空了。
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
65
66
67
68
69
70
71
72
package main

import "fmt"

type Stack struct {
    // 用来装元素的切片
    container []int
    // 栈顶标记位
    top int
    // 容量限制
    size int
}

// 初始化时，要传入容量限制
func NewStack(size int) Stack {
    return Stack{
        container: make([]int, size),
        top:       0,
        size:      size,
    }
}

func (s *Stack) Push(e int) bool {
    if s.IsFull() {
        return false
    }
    // 把盘子摞上去
    s.container[s.top] = e
    // 下一个能摞盘子的位置
    s.top++
    return true
}

func (s *Stack) Pop() (flag bool, ret int) {
    // 如果栈空了，你就无法拿到新盘子，所以flag此时为false
    if s.IsEmpty() {
        return false, ret
    }
    // 取出盘子
    ret = s.container[s.top-1]
    // 下一个能取盘子的位置
    s.top--
    return true, ret
}

func (s *Stack) IsEmpty() bool {
    if s.top == 0 {
        return true
    }
    return false
}

func (s *Stack) IsFull() bool {
    if s.top == s.size {
        return true
    }
    return false
}

func main() {
    stack := NewStack(3)
    // 先测试栈为空的时候能否Pop
    fmt.Println(stack.Pop())
    // 测试Push是否正常
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    // 如果栈为正常的，这里Pop打印顺序应该是3,2,1
    fmt.Println(stack.Pop())
    fmt.Println(stack.Pop())
    fmt.Println(stack.Pop())
}

栈的常见应用

浏览器中的前进后退

假设你现在是 N 年前的 Chrome 浏览器工程师， 你现在很苦恼，有的网页在打开下一个页面后就回不去上一级了，你现在急迫的想要一个后退的功能，请问要怎么样实现呢？

仔细分析之后不难发现，所谓的后退，撤销等操作，其实就是一个栈的 Pop 操作，我们每次点击的网址, 或者进行的操作，都是被程序 Push 到了一个栈中，所以一旦我们点击撤销或后退时，总是可以返回我们最近一次的操作。这就是栈的最广泛的应用。

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
65
66
package main

import "fmt"

type Stack struct {
    // 用来装元素的切片
    container []string
    // 栈顶标记位
    top int
    // 容量限制
    size int
}

// 初始化时，要传入容量限制
func NewStack(size int) Stack {
    return Stack{
        container: make([]string, size),
        top:       0,
        size:      size,
    }
}

func (s *Stack) Push(e string) bool {
    if s.IsFull() {
        return false
    }
    s.container[s.top] = e
    s.top++
    return true
}

func (s *Stack) Pop() (flag bool, ret string) {
    // 如果栈是空的，那么就不能继续 Pop 了
    if s.IsEmpty() {
        return false, ret
    }
    ret = s.container[s.top-1]
    s.top--
    return true, ret
}

func (s *Stack) IsEmpty() bool {
    if s.top == 0 {
        return true
    }
    return false
}

func (s *Stack) IsFull() bool {
    if s.top == s.size {
        return true
    }
    return false
}

func main() {
    back := NewStack(3)
    // 模拟每次点击网页时，浏览器会自push你的网址到栈中
    back.Push("www.baidu.com")
    back.Push("www.bing.com")
    back.Push("www.goole.com")
    // 每次点击后退时，就相当于是从栈中Pop了一个网址
    fmt.Println(back.Pop())
    fmt.Println(back.Pop())
    fmt.Println(back.Pop())
}

括号匹配

在现代的 IDE 中，我们的编辑器环境是十分智能的,我少打了一个括号，IDE 就自动给我画了一条红线。是不是非常的神奇。其实这个功能也是用栈实现的。下面来说一下思路：
若遇到左括号入栈，遇到右括号时将栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；如果遍历之后 stack 不为空，那么说明有多余的左括号。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package main

import "fmt"

type Stack struct {
    // 用来装元素的切片
    container []byte
    // 栈顶标记位
    top int
    // 容量限制
    size int
}

// 初始化时，要传入容量限制
func NewStack(size int) Stack {
    return Stack{
        container: make([]byte,size),
        top:       0,
        size:      size,
    }
}

func (s *Stack) Push (e byte) bool {
    if s.IsFull() {
        return false
    }
    s.container[s.top] = e
    s.top++
    return true
}


func (s *Stack) Pop () (flag bool,ret byte) {
    // 如果栈是空的，那么就不能继续 Pop 了
    if s.IsEmpty() {
        return false,ret
    }
    ret = s.container[s.top-1]
    s.top--
    return true,ret
}


func (s *Stack) IsEmpty () bool {
    if s.top == 0 {
        return true
    }
    return false
}


func (s *Stack) IsFull () bool {
    if s.top == s.size {
        return true
    }
    return false
}

func IsValid(s string) bool {
    stack := NewStack(100)
    // 遍历括号字符串
    for _,v := range s {
        if v == '(' {
            // 由于golang中的字符串默认是unicode编码，所以我们要做一个强制类型转换
            stack.Push(byte(v))
        }
        if v == ')' {
            // 如果flag不为true，说明栈已经到底了，可以直返回false
            if flag,top := stack.Pop(); flag == true &&top == '(' {
                continue
            } else {
                return false
            }
        }
    }
    // 字符串遍历完后如果栈也空了，说明括号匹配
    if stack.IsEmpty() {
        return true
    }
    // 如果栈不空，说明栈里还有多余的左括号
    return false
}

func main() {
    test1 := "()()())"
    test2 := "((()"
    test3 := "()()()()"
    fmt.Println(IsValid(test1))
    fmt.Println(IsValid(test2))
    fmt.Println(IsValid(test3))
}