golang没有提供stack的实现，只能自己搞一把了。
方案1：使用slice
type IntStack struct {
list []int
}
func (s *IntStack) Empty() bool {
return len(s.list) == 0
}
func (s *IntStack) Push(item int) {
s.list = append(s.list, item)
}
func (s *IntStack) Pop() int {
if s.Empty() {
return -1
}
lth := len(s.list)
top := s.list[lth-1]
s.list = s.list[0:lth-1]
return top
}
func (s *IntStack) Top() int {
if s.Empty() {
return -1
}
return s.list[len(s.list)-1]
}
方案2：使用container.list
type stack struct {
list *list.List
}
func NewStack() *stack {
return &stack{
list: list.New(),
}
}
func (s *stack) Push(v interface{}) {
s.list.PushBack(v)
}
func (s *stack) Pop() interface{} {
top := s.list.Back()
if top == nil {
return nil
}
s.list.Remove(top)
return top.Value
}
func (s *stack) Top() interface{} {
return s.list.Back().Value
}
func (s *stack) Empty() bool {
return s.list.Len() == 0
}
应用场景
type IntStack struct {
list []int
}
func (s *IntStack) Empty() bool {
return len(s.list) == 0
}
func (s *IntStack) Push(v int) {
s.list = append(s.list, v)
}
func (s *IntStack) Pop() int {
if s.Empty() {
return -1
}
lth := len(s.list)
top := s.list[lth-1]
s.list = s.list[0:lth-1]
return top
}
type StringStack struct {
list []string
}
func (s *StringStack) Empty() bool {
return len(s.list) == 0
}
func (s *StringStack) Push(v string) {
s.list = append(s.list, v)
}
func (s *StringStack) Pop() string {
if s.Empty() {
return ""
}
lth := len(s.list)
top := s.list[lth-1]
s.list = s.list[0:lth-1]
return top
}
func decodeString(s string) string {
intStack := &IntStack{}
strStack := &StringStack{}
var curStr string
var k int
for i := 0; i < len(s); i++ {
if s[i] >= '0' && s[i] <= '9' {
k = k * 10 + int(s[i] - '0')
} else if s[i] == '[' {
intStack.Push(k)
strStack.Push(curStr)
curStr = ""
k = 0
} else if s[i] == ']' {
tmp := curStr
curStr = strStack.Pop()
curStr += strings.Repeat(tmp, intStack.Pop())
} else {
curStr += string(s[i])
}
}
return curStr
}