RunnerGo - 社区

定义：

栈是一种只能在一端插入或删除的线性表，插入和删除都是操作的栈顶，一般称之为入栈和出栈

特性：

先进后出（FILO）

存储结构：

顺序栈和链式栈两种

栈所应该有的方法：

Push() 入栈

Pop() 出栈

Len() 栈的长度

Peek() 栈的栈顶

IsEmpty() 是否为空

Print() 遍历打印

顺序栈的实现

type Stack struct {
  Top  interface{}
  Data []interface{}
}


// NewStack 初始化一个栈
func NewStack() *Stack {
  s := &Stack{}
  var data []interface{}
  s.Data = data
  return s
}

// IsEmpty 是否为空
func (s *Stack) IsEmpty() bool {
  if s.Data == nil || len(s.Data) <= 0 {
    return true
  }
  return false

}


// Push 入栈
func (s *Stack) Push(data interface{}) {
  s.Top = data
  s.Data = append(s.Data, data)
}

// Pop 出栈
func (s *Stack) Pop() interface{} {
  if s.IsEmpty() {
    return nil
  }
  value := s.Top
  s.Data = s.Data[:s.Len()-1]
  if s.Len() >= 1 {
    s.Top = s.Data[s.Len()-1]
  } else {
    s.Top = nil
  }

  return value
}

// Print 遍历打印
func (s *Stack) Print() {
  if s.IsEmpty() {
    return
  }
  for _, v := range s.Data {
    fmt.Println(v)
  }
}

// Peek 栈顶元素
func (s *Stack) Peek() interface{} {
  return s.Top
}


// Len 获取长度
func (s *Stack) Len() int {
  if s.IsEmpty() {
    return 0
  }
  return len(s.Data)
}

链式栈的实现

type LinkList struct {
  value interface{}
  Next  *LinkList
}

type LinkStack struct {
  length   int
  LinkList *LinkList
}

func NewLinkStack() *LinkStack {
  return &LinkStack{}
}

func (ls *LinkStack) Push(value interface{}) {
  linkList := &LinkList{
    value: value,
  }
  if ls.LinkList == nil {
    ls.LinkList = linkList
  } else {
    linkList.Next, ls.LinkList = ls.LinkList, linkList
  }
  ls.length++
}

func (ls *LinkStack) Pop() interface{} {
  if ls.IsEmpty() {
    return nil
  }

  value := ls.LinkList.value
  ls.LinkList = ls.LinkList.Next
  ls.length--
  return value
}

func (ls *LinkStack) Len() int {
  return ls.length
}

func (ls *LinkStack) IsEmpty() bool {
  if ls.LinkList == nil {
    return true
  } else {
    return false
  }
}

func (ls *LinkStack) Peek() interface{} {
  if ls.IsEmpty() {
    return nil
  }
  return ls.LinkList.value
}

func (ls *LinkStack) Print() {
  if ls.IsEmpty() {
    return
  }
  link := ls.LinkList
  for link != nil {
    fmt.Println(link.value)
    link = link.Next
  }
}

【每日一算法】实现一个栈