Golang-Stack-Implementierung-Golang-php.cn

Golang-Stack-Implementierung

王林

Freigeben： 2023-05-16 11:06:37

Original

722 Leute haben es durchsucht

Golang ist eine effiziente, skalierbare und gleichzeitige Programmiersprache, die in der Internetbranche weit verbreitet und anerkannt ist. Für Golang-Entwickler gehören Datenstrukturen und Algorithmen zu den Grundkenntnissen und die Implementierung des Stacks ist ein wesentlicher Bestandteil. In diesem Artikel werden wir uns eingehend mit der Implementierung eines Stacks in Golang befassen.

Was ist ein Stapel?

Der Stapel ist eine spezielle lineare Struktur, die nur an einem Ende bedient werden kann, dh Elemente können nur oben im Stapel eingefügt und gelöscht werden. Daher lautet die Datenzugriffsmethode des Stapels „First In, Last Out“. Es handelt sich um eine Datenstruktur, die für viele Gelegenheiten geeignet ist, z. B. Caching, Ausdrucksauswertung, Funktionsaufruf usw.

Zu den häufig verwendeten Stapeloperationen gehören Push und Pop. Beim Push wird das neue Element immer oben auf dem Stapel platziert. Beim Popen wird das oberste Element immer gelöscht, sodass sich die Länge des Stapels weiter ändert.

So implementieren Sie den Stack

Es gibt zwei Möglichkeiten, den Stack in Golang zu implementieren: Eine besteht darin, Slice zu verwenden, und die andere darin, Linked List zu verwenden.

2.1 Slice-Implementierung

Wenn Sie Slices zum Implementieren eines Stapels verwenden, muss unsere Stapelstruktur nur ein Slice enthalten. Das Folgende ist ein einfaches Beispiel eines Slice-Implementierungsstapels:

type Stack struct {
  data []interface{}
}

func (s *Stack) Push(val interface{}) {
    s.data = append(s.data, val)
}

func (s *Stack) Pop() interface{} {
    if s.IsEmpty() {
        return nil
    }
    last := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return last
}

func (s *Stack) IsEmpty() bool {
    return len(s.data) == 0
}

Nach dem Login kopieren

In der Implementierung definieren wir zunächst eine Struktur Stack, die einen Slice data enthält. Die Funktion Push() schiebt Elemente oben auf den Stapel und fügt Elemente am Ende des Slice hinzu. Die Funktion Pop() fügt Elemente von oben ein Der Stapel wird ermittelt, indem das letzte Element im Slice abgerufen wird. Die Funktion IsEmpty() bestimmt, ob der Stapel leer ist. Stack，它包含一个切片data。Push()函数将元素压入栈顶，依次将元素添加到切片末尾；Pop()函数将元素从栈顶弹出，通过获取切片中的最后一个元素，然后将该元素从切片中删除；IsEmpty()函数判断栈是否为空。

2.2 链表实现

链表实现栈的基本逻辑是使用链表的头部作为栈顶，每插入一个元素，就将其放在头部，每弹出一个元素就将头部的元素删除。下面是链表实现栈的示例：

type node struct {
  val  interface{}
  next *node
}

type Stack struct {
  head *node
}

func (s *Stack) Push(val interface{}) {
  s.head = &node{val, s.head}
}

func (s *Stack) Pop() interface{} {
  if s.head == nil {
    return nil
  }
  val := s.head.val
  s.head = s.head.next
  return val
}

func (s *Stack) IsEmpty() bool {
  return s.head == nil
}

Nach dem Login kopieren

在实现中，我们首先定义一个结构体node表示链表的每一个节点。每个节点都包含一个元素val，和一个指向下一个节点的指针next。然后我们定义结构体Stack表示栈，其中head指针指向栈顶元素；Push()函数依次将元素插入到链表头部；Pop()函数通过先获取头部节点中的值，然后再将头部指针指向下一个节点实现弹出操作；IsEmpty()

2.2 Implementierung einer verknüpften Liste

Die Grundlogik des Implementierungsstapels für verknüpfte Listen besteht darin, den Kopf der verknüpften Liste als obersten Teil des Stapels zu verwenden. Jedes Mal, wenn ein Element eingefügt wird, wird es an der Spitze platziert, und jedes Mal, wenn ein Element wird herausgesprungen, das Element an der Spitze wird gelöscht. Das Folgende ist ein Beispiel für einen Implementierungsstapel für verknüpfte Listen:

func EvaluateExpression(expression string) (float64, error) {
  stack := Stack{}
  tokens := strings.Split(expression, " ")
  for _, token := range tokens {
    switch token {
      case "+", "-", "*", "/":
        if stack.IsEmpty() {
          return 0, errors.New("Invalid expression")
        }
        b, err := stack.Pop().(float64)
        if !err {
          return 0, errors.New("Invalid expression")
        }
        if stack.IsEmpty() {
          return 0, errors.New("Invalid expression")
        }
        a, err := stack.Pop().(float64)
        if !err {
          return 0, errors.New("Invalid expression")
        }
        var result float64
        switch token {
          case "+":
            result = a + b
          case "-":
            result = a - b
          case "*":
            result = a * b
          case "/":
            result = a / b
        }
        stack.Push(result)
      default:
        num, err := strconv.ParseFloat(token, 64)
        if err != nil {
          return 0, errors.New("Invalid expression")
        }
        stack.Push(num)
    }
  }
  if stack.IsEmpty() {
    return 0, errors.New("Invalid expression")
  }
  result, err := stack.Pop().(float64)
  if !err || !stack.IsEmpty() {
    return 0, errors.New("Invalid expression")
  }
  return result, nil
}

Nach dem Login kopieren

node

val

next

Stack

head

Pop()

IsEmpty()

Verwenden Sie den Stack

Die vom Stack bereitgestellten Funktionen sind eine Möglichkeit, die Bearbeitung komplexer Probleme zu verbessern. Probleme wie Ausdrucksauswertung und Klammerabgleich können mit dem Stack gut gelöst werden. Das Folgende ist ein Beispiel für Ausdrucksauswertungscode, der mithilfe von Slicing implementiert wurde:

Das obige ist der detaillierte Inhalt vonGolang-Stack-Implementierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!