Go Data Structures: Stack

تحليل وتنفيذ بنية بيانات Stack في Go

المكدس عبارة عن مجموعة مرتبة من العناصر تتبع مبدأ Last-In-First-Out (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”


المزيد من دروس Go: