Go实现堆栈

【译文】原文地址
本文讨论计算机科学中的堆栈数据结构:堆栈数据结构是什么、堆栈操作、基于切片实现堆栈示例。

堆栈是一种抽象数据类型

在计算机科学中，堆栈是一种抽象数据类型，它服务于根据后进先出(LIFO)原则插入和删除的一组元素。这意味着你放入堆栈的最后一个元素是你取出的第一个元素。

用一个类比来帮助理解堆栈，可以想象一堆盘子。当需要一个新的盘子，将从最顶端的那个盘子先拿出，当要加入新的盘子，将放在整堆盘子的最顶端。

栈的底层数据结构可以是数组、链表或任何其他集合。需要注意的是，链表和数组的实现和性能是不同的。例如，一个数组支持随机访问，这意味着你可以直接访问一个元素(arr[1])。同时，链表支持顺序访问，这意味着您按顺序遍历链表以获得所需的元素。

然而，无论底层数据结构如何，其功能都必须相同。

申明Stack类型

我们将栈声明为结构体，其中包元素切片和互斥量字段。

type Item interface{}

type Stack struct {
    items []Item
    mutex sync.Mutex
}

items是作为堆栈底层集合使用的元素片。互斥锁用于避免竞争条件。当两个或多个线程并发地访问相同的资源，并且至少有一个线程正在写入时，就会出现竞争条件。当多个线程读取相同的资源时，只要它们不发生变化，它们就是安全的。
Lock方法锁定互斥锁，以排除两个或多个线程可以访问并修改堆栈的情况。Unlock方法解锁互斥锁，以便在前一个线程完成后可以对栈进行写入。

堆栈操作

经典的堆栈定义包括两个基本操作:Push()和Pop()。IsEmpty、Reset、Dump和Peek()是不重要的。stack.Push(item Item)在堆栈顶部插叙新元素：

元素入栈说明

该方法调用内置函数append()，将元素插入到切片的末尾。

func (stack *Stack) Push(item Item) {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    stack.items = append(stack.items, item)
}

通过引入defer语句，我们可以确保在处理操作后堆栈总是未锁定的。但是，在性能方面，使用defer比在return语句之前解锁堆栈代价更大。

stack.Pop() Item函数从堆栈中移除顶部的元素。

元素出栈说明

首先，我们需要检查堆栈的长度。如果我们从一个空堆栈中移除一个项，该方法必须返回nil。如果堆栈非空，则将堆栈的最后一项复制到一个新变量中。

func (stack *Stack) Pop() Item {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    if len(stack.items) == 0 {
        return nil
    }

    lastItem := stack.items[len(stack.items)-1]
    stack.items = stack.items[:len(stack.items)-1]

    return lastItem
}

stack.IsEmpty() bool函数检查堆栈是否为空。该方法执行len()内置函数，该函数返回slice中元素的数量。如果数值为0 -堆栈为空，返回值为true。如果数字大于0 -堆栈不为空，返回值为false。

func (stack *Stack) IsEmpty() bool {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    return len(stack.items) == 0
}

注意：这里加锁是因为len函数是不安全的。

stack.Reset()函数删除stack中所有元素，该方法将一个零值(nil)赋给切片。

func (stack *Stack) Reset() {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    stack.items = nil
}

stack.Dump() []Item函数返回栈中所有元素，该方法生成并返回原始片的副本。建议返回一个副本，以避免修改原始片。

func (stack *Stack) Dump() []Item {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    var copiedStack = make([]Item, len(stack.items))
    copy(copiedStack, stack.items)

    return copiedStack
}

stack.Peek() Item方法返回栈顶元素，Peek()方法与Pop()方法相似，不同之处在于Peek()不会删除一个元素。

func (stack *Stack) Peek() Item {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    if len(stack.items) == 0 {
        return nil
    }

    return stack.items[len(stack.items)-1]
}

main函数示例：

func main() {
    var stack Stack

    fmt.Println("Stack:", stack.Dump())

    stack.Push(1)
    stack.Push(6)
    stack.Push("one")
    stack.Push(10)
    stack.Push(10.01)
    stack.Push("two")

    fmt.Println("Stack:", stack.Dump())

    fmt.Println("Last item:", stack.Peek())

    fmt.Println("Stack is empty:", stack.IsEmpty())

    fmt.Println("Last removed item:", stack.Pop())

    fmt.Println("Stack:", stack.Dump())

    stack.Reset()

    fmt.Println("Stack is empty:", stack.IsEmpty())

    fmt.Println("Last item:", stack.Peek())
}

output:

Stack: []                                                                                                                      
Stack: [1 6 one 10 10.01 two]                                                                                                  
Last item: two                                                                                                                 
Stack is empty: false                                                                                                          
Last removed item: two                                                                                                         
Stack: [1 6 one 10 10.01]                                                                                                      
Stack is empty: true                                                                                                           
Last item: <nil>