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

JiBadBoy · · 629 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

  • 链栈的介绍

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

}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:JiBadBoy

查看原文:Golang 数据结构之【4.6链栈存储】

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

629 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传