【数据结构golang版】第一篇:栈的实现

想复习一下数据结构的知识,最好的方式就是敲一遍代码啊,上学期是用C语言学的,在这里想用goalng把基本的数据结构重写一遍。今天先写简单的栈。

可能和C语言学过的有点儿不一样,第一个是我用了一个StackType的结构体,有两个成员:一个是Array,用来存储数据,一个是Top,用来指示栈顶的元素。定义的初始长度是MAX_SIZE = 10,元素的类型为Element ,本质是int64类型。没有入栈是默认值为零,出栈以后值也会变成0:这个地方我承认处理的不好。其实可以用golang中的slice每次只要append进去就好了,不过我觉得那种的话就太方便了,完全没有意义去判断栈满,于是就还是像上面那种处理了。OK ,现在上代码:

package main

//栈的实现
import (
"fmt"
)

const (
MAX_SIZE = 10 //最大元素量
EMPTY    = -1 //空值
)

//元素类型
type Element int64

//stack 结构体
type StackType struct {
Array []Element //数组
Top   int       //栈顶指示器
}

//创建Stack
func CreateStack() StackType {
var stack StackType
stack.Array = make([]Element, MAX_SIZE)
stack.Top = -1
fmt.Println("Create successful!")
return stack
}

//入栈
func Push(stack *StackType, data Element) {
if !IsFull(stack) {
stack.Top++
stack.Array[stack.Top] = data
fmt.Println("Push OK!")
fmt.Println(stack.Array)
} else {
fmt.Println("stack is FULL!")
fmt.Println(data, "can't Push")
fmt.Println(stack.Array)
}
}

//出栈
func Pop(stack *StackType) Element {
if !IsEmpty(stack) {
data := stack.Array[stack.Top]
stack.Array[stack.Top] = 0
stack.Top--
fmt.Println("Pop OK!")
fmt.Println("data is", data)
fmt.Println(stack.Array)
return data
} else {
fmt.Println("stack is EMPTY!")
return EMPTY
}
}

//取栈顶元素
func GetTopData(stack *StackType) Element {
return stack.Array[stack.Top]
}

//判断栈满
func IsFull(stack *StackType) bool {
return stack.Top >= MAX_SIZE-1
}

//判断栈空
func IsEmpty(stack *StackType) bool {
return stack.Top == -1
}

//主函数
func main() {
stack := CreateStack()  //新建
Push(&stack, 80000)     //进栈
data := GetTopData(&stack)   //取栈顶元素
fmt.Println(data)
Push(&stack, 1951569)
Pop(&stack)      //出栈
}

这就是基本的栈的实现了。做了一些小的处理,基本能实现静态栈的功能。

尽量写下去吧,用golang实现一遍基本的数据结构:栈,队列,链表,二叉树,哈弗曼树,查找和排序的几种不同算法。自己给自己加油!

刘凯宁@C2P
20140811

Share