Truy cập cấu trúc dữ liệu: Ngăn xếp

Phân tích và triển khai cấu trúc dữ liệu Stack trong Go

Ngăn xếp là một tập hợp các mục có thứ tự tuân theo nguyên tắc Cuối cùng vào Đầu ra (LIFO). Chúng tôi thêm và xóa các mục từ cùng một phần của đống, được gọi là phần trên cùng. Chúng tôi không thể loại bỏ các mục khỏi cơ sở. Cũng giống như một đống sách.

Ngăn xếp có rất nhiều cách sử dụng, từ tạo lịch sử các trang đã truy cập đến các lệnh đã nhập và lưu trữ các hành động có thể hoàn tác.

Thực hiện

Bên trong ngăn xếp sẽ được biểu diễn bằng mộtslicegõ, và tôi sẽ hiển thị

  • Push()
  • Pull()
  • New()

các phương pháp.

New()đóng vai trò là phương thức khởi tạo, khởi tạo lát bên trong khi chúng ta bắt đầu sử dụng nó.

Tôi sẽ tạo mộtItemStackloại chung, an toàn đồng thời, có thể tạo ngăn xếp chứa bất kỳ loại nào bằng cách sử dụnggenny, để tạo một triển khai ngăn xếp kiểu cụ thể, đóng gói cấu trúc dữ liệu giá trị cụ thể thực tế có chứa dữ liệu.

// 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 }

Kiểm tra

Các bài kiểm tra mô tả việc sử dụng triển khai trên.

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>)
}

}

Tạo cấu trúc dữ liệu ngăn xếp cụ thể

Bạn có thể sử dụng cách áp dụng chung này để tạo các ngăn xếp loại cụ thể, bằng cách sử dụng

//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”


Các hướng dẫn về go khác: