Published on

知识点

Authors

在本次实验中，我们将从栈的定义开始，先实现一个栈的数据结构，然后再实现栈的基本操作。最后通过实现两个栈的常见的应用场景。通过这种由浅入深的实验方式，加深大家对于栈这个数据结构的理解。

知识点

  • 栈的定义
  • 栈的基本操作
  • 栈的实现
  • 栈的应用

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

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

我们首先还是在当前目录下去新建一个名叫 stack.go 的文件。

img

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

分析到这里，栈的数据结构已经呼之欲出了。我们就直接写出栈的数据结构和他的构造方法。

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 的指针，还记得我们上节学到过引用传递在系统中的开销比较小吗？

到这里，我们对于 Golang 栈的定义以及初始化操作以及完成了，下一小节中我们将学习栈的基本操作。

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

  • Push(e E) , 将一个数据类型为 E 的元素 e 放到栈顶。
  • Pop() , 将栈顶元素取出。
  • IsFul() , 栈是否满了。
  • IsEmpty() , 栈是否空了。

这里我们还是在 stack.go 中继续实验。实现其上述四个基本功能，并且在主函数中进行测试。代码如下：

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())
}

我们输入 go run stack.go 查看执行结果。

img

各位同学在书写 Golang 代码时如果不知道 Golang 的代码风格规范，可以在写完代码后执行 go fmt stack.go 编译器会自动帮我们整理代码风格。

现在，我们已经实现了栈的基本操作，接下来我们将改造一下我们的栈，来解决实际的问题。

在这一小节中，我们将通过解决两个具体的实际问题来巩固栈的知识。

浏览器中的前进后退

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

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

我们新建一个名叫 browser.go 的文件。然后将我们在 stack.go 中实现的代码除主函数外全都拷贝进去， 并且因为浏览器的网址是字符串类型的，所以我们需要把除了 top 和 size 以外的 int 改为 string 。

代码如下：

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())
}

执行结果:

img

下面关于这道题留下一个思考问题，我们的浏览器不光有后退操作，还是有前进操作的，其实前进也是一个栈，请尝试实现出完善的前进，后退功能。

括号匹配

在现代的 IDE 中，我们的编辑器环境是十分智能的，比如下图:

img

我少打了一个括号，IDE 就自动给我画了一条红线。是不是非常的神奇。其实这个功能也是用栈实现的。下面来说一下思路：

若遇到左括号入栈，遇到右括号时将栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；如果遍历之后 stack 不为空，那么说明有多余的左括号。上图中就是这种情况。

我们新建一个名叫 valid.go 的文件，并且将 stack.go 中的代码拷贝进去。把除了 top 和 size 以外的 int 改为 byte 。

然后我们通过实现 isValid 函数去完成括号匹配的功能。完整代码与测试结果如下:

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))
}

测试结果:

img

现在我们就已经完成了小括号的匹配功能，下面请大家思考一下如果匹配小括号，中括号，大括号混合的字符串，那么我们的 IsValid 函数需要做什么样的修改呢？

在本节中，我们从栈的数据结构开始分析，学习了栈的数据结构，栈的四个基本操作，以及栈的两个常见应用和两个思考题。大家在用栈的时候只要牢记一个定义，栈是后进先出的一种线性结构。如果你的问题是符合后进先出的功能，那么用栈进行实现就肯定没错了。

Discuss on Twitter • View on GitHub