栈

如何理解栈

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

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()
}

执行结果