【算法笔记】stack的简单实践

李明燮(li_mingxie)
algorithm
Page content

今天用go语言简单的写了一下stack的方法。
为了以后方便查看，当做笔记整理了一下~~

1.栈(Stack)

维基百科里是这么解释的。

是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。
因而按照后进先出（LIFO, Last In First Out）的原理运作。

具体的详解可以参考这篇文章里的Stack部分栈(STACK), 堆(HEAP), 队列(QUEUE) 是什么？

2.数组栈

struct

type Stack struct {
 Capacity int
 Top      int
 Values   []int
}

进栈(push)

func (s *Stack) Push(val int) bool {
 if s.Top >= s.Capacity {
  fmt.Println("Stack Overflow!")
  return false
 }
 s.Top++
 s.Values[s.Top] = val
 return true
}

出栈(pop)

func (s *Stack) Pop() int {
 if s.Top < 0 {
  fmt.Println("Stack Underflow!")
  return 0
 }
 result := s.Values[s.Top]
 s.Top--
 return result
}

查看栈顶元素(peek)和IsEmpty()

func (s *Stack) Peek() int {
 if s.Top < 0 {
  fmt.Println("Stack Underflow!")
  return 0
 }
 result := s.Values[s.Top]
 return result
}

func (s *Stack) IsEmpty() bool {
 return s.Top < 0
}

执行结果

