Go中的并发安全堆栈实现

Question

由于Go没有提供大量的集合结构，所以我自己实现了堆栈，构建了一些浮动在其中的示例代码。然后，我尝试将其进一步扩展如下：

• 为不同的栈实现创建一个“堆栈”接口。
• 生成一个安全的实现，以供使用互斥的并发goroutines使用。

我最近才了解到互斥是如何工作的，所以我想确定我使用的是正确的。ConcurrentStack结构只是一个带有读/写互斥体的Stack的包装器。

• 我正确地使用了sync.RWMutex吗？
• 无视这样的事实，我将几乎没有控制的顺序，并发goroutines将元素推到堆栈，这总是安全的工作吗？

代码：

package structures

import (
    "sync"
)

// Stacker is an interface describing the behaviour of a FILO (first in, last out) stack. It allows concurrency-safe
// stacks to be used in the same places as regular stacks, if performance or concurrency safety are specific
// requirements.
type Stacker interface {
    Len() int          //Return the number of elements in the stack.
    Push(interface{})  //Push an object of unknown type onto the stack.
    Pop() interface{}  //Remove an object from the top of the stack and return it.
    Peek() interface{} //Return an object from the top of the stack without removing it.
}

// Stack is an implementation of a FILO stack structure using a linked list. The reason behind using a linked list
// rather than a dynamic array is because we guarantee any operation on the stack can be completed in O(1) time,
// disregarding overhead. While compiler optimisation might mean dynamic arrays are better in some circumstances, the
// linked list gives us a more general guarantee.
type Stack struct {
    topPtr *stackElement
    size   int
}

// stackElement holds one element from a Stack and is equivalent to a node in a linked list.
type stackElement struct {
    value interface{}
    next  *stackElement
}

// Len returns the number of elements in the stack.
func (s Stack) Len() int {
    return s.size
}

// Push pushes a new element on to the stack.
func (s *Stack) Push(v interface{}) {
    s.topPtr = &stackElement{
        value: v,
        next:  s.topPtr,
    }
    s.size++
}

// Pop removes the top element from the stack and returns it. If the stack is empty then this function will return nil.
func (s *Stack) Pop() interface{} {
    if s.size > 0 {
        retVal := s.topPtr.value
        s.topPtr = s.topPtr.next
        s.size--
        return retVal
    }
    return nil
}

// Peek returns a copy of the top element on the stack (the one which will be popped first) without removing it from the
// underlying stack. If the stack is empty, it will return nil.
func (s Stack) Peek() interface{} {
    if s.size > 0 {
        return s.topPtr.value
    }
    return nil
}

// ConcurrentStack is a concurrency-safe implementation of the Stacker interface. It has a slight performance hit when
// compared to the other implementation (Stack), but the trade-off is that ConcurrentStack can be safely used between
// different goroutines, while the object is kept synchronised.
type ConcurrentStack struct {
    internalStack Stack
    lock          sync.RWMutex
}

// Len returns the number of elements in the stack. Unlike a regular Stack, this function operates on the pointer to cs
// so that the mutex is not duplicated.
func (cs *ConcurrentStack) Len() int {
    cs.lock.RLock()
    defer cs.lock.RUnlock()
    return cs.internalStack.size
}

// Push pushes a new element onto the stack.
func (cs *ConcurrentStack) Push(v interface{}) {
    cs.lock.Lock()
    defer cs.lock.Unlock()
    cs.internalStack.Push(v)

}

// Pop removes an element from the top of the stack and returns it. If the stack is empty, it will return nil.
func (cs *ConcurrentStack) Pop() interface{} {
    cs.lock.Lock()
    defer cs.lock.Unlock()
    return cs.internalStack.Pop()
}

// Peek returns a copy of the top element on the stack (the one which will be popped first) without removing it from the
// underlying stack. If the stack is empty, it will return nil.
func (cs *ConcurrentStack) Peek() interface{} {
    cs.lock.RLock()
    defer cs.lock.RUnlock()
    return cs.internalStack.Peek()
}

Answer 1

• 你的代码基本上没问题。以下是吹毛求疵的评论。
• 我同意Elias的观点，默认的实现应该是线程安全的。
• 我建议您的Pop函数返回(interface{}, error)，而不是返回零，如果您试图弹出一个空堆栈，则返回一个错误。它允许您将零存储在堆栈中(您可能希望禁止它，但随后显式地这样做)，并迫使调用方考虑这种可能性。
• stackElement不必要地冗长。只是个节点。叫它node。
• 您的Stack文档提到了实现，这不是很好的实践。假设所有操作都在O(1)中，这是主要的，也是唯一重要的部分。

Answer 2

在特德的回答上添加：

• 您可以将基本实现命名为UnsafeStack (或MonothreadStack)
• 在Pop上，您可以返回一个错误(如果堆栈为空)或一个bool (例如从映射中获取元素时)，指示是否存在值。
• 另一个实现可以称为RWLockedStack (或简单地称为Stack)。

我还建议对这个RWLockedStack做一些修改：

• 在声明互斥必须保护对一个或多个字段的访问的结构时，将互斥对象置于它将保护的字段之上，作为最佳实践。(来源)
• 嵌入Stacker接口而不是UnsafeStack对象

可能的代码：

type RWLockedStack struct {
    lock  sync.RWMutex // before the protected members
    stack Stacker      // use the Stacker interface
}

func (cs *RWLockedStack) Len() int {
    cs.lock.RLock()
    defer cs.lock.RUnlock()
    return cs.stack.Len()
}