Concurrency-safe stack implementation in Go

Question

As Go doesn't come with a lot of collection structures, I've implemented stacks myself, building off some sample code I found floating around. I've then tried to extend it further by:

• Making a "Stacker" interface for different implementations of stacks.
• Making an implementation that is safe for use by concurrent goroutines using mutexes.

I've only recently learned how mutexes work, so I want to be sure I'm using them right. The ConcurrentStack struct is just a wrapper around Stack with a read/write mutex.

• Am I using sync.RWMutex correctly?
• Disregarding the fact I will have little control over the order concurrent goroutines push elements onto the stack, will this always work safely?

Code:

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

• Elias Van Ootegem: Why do you differentiate between Stack and ConcurrentStack? If I use a stack implementation, the first thing I want to know is whether or not it's implemented in a thread-safe way. A stack is a stack, is a stack, and a stack should be thread safe. I also don't get the Peek function. By definition that function is untrustworthy: you might get the current top element, but between you calling Peek and Pop, the top element might have changed already

Answer 1

• Your code is mostly fine. The following comments are nitpicking.
• I agree with Elias, your default implementation should be thread-safe.
• Instead of returning nil, I would suggest your Pop function returns (interface{}, error), and return an error if you're trying to pop an empty stack. It allows you to store nil in the stack (which you might want to forbid, but then, do it explicitly), and forces the caller to think about this possibility.
• stackElement is needlessly verbose. It's just a node. Call it node.
• Your documentation of Stack mentions implementation, which isn't very good practice. Say that all operations are guaranteed to be in O(1), that's the main and only important bit.

Answer 2

Adding on Ted's answer:

• you could name the base implementation UnsafeStack (or MonothreadStack)
• on Pop, you could return an error (if stack empty) or a bool (like when getting an element from a map) telling if there was a value
• the other implementation could be called RWLockedStack (or simply Stack)

I would also suggest a couple of changes on this RWLockedStack:

• When declaring a struct where the mutex must protect access to one or more fields, place the mutex above the fields that it will protect as a best practice. (source)

• embed the Stacker interface instead of a UnsafeStack object

Possible code:

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