Goでのスタックデータ構造の分析と実装
スタックは、後入れ先出し(LIFO)の原則に従った順序付けられたアイテムのコレクションです。トップと呼ばれるパイルの同じ部分にアイテムを追加および削除します。ベースからアイテムを削除することはできません。本の山のように。
スタックには、アクセスしたページの履歴の作成から、入力したコマンドの作成、元に戻すことができるアクションの保存まで、さまざまな用途があります。
実装
内部的には、スタックはで表されますslice
タイプ、そして私は公開します
Push()
Pull()
New()
メソッド。
New()
コンストラクターとして機能し、使用を開始すると内部スライスを初期化します。
作成しますItemStack
ジェネリック型、並行性セーフ、を使用して任意の型を含むスタックを生成できますgenny
、タイプ固有のスタック実装を作成し、データを含む実際の値固有のデータ構造をカプセル化します。
// Package stack creates a ItemStack data structure for the Item type
package stack
import (
“sync”
<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>
)
// Item the type of the stack
type Item generic.Type
// ItemStack the stack of Items
type ItemStack struct {
items []Item
lock sync.RWMutex
}
// New creates a new ItemStack
func (s ItemStack) New() ItemStack {
s.items = []Item{}
return s
}
// Push adds an Item to the top of the stack
func (s *ItemStack) Push(t Item) {
s.lock.Lock()
s.items = append(s.items, t)
s.lock.Unlock()
}
// Pop removes an Item from the top of the stack
func (s ItemStack) Pop() Item {
s.lock.Lock()
item := s.items[len(s.items)-1]
s.items = s.items[0 : len(s.items)-1]
s.lock.Unlock()
return &item
}
テスト
テストでは、上記の実装の使用法について説明します。
package stack
import (
“testing”
)
var s ItemStack
func initStack() *ItemStack {
if s.items == nil {
s = ItemStack{}
s.New()
}
return &s
}
func TestPush(t *testing.T) {
s := initStack()
s.Push(1)
s.Push(2)
s.Push(3)
if size := len(s.items); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
}
func TestPop(t *testing.T) {
s.Pop()
if size := len(s.items); size != 2 {
t.Errorf(“wrong count, expected 2 and got %d”, size)
}
<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Pop</span>()
<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Pop</span>()
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> len(<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">items</span>); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">0</span> {
<span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 0 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}
}
具体的なスタックデータ構造の作成
この一般的な実装を使用して、を使用してタイプ固有のスタックを生成できます。
//generate a `IntStack` stack of `int` values
genny -in stack.go -out stack-int.go gen "Item=int"
//generate a </span>StringStack<span style="color:#e6db74">
stack of </span>string<span style="color:#e6db74">
values
genny -in stack.go -out stack-string.go gen “Item=string”
その他のチュートリアル:
- NGINXリバースプロキシを使用してGoサービスを提供する
- Goで構造体のコピーを作成する
- GoWebサーバーの基本
- Goでのマップタイプの並べ替え
- 一言で言えばポインタを移動します
- タグの説明に行く
- 日付と時刻のフォーマットに移動
- Goを使用したJSON処理
- 可変個引数関数に移動
- GoStringsチートシート
- GoEmptyインターフェイスの説明
- Go withVSCodeとDelveのデバッグ
- NamedGoはパラメータを返します
- Goで乱数と文字列を生成する
- Goプロジェクトのファイルシステム構造
- Goに実装された二分探索アルゴリズム
- Goでのコマンドラインフラグの使用
- GOPATHの説明
- Goでコマンドラインアプリを作成する:lolcat
- Goを使用したCLIコマンドの作成:cowsay
- Goでのシェルパイプの使用
- CLIチュートリアルに移動:フォーチュンクローン
- Goを使用してフォルダ内のファイルを一覧表示します
- Goを使用して、GitHubからリポジトリのリストを取得します
- 移動し、文字列のスライスをファイルに追加します
- 文字列をバイトスライスに変換します
- GoでローカルGitの貢献を視覚化する
- GoCPUとメモリプロファイリングの開始
- Goプログラムの「インデックス作成をサポートしていません」エラーを解決する
- Goプログラムでの実行時間の測定
- 重複するタイトルを検出するためにGoを使用してWebクローラーを構築する
- ベストプラクティスに進む:ポインターまたは値のレシーバー?
- ベストプラクティスに進む:メソッドまたは関数を使用する必要がありますか?
- データ構造の移動:設定
- マップのチートシートに移動
- Goでジェネリック型の実装を生成する
- Goデータ構造:辞書
- Goデータ構造:ハッシュテーブル
- Go throughChannelsにイベントリスナーを実装する
- Goデータ構造:スタック
- データ構造の移動:キュー
- Goデータ構造:二分探索木
- Goデータ構造:グラフ
- Goデータ構造:リンクリスト
- Goデータ構造の完全ガイド
- Go値の比較
- Goはオブジェクト指向ですか?
- GoでのSQLデータベースの操作
- Goでの環境変数の使用
- チュートリアルに進む:PostgreSQLに裏打ちされたREST API
- GoWebサーバーでのCORSの有効化
- DockerコンテナへのGoアプリケーションのデプロイ
- GoがPHP開発者として学ぶための強力な言語である理由
- 移動し、io.Reader.ReadString改行文字を削除します
- 移動、変更を監視してプログラムを再構築する方法
- 行って、日付からの月を数えます
- GoでHTTPPOSTパラメーターにアクセスする