栈
栈（stack）又名堆栈，它是一种运算受限的线性表。 限定仅在表尾进行插入和删除操作的线性表。 这一端被称为栈顶，相对地，把另一端称为栈底。
栈的实现可以通过数组和链表来实现， 用数组实现的可以称为顺序栈， 用链表实现的成为链式栈
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
| package stack
type ArrayStack struct {
data []string
length int
size int
}
func NewArrayStack(len int) *ArrayStack{
if len <0 {
return nil
}
return &ArrayStack{
data: make([]string, len),
length: len,
size: 0,
}
}
func (me *ArrayStack) push(data string) bool {
if me.length == me.size {
return false
}
me.data = append(me.data, data)
me.size++
return true
}
func (me *ArrayStack) pop() string{
if me.size == 0 {
return ""
}
item := me.data[me.size - 1]
me.size--
return item
}
type node struct {
next *node
val interface{}
}
type LinkedListStack struct {
top *node
}
func NewLinkedListStack() *LinkedListStack {
return &LinkedListStack{nil}
}
func (me LinkedListStack) IsEmpty() bool {
return me.top == nil
}
func (me *LinkedListStack) Push(data interface{}) bool {
nd := &node{val: data, next: nil}
if me.IsEmpty() {
me.top = nd
} else {
nd.next = me.top
me.top = nd.next
}
return true
}
func (me *LinkedListStack) Pop() interface{} {
if me.IsEmpty() {
return nil
}
result := me.top.val
me.top = me.top.next
return result
}
func (me *LinkedListStack) Top() interface{} {
if me.IsEmpty() {
return nil
}
return me.top.val
}
func (me *LinkedListStack) Print() {
if me.IsEmpty() {
return
} else {
curr := me.top
for nil != curr {
fmt.Println(curr.val)
curr = curr.next
}
}
}
|