Golang-Stack-Implementierung

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.

1. 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.

2. 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 }

In der Implementierung definieren wir zunächst eine StrukturStack, die einen Slicedataenthält. Die FunktionPush()schiebt Elemente oben auf den Stapel und fügt Elemente am Ende des Slice hinzu. Die FunktionPop()fügt Elemente von oben ein Der Stapel wird ermittelt, indem das letzte Element im Slice abgerufen wird. Die FunktionIsEmpty()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 }

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

3. 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
In der Implementierung definieren wir zunächst eine Struktur node, um jeden Knoten der verknüpften Liste darzustellen. Jeder Knoten enthält ein Element valund einen Zeiger auf den nächsten Knoten next. Dann definieren wir die Struktur Stack, um den Stapel darzustellen, wobei der head-Zeiger auf das oberste Element des Stapels zeigt; fügt der Reihe nach Elemente in den Kopf der verknüpften Liste ein. Die Funktion Pop()realisiert die Pop-Operation, indem sie zuerst den Wert im Kopfknoten abruft und dann den Kopfzeiger auf den nächsten Knoten zeigt. Die Funktion IsEmpty()bestimmt, ob der Stapel leer ist.

Verwenden Sie den Stack

4. 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:
rrreee
Bei der Ausdrucksauswertung verwenden wir die Idee des Stapels, um umgekehrte polnische Ausdrücke zu verarbeiten. Teilen Sie den Ausdruck zunächst durch Leerzeichen auf und verarbeiten Sie dann jeden Teil. Wenn es sich um einen Operator (+ - */) handelt, werden die beiden Elemente oben im Stapel herausgenommen, die entsprechende Operation ausgeführt und das Ergebnis auf den Stapel verschoben direkt auf den Stapel. Wenn der Stapel schließlich nicht leer ist, wird als Ergebnis der Operation der Wert oben im Stapel zurückgegeben.
ZusammenfassungStack ist eine sehr praktische Datenstruktur, die in vielen Situationen ein breites Anwendungsspektrum bietet. Es gibt viele Möglichkeiten, Stapel mit Golang zu implementieren. In diesem Artikel werden hauptsächlich zwei Implementierungsmethoden vorgestellt: Slices und verknüpfte Listen. Die Implementierung des Slicing ist einfach und leicht zu verstehen, aber wenn die Elemente eine große Größe erreichen, nimmt die Effizienz der Speicherzuweisung ab. Die Implementierung der Speicherzuweisung für verknüpfte Listen ist flexibler, aber auch die Komplexität des Codes nimmt zu. Eine angemessene Auswahl von Implementierungsmethoden kann unnötige Ressourcenverschwendung in praktischen Anwendungen vermeiden und die Effizienz der Programmausführung verbessern.

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