今天用go语言简单的写了一下stack的方法。
为了以后方便查看，当做笔记整理了一下~~
1.栈(Stack)
维基百科里是这么解释的。
是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。
因而按照后进先出（LIFO, Last In First Out）的原理运作。
具体的详解可以参考这篇文章里的Stack部分栈(STACK), 堆(HEAP), 队列(QUEUE) 是什么？
2.数组栈
struct
type Stack struct {
Capacity int
Top int
Values []int
}
进栈(push)
func (s *Stack) Push(val int) bool {
if s.Top >= s.Capacity {
fmt.Println("Stack Overflow!")
return false
}
s.Top++
s.Values[s.Top] = val
return true
}
出栈(pop)
func (s *Stack) Pop() int {
if s.Top < 0 {
fmt.Println("Stack Underflow!")
return 0
}
result := s.Values[s.Top]
s.Top--
return result
}
查看栈顶元素(peek)和IsEmpty()
func (s *Stack) Peek() int {
if s.Top < 0 {
fmt.Println("Stack Underflow!")
return 0
}
result := s.Values[s.Top]
return result
}
func (s *Stack) IsEmpty() bool {
return s.Top < 0
}
执行结果
func main() {
stack := Stack{}
stack.Capacity = 10
stack.Top = -1
stack.Values = make([]int, stack.Capacity)
stack.Push(10)
stack.Push(11)
stack.Push(12)
fmt.Println("-------- stack.Values --------")
fmt.Printf("%+v", stack.Values)
fmt.Println("")
fmt.Println("-------- stack.IsEmpty() --------")
fmt.Println(stack.IsEmpty())
fmt.Println("-------- stack.Pop() --------")
fmt.Println(stack.Pop())
fmt.Println("-------- stack.Peek() --------")
fmt.Println(stack.Peek())
执行结果为：
$ go run main.go
-------- stack.Values --------
[10 11 12 0 0 0 0 0 0 0]
-------- stack.IsEmpty() --------
false
-------- stack.Pop() --------
12
-------- stack.Peek() --------
11
3.链式栈
struct
type LinkStack struct {
Top *StackNode
}
type StackNode struct {
Value int
Next *StackNode
}
进栈(push)
func (s *LinkStack) Push(val int) bool {
newNode := StackNode{Value: val}
if s.Top == nil {
s.Top = &newNode
} else {
newNode.Next = s.Top
s.Top = &newNode
}
return true
}
出栈(pop)
func (s *LinkStack) Pop() int {
if s.Top == nil {
fmt.Println("stack is empty!")
return -1
}
result := s.Top
s.Top = result.Next
return result.Value
}
查看栈顶元素(peek)和IsEmpty()，Print()
func (s *LinkStack) Peek() int {
if s.Top == nil {
fmt.Println("stack is empty!")
return -1
}
return s.Top.Value
}
func (s *LinkStack) IsEmpty() bool {
return s.Top == nil
}
func (node *StackNode) Print() {
if node == nil || node.Value == 0 {
return
} else {
fmt.Print(node.Value, " ")
node.Next.Print()
}
}
执行结果
func main() {
linkStack := LinkStack{}
linkStack.Top = &StackNode{Value: 10}
linkStack.Top.Next = &StackNode{Value: 11}
linkStack.Top.Next.Next = &StackNode{Value: 12}
fmt.Println("-------- linkStack.Values --------")
linkStack.Top.Print()
fmt.Println("")
fmt.Println("-------- stack.IsEmpty() --------")
fmt.Println(linkStack.IsEmpty())
fmt.Println("-------- stack.Pop() --------")
fmt.Println(linkStack.Pop())
fmt.Println("-------- stack.Peek() --------")
fmt.Println(linkStack.Peek())
fmt.Println("-------- linkStack.Values --------")
linkStack.Top.Print()
}
执行结果为：
$ go run main.go
-------- linkStack.Values --------
10 11 12
-------- stack.IsEmpty() --------
false
-------- stack.Pop() --------
10
-------- stack.Peek() --------
11
-------- linkStack.Values --------
11 12
欢迎大家的意见和交流
email: li_mingxie@163.com
网友评论