golang スタックの実装

Golang は、インターネット業界で広く使用され、評価されている、効率的でスケーラブルな同時実行性の高いプログラミング言語です。 Golang 開発者にとって、データ構造とアルゴリズムは基本スキルの 1 つであり、スタックの実装は不可欠な部分です。この記事では、Golang でスタックを実装する方法について詳しく説明します。

1. スタックとは何ですか?

スタックは、一方の端でのみ操作できる特殊な線形構造です。つまり、要素はスタックの最上部でのみ挿入および削除できます。したがって、スタックのデータ アクセス方法は「先入れ後出し」です。キャッシュ、式の評価、関数呼び出しなど、さまざまな場面に適したデータ構造です。

一般的に使用されるスタック操作には、プッシュとポップが含まれます。プッシュする場合、新しい要素は常にスタックの先頭に配置され、ポップする場合、スタックの先頭は常に削除されます。要素なので、スタックの長さは変化し続けます。

2. スタックの実装方法

Golang でスタックを実装するには 2 つの方法があります。1 つはスライスを使用する方法、もう 1 つはリンク リストを使用する方法です。) 。

2.1 スライスの実装

スライスを使用してスタックを実装する場合、スタック構造に含まれる必要があるのはスライス 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
}

実装では、まず、スライス data を含む構造体 Stack を定義します。 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. スタックの使用

スタックによって提供される関数は、複雑な問題の処理を強化する方法です。式の評価や括弧の一致などの問題は、スタックを使用するとうまく解決できます。以下は、スライスを使用して実装された式評価コードの例です。

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
}

式評価では、スタックの概念を使用して逆ポーランド式を処理します。まず式をスペースで分割し、各部分を処理します。演算子 (- * /) の場合は、スタックの先頭にある 2 つの要素が取り出され、対応する演算が実行され、結果がスタックにプッシュされます。オペランドの場合は、スタックにプッシュされます。直接スタックします。最後に、スタックが空でない場合は、スタックの先頭の値が操作の結果として返されます。

4. 概要

スタックは、多くの状況で広く使用される非常に実用的なデータ構造です。 Golangを使ったスタックの実装方法は数多くありますが、本記事では主にスライスとリンクリストの2つの実装方法を紹介します。スライスの実装はシンプルで理解しやすいですが、要素のサイズが大きくなるとメモリ割り当ての効率が低下します。リンク リストのメモリ割り当ての実装はより柔軟ですが、コードの複雑さも増加します。実装方法を合理的に選択すると、実際のアプリケーションでリソースの不必要な浪費を回避し、プログラムの実行効率を向上させることができます。

以上がgolang スタックの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。