-
Notifications
You must be signed in to change notification settings - Fork 37
/
stack.go
86 lines (74 loc) · 1.59 KB
/
stack.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package stack
type Stack struct {
top *Element
size int
max int
}
type Element struct {
value interface{}
next *Element
}
func NewStack(max int) *Stack {
return &Stack{max: max}
}
// Return the stack's length
func (s *Stack) Len() int {
return s.size
}
// Return the stack's max
func (s *Stack) Max() int {
return s.max
}
// Push a new element onto the stack
func (s *Stack) Push(value interface{}) {
if s.size+1 > s.max {
if last := s.PopLast(); last == nil {
panic("Unexpected nil in stack")
}
}
s.top = &Element{value, s.top}
s.size++
}
// Remove the top element from the stack and return it's value
// If the stack is empty, return nil
func (s *Stack) Pop() (value interface{}) {
if s.size > 0 {
value, s.top = s.top.value, s.top.next
s.size--
return
}
return nil
}
func (s *Stack) PopLast() (value interface{}) {
if lastElem := s.popLast(s.top); lastElem != nil {
return lastElem.value
}
return nil
}
//Peek returns a top without removing it from list
func (s *Stack) Peek() (value interface{}, exists bool) {
exists = false
if s.size > 0 {
value = s.top.value
exists = true
}
return
}
func (s *Stack) popLast(elem *Element) *Element {
if elem == nil {
return nil
}
// not last because it has next and a grandchild
if elem.next != nil && elem.next.next != nil {
return s.popLast(elem.next)
}
// current elem is second from bottom, as next elem has no child
if elem.next != nil && elem.next.next == nil {
last := elem.next
// make current elem bottom of stack by removing its next element
elem.next = nil
s.size--
return last
}
return nil
}