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>
|