Golang 数据结构之【4.6链栈存储】

链栈的介绍

对于链钱来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如
果真的发生，那时的计算机操作系统已经面临死机崩溃的情况，而不是这个栈是
否溢出的问题。
但对于空栈来说，链表原定义是头指针指向空那么链栈的空其实就是 top=nil
的时候。

top 为栈顶指针

图片来源于《大话数据结构》

链栈的push操作

图片来源于《大话数据结构》
链栈的pop操作

图片来源于《大话数据结构》

go实现的代码如下：

package main

import (
    "errors"
    "fmt"
)

type SElemType int //节点数据类型

// 链栈节点结构
type LinkNode struct {
    data SElemType  //节点数据
    next *LinkNode  // 下个节点的指针
}

// 链栈结构
type LinkStack struct {
    top *LinkNode  //栈顶节点指针
    count int      //链栈长度
}

// 初始化一个空栈
func (l *LinkStack) InitStack()  {
    l.top = nil
    l.count = 0
}

// 若栈l为空栈，则返回true 否则返回false
func (l *LinkStack) IsEmpty() bool {
    if l.count == 0 {
        return true
    } else {
        return false
    }
}

// 返回l的元素个数，即栈的长度
func (l *LinkStack) StackLength() int {
    return l.count
}

// 若栈不空，则用data返回l的栈顶元素,否则返回error
func (l *LinkStack) GetTop() (data SElemType, err error) {
    if l.top == nil {
        return 0 ,errors.New("stack is empty")
    } else {
        data = l.top.data
        return
    }
}

// 插入元素data为新的栈顶元素
func (l *LinkStack) Push(data SElemType)  {
    node := new(LinkNode)
    node.data = data
    node.next = l.top  //把当前的栈顶元素赋值给新节点的直接后继
    l.top = node    // 将新的节点node赋值给栈顶指针
    l.count++
}

func (l *LinkStack) Pop() (data SElemType, err error) {
    if l.IsEmpty() {
        return 0, errors.New("stack is empty")
    }
    data = l.top.data
    l.top =  l.top.next     // 使得栈顶指针下移一位，指向后一节点
    l.count--
    return
}

//遍历整个栈
func (l *LinkStack) Traverse() {
    node := l.top

    for node != nil {
        fmt.Println(node.data)
        node = node.next
    }
}


func main()  {
    var s LinkStack
    s.InitStack()
    for j:=1;j <= 10 ; j++ {
        s.Push(SElemType(j))
    }

    fmt.Println("栈中的元素为：")
    s.Traverse()
    e, _ := s.Pop()
    fmt.Println("弹出的元素为：", e)
    fmt.Println("栈是否为空：", s.IsEmpty())
    fmt.Println("栈的长度：", s.StackLength())

}

最后编辑于：2019.05.16 13:58:06