Last active
August 15, 2017 19:04
Star
You must be signed in to star a gist
LIFO Stack implemented with Go
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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