go实现数组栈
数组内存连续，内存可计算，
删除和插入慢 最坏时间复杂度是o(n)
查找和修改 是o(1)
栈可以模拟递归，完成深度遍历
队列可以完成广度遍历
go 实现ArrayList
1package ArrayList
2import (
3 "fmt"
4 "github.com/pkg/errors"
5)
6
7//定义接口
8type List interface {
9 Size() int //数组大小
10 Get(index int) (interface{}, error) //获得第index元素
11 Set(index int, newVal interface{}) error //修改
12 Insert(index int, newVal interface{}) error //插入
13 Append(newVal interface{}) //追加
14 Clear() //清空
15 Delete(index int) error //删除元素
16 String() string //返回字符串
17}
18
19//数据结构 可以存 整数，字符串，实数
20type ArrayList struct {
21 dataStore []interface{} //数组存储
22 TheSize int //数组大小
23}
24
25func NewArrayList() *ArrayList {
26 list := new(ArrayList)
27 list.dataStore = make([]interface{}, 0, 10) //开辟10个空间
28 list.TheSize = 0
29 return list
30}
31
32//返回数组的大小
33func (list *ArrayList) Size() int {
34 return list.TheSize //返回数组的大小
35}
36
37//获得元素
38func (list *ArrayList) Get(index int) (interface{}, error) {
39 if index < 0 || index >= list.TheSize {
40 return nil, errors.New("索引越界")
41 }
42 return list.dataStore[index], nil
43}
44func (list *ArrayList) Set(index int, newVal interface{}) error {
45 if index < 0 || index >= list.TheSize {
46 return errors.New("索引越界")
47 }
48 list.dataStore[index] = newVal
49 return nil
50}
51
52//追加
53func (list *ArrayList) Append(newVal interface{}) {
54 list.dataStore = append(list.dataStore, newVal)
55 list.TheSize++
56}
57
58//返回数组的字符串
59func (list *ArrayList) String() string {
60 return fmt.Sprint(list.dataStore)
61}
62
63//清空
64func (list *ArrayList) Clear() {
65 //重新开辟内存空间
66 list.dataStore = make([]interface{}, 0, 10)
67 list.TheSize = 0
68}
69
70//删除
71func (list *ArrayList) Delete(index int) error {
72 if index < 0 || index >= list.TheSize {
73 return errors.New("索引越界")
74 }
75 list.dataStore = append(list.dataStore[:index], list.dataStore[index+1:]...) //重新叠加 跳过index
76 list.TheSize--
77 return nil
78}
79
80//检查是否已经满了，满了就开辟2倍内存
81func (list *ArrayList) checkIsFull() {
82 if list.TheSize == cap(list.dataStore) {
83 newDataStore := make([]interface{}, 2*cap(list.dataStore), 2*cap(list.dataStore))
84 copy(newDataStore, list.dataStore)
85 list.dataStore = newDataStore
86 }
87}
88
89//插入
90func (list *ArrayList) Insert(index int, newVal interface{}) error {
91 if index < 0 || index >= list.TheSize {
92 return errors.New("索引越界")
93 }
94 //判断内存是否已经满了
95 list.checkIsFull()
96 //最后的元素 向后移动一位啊。
97 for allSize := list.TheSize; allSize > index; allSize-- {
98 list.dataStore[allSize] = list.dataStore[allSize-1]
99 }
100 list.dataStore[index] = newVal
101 list.TheSize++
102 return nil
103
104}
1package main
2
3import (
4 "ArrayList"
5 "fmt"
6)
7
8func main(){
9 list := ArrayList.NewArrayList()
10 list.Append(1)
11 list.Append(2)
12 list.Append(3)
13 list.Append("222")
14 fmt.Println(list)
15 fmt.Println(list.TheSize)
16 var p ArrayList.List=ArrayList.NewArrayList()
17 for i:=0;i<100;i++ {
18 p.Append(i)
19 fmt.Println(p)
20 }
21}
使用迭代器遍历数组
1package ArrayList
2
3import "github.com/pkg/errors"
4
5type Iterator interface {
6 HasNext() bool //是否有下一个
7 Next() (interface{}, error) //下一个
8 Remove() //删除当前索引元素
9 GetIndex() int //得到当前索引
10}
11
12type Iterable interface {
13 Iterator() Iterator //构造初始化接口
14}
15
16type ArraylistIterator struct {
17 list *ArrayList //数组指针
18 currentIndex int //当前索引
19}
20
21func (it *ArraylistIterator) HasNext() bool { //是否有下一个
22 return it.currentIndex < it.list.TheSize
23}
24
25//获得下一个元素
26func (it *ArraylistIterator) Next() (interface{}, error) {
27 if !it.HasNext() {
28 return nil, errors.New("没有下一个")
29 }
30 value, err := it.list.Get(it.currentIndex)
31 it.currentIndex++
32 return value, err
33}
34
35//删除当前索引元素
36func (it *ArraylistIterator) Remove() {
37 it.currentIndex--
38 it.list.Delete(it.currentIndex)
39}
40
41func (it *ArraylistIterator) GetIndex() int {
42 return it.currentIndex
43}
44
45//构造迭代器
46func (list *ArrayList) Iterator() Iterator {
47 it := new(ArraylistIterator)
48 it.list = list
49 it.currentIndex = 0
50 return it
51}
1//使用迭代器遍历数组
2func main() {
3 list := ArrayList.NewArrayList()
4 list.Append(1)
5 list.Append(2)
6 list.Append(3)
7 list.Append("222")
8 it := list.Iterator()
9 for it.HasNext() {
10 val, _ := it.Next()
11 fmt.Println(val)
12 }
13}
栈的实现
1package StackArray
2
3type StackArray interface {
4 Clear() //清空
5 Size()int //大小
6 Pop()interface{} //弹出
7 Push(data interface{})//压入
8 IsFull() bool //是否满了
9 IsEmpty() bool//是否为空
10}
11type Stack struct{
12 dataSource [] interface{}
13 capsize int //最大范围
14 currentsize int //实际使用大小
15}
16func NewStack()*Stack{
17 mystack:=new(Stack)
18 mystack.dataSource=make([]interface{},0,1000) //数组
19 mystack.capsize=1000//空间
20 mystack.currentsize=0
21 return mystack
22}
23func (mystack * Stack )Clear() {
24 mystack.dataSource=make([]interface{},0,1000) //数组
25 mystack.currentsize=0
26 mystack.capsize=1000//空间
27}
28func (mystack * Stack )Size()int {
29 return mystack.currentsize
30}
31func (mystack * Stack )Pop()interface{} {
32 if !mystack.IsEmpty(){
33 last:=mystack.dataSource[mystack.currentsize-1]//最后一个数据
34 mystack.dataSource=mystack.dataSource[:mystack.currentsize-1]//删除最后一个
35 mystack.currentsize--//删除
36 return last
37
38 }
39 return nil
40}
41func (mystack * Stack ) Push(data interface{}){
42 if !mystack.IsFull(){
43 mystack.dataSource=append(mystack.dataSource,data)//叠加数据，压入
44 mystack.currentsize++
45 }
46}
47func (mystack * Stack ) IsFull() bool { //判断满了
48 if mystack.currentsize>=mystack.capsize{
49 return true
50 }else{
51 return false
52 }
53}
54func (mystack * Stack )IsEmpty() bool{//判断为空
55 if mystack.currentsize==0{
56 return true
57 }else{
58 return false
59 }
60}
1func main() {
2 mystack := StackArray.NewStack()
3 mystack.Push(1)
4 mystack.Push(2)
5 mystack.Push(3)
6 mystack.Push(4)
7 fmt.Println(mystack.Pop())
8 fmt.Println(mystack.Pop())
9 fmt.Println(mystack.Pop())
10 fmt.Println(mystack.Pop())
11 mystack.Push(1)
12 fmt.Println(mystack.Pop())
13 mystack.Push(2)
14 fmt.Println(mystack.Pop())
15 mystack.Push(3)
16 fmt.Println(mystack.Pop())
17 mystack.Push(4)
18 fmt.Println(mystack.Pop())
19}
栈结合ArrayList实现 (ArrayListStack)
1package ArrayList
2
3type StackArray interface {
4 Clear() //清空
5 Size() int //大小
6 Pop() interface{} //弹出
7 Push(data interface{}) //压入
8 IsFull() bool //是否满了
9 IsEmpty() bool //是否空了
10}
11
12type Stack struct {
13 myarray *ArrayList
14 capsize int //栈最大空间（最大范围）
15}
16
17func NewArrayListStack() *Stack {
18 mystack := new(Stack)
19 mystack.myarray = NewArrayList()
20 mystack.capsize = 10 //空间
21 return mystack
22}
23func (mystack *Stack) Clear() {
24 mystack.myarray.Clear()
25}
26
27func (mystack *Stack) Size() int {
28 return mystack.myarray.TheSize
29}
30
31func (mystack *Stack) Pop() interface{} {
32 if mystack.IsEmpty() {
33 return nil
34 }
35 last := mystack.myarray.dataStore[mystack.myarray.TheSize-1]
36 mystack.myarray.Delete(mystack.myarray.TheSize - 1)
37 return last
38}
39
40func (mystack *Stack) Push(data interface{}) {
41 if !mystack.IsFull() {
42 mystack.myarray.Append(data)
43 }
44}
45
46func (mystack *Stack) IsEmpty() bool {
47 if mystack.myarray.TheSize == 0 {
48 return true
49 } else {
50 return false
51 }
52}
53
54func (mystack *Stack) IsFull() bool {
55 if mystack.myarray.TheSize >= mystack.capsize {
56 return true
57 } else {
58 return false
59 }
60}
1func main(){
2 mystack := ArrayList.NewArrayListStack()
3 mystack.Push(1)
4 mystack.Push(2)
5 mystack.Push(3)
6 mystack.Push(4)
7 fmt.Println(mystack.Pop())
8 fmt.Println(mystack.Pop())
9 fmt.Println(mystack.Pop())
10 fmt.Println(mystack.Pop())
11 mystack.Push(1)
12 fmt.Println(mystack.Pop())
13 mystack.Push(2)
14 fmt.Println(mystack.Pop())
15 mystack.Push(3)
16 fmt.Println(mystack.Pop())
17 mystack.Push(4)
18 fmt.Println(mystack.Pop())
19}
数组栈结合迭代器
1package ArrayList
2
3type StackArrayX interface {
4 Clear() //清空
5 Size() int //大小
6 Pop() interface{} //弹出
7 Push(data interface{}) //压入
8 IsFull() bool //是否满了
9 IsEmpty() bool //是否空了
10}
11
12type StackX struct {
13 myarray *ArrayList
14 Myit Iterator
15}
16
17func NewArrayListStackX() *StackX {
18 mystack := new(StackX)
19 mystack.myarray = NewArrayList()
20 mystack.Myit = mystack.myarray.Iterator()
21 return mystack
22}
23func (mystack *StackX) Clear() {
24 mystack.myarray.Clear()
25}
26
27func (mystack *StackX) Size() int {
28 return mystack.myarray.TheSize
29}
30
31func (mystack *StackX) Pop() interface{} {
32 if mystack.IsEmpty() {
33 return nil
34 }
35 last := mystack.myarray.dataStore[mystack.myarray.TheSize-1]
36 mystack.myarray.Delete(mystack.myarray.TheSize - 1)
37 return last
38}
39
40func (mystack *StackX) Push(data interface{}) {
41 if !mystack.IsFull() {
42 mystack.myarray.Append(data)
43 }
44}
45
46func (mystack *StackX) IsEmpty() bool {
47 if mystack.myarray.TheSize == 0 {
48 return true
49 } else {
50 return false
51 }
52}
53
54func (mystack *StackX) IsFull() bool {
55 if mystack.myarray.TheSize >= 10 {
56 return true
57 } else {
58 return false
59 }
60}
1func main() {
2 mystack := ArrayList.NewArrayListStackX()
3 mystack.Push(1)
4 mystack.Push(2)
5 mystack.Push(3)
6 mystack.Push(4)
7 fmt.Println(mystack.Pop())
8 fmt.Println(mystack.Pop())
9 fmt.Println(mystack.Pop())
10 fmt.Println(mystack.Pop())
11 mystack.Push(1)
12 mystack.Push(2)
13 mystack.Push(3)
14 mystack.Push(4)
15 for it := mystack.Myit; it.HasNext(); {
16 val, _ := it.Next()
17 fmt.Println(val)
18 }
19}