Skip to content

Instantly share code, notes, and snippets.

@gmichokostas
Last active August 15, 2017 19:04
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save gmichokostas/95e1b1063cc4992769d99600a952269f to your computer and use it in GitHub Desktop.
LIFO Stack implemented with Go
package stack
import "fmt"
// Stack is a LIFO data structure
type Stack struct {
len int
top *node
}
// Len return the length of this stack
func (s *Stack) Len() int {
return s.len
}
// New return a pointer to a new Stack
func New() *Stack {
return new(Stack)
}
// Push pushes an item onto this stack
func (s *Stack) Push(item interface{}) {
s.top = &node{item: item, next: s.top}
s.len++
}
// Pop removes the latest added item on the stack
func (s *Stack) Pop() (item interface{}) {
if s.len == 0 {
return nil
}
item, s.top = s.top.item, s.top.next
s.len--
return
}
// Search linearly for an item in this stack
func (s *Stack) Search(item interface{}) (found bool) {
currentNode := s.top
for currentNode != nil {
if s.top.item == item {
found = true
return
}
currentNode = currentNode.next
}
found = false
return
}
// Contains an item in the stack
func (s *Stack) Contains(item interface{}) bool {
return search(s.top, item)
}
// search recursively the stack for an item
func search(n *node, item interface{}) bool {
if n == nil {
return false
}
if n.item == item {
return true
}
return search(n.next, item)
}
func (s *Stack) String() string {
return fmt.Sprintf("Stack{len: %v\tnode: %v}", s.len, s.top)
}
type node struct {
item interface{}
next *node
}
func (n node) String() string {
return fmt.Sprintf("Node{item: %v\tnext: %v}", n.item, n.next)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment