pelaksanaan timbunan golang

Golang ialah bahasa pengaturcaraan yang cekap, berskala dan serentak yang digunakan secara meluas dan dihormati dalam industri Internet. Bagi pembangun Golang, struktur data dan algoritma adalah salah satu kemahiran asas, dan pelaksanaan tindanan adalah bahagian penting. Dalam artikel ini, kami akan mendalami cara melaksanakan tindanan di Golang.

1. Apakah tindanan?

Timbunan ialah struktur linear khas yang hanya boleh dikendalikan pada satu hujung, iaitu elemen hanya boleh dimasukkan dan dipadamkan di bahagian atas tindanan. Oleh itu, kaedah capaian data timbunan ialah "masuk dahulu, keluar terakhir". Ia adalah struktur data yang sesuai untuk banyak keadaan, seperti caching, penilaian ekspresi, panggilan fungsi, dll.

Operasi tindanan yang biasa digunakan termasuk tolak dan pop Apabila menolak, elemen baharu sentiasa diletakkan di bahagian atas tindanan, bahagian atas tindanan sentiasa dipadamkan akan terus berubah.

2. Cara melaksanakan tindanan

Terdapat dua cara untuk melaksanakan tindanan dalam Golang: satu adalah menggunakan Slice, satu lagi adalah menggunakan Senarai Berpaut ).

2.1 Pelaksanaan Slice

Apabila menggunakan kepingan untuk melaksanakan tindanan, struktur tindanan kami hanya perlu mengandungi satu kepingan. Berikut ialah contoh ringkas timbunan pelaksanaan kepingan:

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
}

Dalam pelaksanaan, kita mula-mula mentakrifkan struktur Stack yang mengandungi kepingan data. Push()Fungsi menolak elemen ke bahagian atas tindanan dan menambah elemen pada hujung hirisan secara bergilir-gilir Pop()Fungsi ini mengeluarkan elemen dari bahagian atas tindanan dengan mendapatkan elemen terakhir dalam hirisan dan kemudian mengeluarkan unsur tersebut; elemen daripada hirisan; IsEmpty()Fungsi menentukan sama ada tindanan itu kosong.

2.2 Pelaksanaan senarai terpaut

Logik asas timbunan pelaksanaan senarai terpaut ialah menggunakan kepala senarai terpaut sebagai bahagian atas timbunan Setiap kali elemen dimasukkan, ia diletakkan di kepala, dan setiap kali elemen muncul, ia diletakkan di kepala Elemen pengepala dipadamkan. Berikut ialah contoh timbunan pelaksanaan senarai terpaut:

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
}

Dalam pelaksanaan, kami mula-mula mentakrifkan struktur node untuk mewakili setiap nod senarai terpaut. Setiap nod mengandungi elemen val dan penunjuk ke nod seterusnya next. Kemudian kami mentakrifkan struktur Stack untuk mewakili tindanan, dengan penunjuk head menghala ke elemen atas tindanan; mula-mula memperoleh nilai dalam nod kepala, dan kemudian Halakan penuding kepala ke nod seterusnya untuk melaksanakan operasi pop; Push()Pop()IsEmpty()Menggunakan Tindanan

3. Fungsi yang disediakan oleh tindanan ialah cara untuk meningkatkan pemprosesan masalah yang kompleks. Masalah seperti penilaian ekspresi dan pemadanan kurungan boleh diselesaikan dengan baik menggunakan tindanan. Berikut ialah contoh kod penilaian ungkapan yang dilaksanakan menggunakan penghirisan:

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
}

Dalam penilaian ungkapan, kami menggunakan idea timbunan untuk memproses ungkapan Poland terbalik. Mula-mula bahagikan ungkapan dengan ruang, dan kemudian proses setiap bahagian. Jika ia adalah pengendali (+ - * /), dua elemen di bahagian atas tindanan dikeluarkan, operasi yang sepadan dilakukan, dan hasilnya ditolak ke tindanan, jika ia adalah operan, ia ditolak ke atas timbunan secara langsung. Akhir sekali, jika tindanan tidak kosong, nilai di bahagian atas tindanan dikembalikan sebagai hasil daripada operasi.

Ringkasan

4. Timbunan ialah struktur data yang sangat praktikal yang digunakan secara meluas dalam banyak situasi. Terdapat banyak cara untuk melaksanakan tindanan menggunakan Golang Artikel ini terutamanya memperkenalkan dua kaedah pelaksanaan: kepingan dan senarai terpaut. Pelaksanaan penghirisan adalah mudah dan mudah difahami, tetapi apabila elemen mencapai saiz yang besar, kecekapan peruntukan memori akan berkurangan pelaksanaan peruntukan memori senarai terpaut adalah lebih fleksibel, tetapi kerumitan kod juga meningkat; Pemilihan kaedah pelaksanaan yang munasabah boleh mengelakkan pembaziran sumber yang tidak perlu dalam aplikasi praktikal dan meningkatkan kecekapan pelaksanaan program.

Atas ialah kandungan terperinci pelaksanaan timbunan golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!