-
Notifications
You must be signed in to change notification settings - Fork 0
/
stack.go
161 lines (142 loc) · 4.48 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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package arraystack
import (
"github.com/golanglibs/gocollections/generic"
"github.com/golanglibs/gocollections/list/arraylist"
)
/*
Array-based stack. Last element to be pushed will be popped first (LIFO).
It uses gocollections/list/arraylist to perform stack operations. This implementation will outperform the
linked list stack implementation (gocollections/list/linkedliststack) in terms of latency due to the
contiguous nature of the internal container which improves CPU cache utilization. However, this comes at the
cost of extra memory usage if there is a big fluctuation in the size of the stack between operations because
it will not free the memory in the internal container that was allocated when there were more elements pushed
in the stack
Implements Stacker and Collectioner.
Stack is not thread safe
*/
type Stack[T any] struct {
container arraylist.List[T]
}
/*
Creates a new instance of Stack with the given elements with a default equality comparer
and returna pointer to the instance.
If no elements are given, then an empty stack is created. Elements must be comparable
*/
func New[K comparable](elements ...K) Stack[K] {
return Stack[K]{
container: arraylist.New(elements...),
}
}
/*
Creates a new instance of Stack with the given elements with nil equality comparer
and returns pointer to the instance.
If no elements are given, then an empty queue is created. Elements can be of any type
*/
func NewOfAny[T any](elements ...T) Stack[T] {
return Stack[T]{
container: arraylist.NewOfAny(elements...),
}
}
/*
Creates a new instance of Stack from the given collection with a default equality comparer
and returns pointer to the new instance.
Elements of the given collection must be comparable
*/
func NewFromCollection[K comparable](c generic.Collectioner[K]) Stack[K] {
return Stack[K]{
container: arraylist.NewFromCollection(c),
}
}
/*
Creates a new instance of Stack from the given collection with nil equality comparer
and returns pointer to the instance.
Elements of the given collection can be of any type
*/
func NewOfAnyFromCollection[T any](c generic.Collectioner[T]) Stack[T] {
return Stack[T]{
container: arraylist.NewOfAnyFromCollection(c),
}
}
/*
Sets the equality comparer with the given equals function. Implements Stacker.SetEqualityComparer
*/
func (s *Stack[T]) SetEqualityComparer(equals func(a *T, b *T) bool) {
s.container.SetEqualityComparer(equals)
}
/*
Returns the length of the Stack. Implements Stacker.Size and Collectioner.Size
*/
func (s *Stack[T]) Size() int {
return s.container.Size()
}
/*
Returns true if the Stack is empty. Implements Stacker.Empty and Collectioner.Empty
*/
func (s *Stack[T]) Empty() bool {
return s.container.Empty()
}
/*
Adds the given element to the stack. Implements Stacker.Push
*/
func (s *Stack[T]) Push(element T) {
s.container.Add(element)
}
/*
Removes the most recently pushed element in the stack. Panics if Stack is empty.
Implements Stacker.Pop
*/
func (s *Stack[T]) Pop() {
if s.container.Empty() {
panic("Stack.Pop failed because stack is empty")
}
s.container.RemoveBack()
}
/*
Returns a reference to the most recently pushed element in the stack without removing it. Panics if Stack is
empty. Implements Stacker.Peek
*/
func (s *Stack[T]) Peek() *T {
if s.container.Empty() {
panic("Stack.Peek failed because stack is empty")
}
return s.container.Back()
}
/*
Adds the given element to the front of the stack. Always returns true.
Stack.Add functions exactly the same as Stack.Push except that it returns bool.
Implements Stacker.Add and Collectioner.Add
*/
func (s *Stack[T]) Add(element T) bool {
s.container.Add(element)
return true
}
/*
Removes the the given element and returns true if present in the Stack.
Returns false if the given element does not exist.
Implements Stacker.Remove and Collectioner.Remove
*/
func (s *Stack[T]) Remove(element T) bool {
return s.container.Remove(element)
}
/*
Returns true if the given element exists in the Stack. Returns false otherwise.
Implements Stacker.Contains and Collectioner.Contains
*/
func (s *Stack[T]) Contains(element T) bool {
return s.container.Contains(element)
}
/*
Empties the Stack.
Implements Stacker.Clear and Collectioner.Clear
*/
func (s *Stack[T]) Clear() {
s.container.Clear()
}
/*
Iterates through each element in the stack and executes the given function. Note that the order of
iteration will be the opposite of the order each element would be popped
Implements Stacker.ForEach and Collectioner.ForEach
*/
func (s *Stack[T]) ForEach(do func(*T)) {
s.container.ForEach(do)
}