栈,队列

栈(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
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
}
}

}