func main() {
 stack := Stack{}
 stack.Capacity = 10
 stack.Top = -1
 stack.Values = make([]int, stack.Capacity)

 stack.Push(10)
 stack.Push(11)
 stack.Push(12)
 fmt.Println("-------- stack.Values  --------")
 fmt.Printf("%+v", stack.Values)
 fmt.Println("")
 fmt.Println("-------- stack.IsEmpty()  --------")
 fmt.Println(stack.IsEmpty())
 fmt.Println("-------- stack.Pop()  --------")
 fmt.Println(stack.Pop())
 fmt.Println("-------- stack.Peek()  --------")
 fmt.Println(stack.Peek())

执行结果为：

$ go run main.go
-------- stack.Values  --------
[10 11 12 0 0 0 0 0 0 0]
-------- stack.IsEmpty()  --------
false
-------- stack.Pop()  --------
12
-------- stack.Peek()  --------
11

3.链式栈

struct

type LinkStack struct {
 Top *StackNode
}

type StackNode struct {
 Value int
 Next  *StackNode
}

进栈(push)

func (s *LinkStack) Push(val int) bool {
 newNode := StackNode{Value: val}
 if s.Top == nil {
  s.Top = &newNode
 } else {
  newNode.Next = s.Top
  s.Top = &newNode
 }
 return true
}

出栈(pop)

func (s *LinkStack) Pop() int {
 if s.Top == nil {
  fmt.Println("stack is empty!")
  return -1
 }
 result := s.Top
 s.Top = result.Next
 return result.Value
}

查看栈顶元素(peek)和IsEmpty()，Print()

func (s *LinkStack) Peek() int {
 if s.Top == nil {
  fmt.Println("stack is empty!")
  return -1
 }
 return s.Top.Value
}

func (s *LinkStack) IsEmpty() bool {
 return s.Top == nil
}

func (node *StackNode) Print() {
 if node == nil || node.Value == 0 {
  return
 } else {
  fmt.Print(node.Value, " ")
  node.Next.Print()
 }
}

执行结果

func main() {
 linkStack := LinkStack{}
 linkStack.Top = &StackNode{Value: 10}
 linkStack.Top.Next = &StackNode{Value: 11}
 linkStack.Top.Next.Next = &StackNode{Value: 12}

 fmt.Println("-------- linkStack.Values  --------")
 linkStack.Top.Print()
 fmt.Println("")
 fmt.Println("-------- stack.IsEmpty()  --------")
 fmt.Println(linkStack.IsEmpty())
 fmt.Println("-------- stack.Pop()  --------")
 fmt.Println(linkStack.Pop())
 fmt.Println("-------- stack.Peek()  --------")
 fmt.Println(linkStack.Peek())
 fmt.Println("-------- linkStack.Values  --------")
 linkStack.Top.Print()

执行结果为：

$ go run main.go
-------- linkStack.Values  --------
10 11 12 
-------- stack.IsEmpty()  --------
false
-------- stack.Pop()  --------
10
-------- stack.Peek()  --------
11
-------- linkStack.Values  --------
11 12

其它

简单的实现了，小于10的加减乘除法

package main

import (
 "fmt"
 "strconv"
)

type Stack struct {
 Capacity int
 Top      int
 Values   []string
}

func (s *Stack) Push(val string) bool {
 if s.Top >= s.Capacity {
  fmt.Println("Stack Overflow!")
  return false
 }
 s.Top++
 s.Values[s.Top] = val
 return true
}

func (s *Stack) Pop() string {
 if s.Top < 0 {
  fmt.Println("Stack Underflow!")
  return ""
 }
 result := s.Values[s.Top]
 s.Top--
 return result
}

func (s *Stack) Peek() string {
 if s.Top < 0 {
  fmt.Println("Stack Underflow!")
  return ""
 }
 result := s.Values[s.Top]
 return result
}

func (s *Stack) IsEmpty() bool {
 return s.Top < 0
}

func MainStack() {
 stack := Stack{}
 stack.Capacity = 10
 stack.Top = -1
 stack.Values = make([]string, stack.Capacity)

 stack.Push("10")
 stack.Push("11")
 stack.Push("12")
 fmt.Println("-------- stack.Values  --------")
 fmt.Printf("%+v", stack.Values)
 fmt.Println("")
 fmt.Println("-------- stack.IsEmpty()  --------")
 fmt.Println(stack.IsEmpty())
 fmt.Println("-------- stack.Pop()  --------")
 fmt.Println(stack.Pop())
 fmt.Println("-------- stack.Peek()  --------")
 fmt.Println(stack.Peek())
}

func IsOperator(r rune) bool {
 if r == 42 || r == 43 || r == 45 || r == 47 {
  return true
 } else {
  return false
 }
}

func IsPriorityCalculation(r rune) bool {
 if r == 42 || r == 47 {
  return true
 } else {
  return false
 }
}

func Calculation(strn1, strn2, operator string) string {
 n1, err := strconv.Atoi(strn1)
 if err != nil {
  return ""
 }
 n2, err := strconv.Atoi(strn2)
 if err != nil {
  return ""
 }

 switch operator {
 case "+":
  return strconv.Itoa(n1 + n2)
 case "-":
  return strconv.Itoa(n1 - n2)
 case "*":
  return strconv.Itoa(n1 * n2)
 case "/":
  return strconv.Itoa(n1 / n2)
 }
 return ""
}

func main() {
 numStack := &Stack{}
 numStack.Capacity = 10
 numStack.Top = -1
 numStack.Values = make([]string, numStack.Capacity)

 operatorStack := &Stack{}
 operatorStack.Capacity = 10
 operatorStack.Top = -1
 operatorStack.Values = make([]string, operatorStack.Capacity)

 var str = "9+2*3-7+4/2-9-3"
 var n1, n2, operator string
 for i := 0; i < len(str); i++ {
  if IsOperator(rune(str[i])) {
   if IsPriorityCalculation(rune(str[i])) {
    n1 = numStack.Pop()
    n2 = string(str[i+1])
    n1 = Calculation(n1, n2, string(str[i]))
    numStack.Push(n1)
    i++
   } else {
    operatorStack.Push(string(str[i]))
   }

  } else {
   numStack.Push(string(str[i]))
  }
 }

 fmt.Println(numStack.Values)
 fmt.Println(operatorStack.Values)

 if operatorStack.Top < 0 {
  fmt.Print(numStack.Pop())
  return
 }
 resultNumStack := &Stack{}
 resultNumStack.Capacity = 10
 resultNumStack.Top = -1
 resultNumStack.Values = make([]string, resultNumStack.Capacity)
 for {
  if numStack.Top < 0 {
   break
  }
  resultNumStack.Push(numStack.Pop())
 }
 resultOperatorStack := &Stack{}
 resultOperatorStack.Capacity = 10
 resultOperatorStack.Top = -1
 resultOperatorStack.Values = make([]string, resultNumStack.Capacity)
 for {
  if operatorStack.Top < 0 {
   break
  }
  resultOperatorStack.Push(operatorStack.Pop())
 }

 n1 = resultNumStack.Pop()
 for {
  if resultOperatorStack.Top < 0 {
   fmt.Println(n1)
   break
  }
  operator = resultOperatorStack.Pop()
  n2 = resultNumStack.Pop()
  n1 = Calculation(n1, n2, operator)
 }
}

$ go run main.go
[9 6 7 2 9 3    ]
[+ - + - -     ]
-2

欢迎大家的意见和交流

email: li_mingxie@163.com