后进先出，不能从中间任意抽取，砌墙模型。栈有两种实现方式：基于数组的顺序栈和基于链表的链式栈。
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
image.png

实现方式

  • 顺序栈

用数组实现

  1. type AStack struct {
  2.     items []string
  3.     lock  sync.RWMutex
  4. }
  6. func (s *AStack) Push(val string) {
  7.     s.lock.Lock()
  8.     defer s.lock.Unlock()
  9.     s.items = append(s.items, val)
  10.     return 
  11. }
  13. func (s *AStack) Pop() string {
  14.     s.lock.Lock()
  15.     var res string
  16.     defer s.lock.Unlock()
  17.     if len(s.items) != 0 {
  18.         res = s.items(len(s.items)-1)
  19.         s.items = s.items[:len(s.items)-1]
  20.     }
  21.     return res
  22. }
  • 链式栈

用链表实现

  1. type node struct {
  2.     item string 
  3.     prv *node
  4. }
  6. type LStack struct {
  7.     head *node
  8.     len int
  9.     lock *sync.RWMutex
  10. }
  12. func (s *LStack) Push(val string) {
  13.     s.lock.Lock()
  14.     defer s.lock.Unlock()
  15.     // 新的结点连接到原始链表的头
  16.     n := &node{
  17.         item: val
  18.         prv: s.head
  19.     }
  20.     // 将原始链表的头移动到新结点
  21.     s.head = n
  22.     s.len++
  23. }

栈的应用

1. 括号匹配

如LeetCode题目20

2. 进制转换

参考：https://blog.csdn.net/gavin_john/article/details/71374487