124 lines
2.7 KiB
Markdown
124 lines
2.7 KiB
Markdown
---
|
||
title: 使用go实现链栈
|
||
tags: go,数据结构,链栈
|
||
categories: 数据结构
|
||
date: 2022-01-09 10:28:29
|
||
---
|
||
|
||
# 栈的定义
|
||
|
||
栈是一种先进后出的数据结构，日常使用较为广泛，可以将其比喻成一个瓶子，先放进去的东西掉在了最下面，所以后放出来，栈一般只提供了两种操作方式，分别为入栈和出栈。栈分为链栈和顺序栈，顺序栈使用数组存储数据，链栈采用单链表村粗数据，我们今天是实现的链栈。
|
||
|
||
## 结构定义
|
||
|
||
```go
|
||
type Stack struct {
|
||
data interface{}
|
||
next *Stack
|
||
size int
|
||
sync.Mutex
|
||
}
|
||
```
|
||
data对应存储数据，next是一个实例指针，指向下面的一个元素，size用来存储栈的大小，其实可有可无，sync.Mutex是解决并发操作的问题。
|
||
|
||
## 初始化栈
|
||
|
||
```go
|
||
func newStack() *Stack {
|
||
s := new(Stack)
|
||
s.next = nil
|
||
s.size = 0
|
||
return s
|
||
}
|
||
```
|
||
首先创建一个Stack对象，将其next指针域置为nil，size置为0.
|
||
|
||
# 栈的相关操作
|
||
|
||
## 入栈
|
||
|
||
```go
|
||
func (s *Stack) push(element interface{}) {
|
||
s2 := new(Stack)
|
||
s2.next = s.next
|
||
s2.data = element
|
||
s.Lock()
|
||
s.size ++
|
||
s.next = s2
|
||
s.Unlock()
|
||
}
|
||
```
|
||
|
||
入栈首先创建一个新的节点，然后将节点的指针指向头节点的指向，然后为该节点赋值，然后操纵头节点之前应该上锁，将头节点的size加一，同时头节点的指针指向新创建的节点，最后取消锁。
|
||
|
||
## 出栈
|
||
|
||
```go
|
||
func (s *Stack) pop() interface{} {
|
||
if s.next == nil {
|
||
return nil
|
||
}
|
||
node := s.next
|
||
s.Lock()
|
||
s.size --
|
||
s.next = node.next
|
||
s.Unlock()
|
||
return node.data
|
||
}
|
||
```
|
||
出栈首先判断头节点的指针是否为nil,若为nil则代表栈内没有元素，返回nil值，然后将栈顶节点取出来，然后将头节点的size减一，同时将头节点的指针域指向栈顶节点的下一节点，最后返回栈顶节点的值。
|
||
|
||
|
||
## 获取栈顶节点的值
|
||
|
||
|
||
```go
|
||
func (s *Stack) getTop() interface{} {
|
||
if s.next == nil {
|
||
return nil
|
||
}
|
||
return s.next.data
|
||
}
|
||
```
|
||
和出栈不一样的地方是，该方法只获取栈顶节点的值，不会删除栈顶节点。
|
||
|
||
## 全部出栈转为数组
|
||
|
||
```go
|
||
func (s *Stack) toArray() []interface{} {
|
||
array:= make([]interface{}, s.size)
|
||
length := s.size
|
||
for i := 0; i < length; i++ {
|
||
array[i] = s.pop()
|
||
}
|
||
return array
|
||
}
|
||
```
|
||
其中要将s.size单独取出来，因为在循环过程中出栈，s.size的值会发生改变。
|
||
|
||
# 测试
|
||
```go
|
||
func main() {
|
||
stack := newStack()
|
||
stack.push(1)
|
||
stack.push(2)
|
||
stack.push(3)
|
||
stack.push(1)
|
||
stack.push(4)
|
||
|
||
fmt.Println(stack.pop())
|
||
fmt.Println(stack.pop())
|
||
fmt.Println("栈的剩余元素个数：",stack.size)
|
||
|
||
fmt.Println(stack.toArray())
|
||
}
|
||
|
||
|
||
// 4
|
||
// 1
|
||
// 栈的剩余元素个数： 3
|
||
// [3 2 1]
|
||
|
||
```
|
||
|
||
## 个人博客地址：<https://vtsqr.xyz> |