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
|
package query
import "errors"
// not threadsafe implementation of stack
type nodeStack struct {
buf []*Node
}
func (s nodeStack) Push(n *Node) {
s.buf = append(s.buf, n)
}
func (s nodeStack) Pop() *Node {
last_index := len(s.buf) - 1
n := s.buf[last_index]
s.buf = s.buf[:last_index]
return n
}
func (s nodeStack) Peek() *Node {
return s.buf[len(s.buf)-1]
}
func (s nodeStack) IsEmpty() bool {
return len(s.buf) == 0
}
type nodeQueue struct {
buf []*Node
head int
tail int
}
func makeNodeQueue(initial *Node, cap int) nodeQueue {
if cap < 1 {
panic("Invalid nodeQueue Capacity")
}
q := nodeQueue{
buf: make([]*Node, 0, cap),
head: 0,
tail: 1,
}
q.buf[0] = initial
return q
}
func (q nodeQueue) Enqueue(n *Node) error {
q.buf[q.tail] = n
new_tail := (q.tail + 1) % len(q.buf)
if new_tail == q.head {
return errors.New("Queue out of capacity")
}
q.tail = new_tail
return nil
}
func (q nodeQueue) Dequeue() (*Node, error) {
if q.head == q.tail {
return nil, errors.New("Empty Queue")
}
n := q.buf[q.head]
q.head = (q.head + 1) % len(q.buf)
return n, nil
}
func (q nodeQueue) PeekHead() (*Node, error) {
if q.head == q.tail {
return nil, errors.New("Empty queue")
}
return q.buf[q.head], nil
}
func (q nodeQueue) PeekTail() (*Node, error) {
if q.head == q.tail {
return nil, errors.New("Empty Queue")
}
return q.buf[q.tail-1], nil
}
func (q nodeQueue) IsEmpty() bool {
return q.head == q.tail
}
|
