首頁 > 後端開發 > Golang > 主體

golang堆疊實現

王林
發布: 2023-05-16 11:06:37
原創
739 人瀏覽過

Golang是一種高效能、可擴展且並發性強的程式語言,在網路產業中被廣泛使用和推崇。對於Golang的開發者來說,資料結構和演算法是基本功之一,而其中棧(Stack)的實作是不可或缺的一部分。在本文中,我們將深入探討如何在Golang中實作堆疊。

  1. 什麼是堆疊?

堆疊是一種特殊的線性結構,它只能在一端進行操作,也就是只能在堆疊頂部進行元素的插入和刪除。因此,棧的資料存取方式是「先進後出」。它是一個適用於多種場合的資料結構,如快取、表達式求值、函數呼叫等。

常用的堆疊操作有入棧(push)和出棧(pop)兩種操作,入棧時,新的元素總是放在棧頂位置;出棧時,總是刪除棧頂元素,因此堆疊的長度會不斷的變化。

  1. 堆疊的實作方式

在Golang中實作堆疊有兩種方式:一種是使用切片(Slice),另一種是使用鍊錶(Linked List )。

2.1 切片實作

在使用切片實作堆疊時,我們的堆疊結構體只需要包含一個切片即可。下面是切片實作堆疊的簡單範例:

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
}
登入後複製

在實作中,我們先定義了一個結構體Stack,它包含一個切片dataPush()函數將元素壓入堆疊頂,依序將元素加入切片末端;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()函數判斷堆疊是否為空。

  1. 使用堆疊

堆疊所提供的功能是加強複雜的問題處理的一種方式。對於表達式求值、括號匹配等問題,使用堆疊都能夠得到良好的解決。以下是使用切片實作的表達式求值程式碼範例:

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
}
登入後複製

在表達式求值中,我們使用了堆疊的想法來處理逆波蘭表達式。首先將表達式按照空格分割開來,然後對每一部分進行處理。如果是運算元( - * /),則取出棧頂的兩個元素進行對應的運算,並將結果壓入堆疊中;如果是操作數,則直接將其壓入堆疊中。最後,如果堆疊不為空,則將棧頂的值作為運算結果傳回。

  1. 總結

堆疊是一種非常實用的資料結構,它在許多場合都有著廣泛的應用。使用Golang實作堆疊的方法有很多種,本文主要介紹了切片和鍊錶兩種實作方式。切片的實作方式簡單易懂,但當元素達到較大規模時,會導致記憶體分配的效率下降;鍊錶的實作方式記憶體分配更加靈活,但程式碼的複雜度也有所增加。合理選擇實現方式可以在實際應用中避免浪費不必要的資源,並提高程式的執行效率。

以上是golang堆疊實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板