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

如何理解栈

栈其实十分好理解,后进者先出,先进者后出,就是典型的栈的结构。


2019-08-18 17-15-13屏幕截图.png

当一个数据只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,就应该选择“栈”这种数据结构。

如何实现一个栈

栈有 顺序栈链式栈 。顺序栈是由数组实现的,而链式栈是由链表实现的。
有了实现方式还差栈的最常规操作,出栈和入栈。这里利用数组实现一个顺序栈。

顺序栈

一个最基础的顺序栈 实现(使用golang)

type ArrayStack struct {
    Item  []string     // 数组
    Cnt   int          // 栈中元素个数
    n     int          // 栈的大小
}

func (s *ArrayStack) InitStack(n int) {
    s.Item  = make([]string,n)
    s.n     = n
    s.Cnt   = 0
}

// 入栈操作
func (s *ArrayStack) Push(item string) error {
    // 数组空间不够了,直接返回 error , 入栈失败
    if s.Cnt == s.n {
        return errors.New("The Stack Is Full.")
    }
    s.Item[s.Cnt] = item
    s.Cnt++
    return nil
}

// 出栈操作
func (s *ArrayStack) Pop() (string,error) {
    // 栈为空,直接返回 error , 出栈失败
    if s.Cnt == 0 {
        return "",errors.New("The Stack Is Empty.")
    }
    tmp := s.Item[s.Cnt-1]
    s.Cnt--
    return tmp,nil
}
栈在函数中的应用。

函数调用栈,操作系统会给每一个线程分配一块独立的内存空间,这块内存被组织成了“栈”这种结构。栈是用来存放临时变量的,每进入一个函数,就会将临时变量作为一个栈帧压入栈。当被调用函数执行完成之后,对应栈帧会被弹出。

func add(x,y int) int {
    var sum int
    sum = x+y
    return sum
}

func main() {
    var a   int = 1
    var ret int
    var res int

    ret = add(3,5)
    res = a + ret
    fmt.Println(res)
}
函数栈

关于栈相关的题目在leetcode上可以尝试 20,155,232,844,224,682,496

如 20 题 有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
例如 “[][]{()[]}” true
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses

利用栈来解决。

type Stack struct {
    item  []string
    cnt   int
}

func (s *Stack) Pop()  {  // 这个pop只弹出就可以了,不需要返回内容
    s.item[s.cnt-1] = ""
    if s.cnt > 0 {
        s.cnt--  // 指针偏移一下
    }
}

func (s *Stack) Push(str string)  {
    if s.cnt < 10 {
        s.item[s.cnt] = str
    } else {
        s.item = append(s.item,str)
    }
    s.cnt ++
}

func (s *Stack) InitStack() {
    s.item = make([]string,10)
    s.cnt = 0
}

func (s *Stack) GetTop() string {
    if s.cnt - 1 < 0 {
        return ""
    }
    return s.item[s.cnt-1]
}

func (s *Stack) IsEmpty() bool {
    return s.cnt == 0
}

func isValid(s string) bool {
    ss := &Stack{}
    ss.InitStack()

    for i := 0; i < len(s); i++{
        top := ss.GetTop()
        switch top {
        case "{":
            if string(s[i]) == "}" {   // 遇到一对 就弹出
                ss.Pop()
            } else {
                ss.Push(string(s[i]))  // 否则再压入栈中
            }
        case "(":
            if string(s[i]) == ")" {
                ss.Pop()
            }else {
                ss.Push(string(s[i]))
            }
        case "[":
            if string(s[i]) == "]" {
                ss.Pop()
            }else {
                ss.Push(string(s[i]))
            }
        default:
            ss.Push(string(s[i]))
        }

    }

    return ss.IsEmpty()
}

执行结果



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

本文来自:简书

感谢作者:OOM_Killer

查看原文:

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

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