Go data structure: stack

Analysis and Implementation of Stack Data Structure in Go

A stack is an ordered collection of items that follow the last in, first out (LIFO) principle. We add and delete items from the same part of the heap (called the top). We cannot delete items from the base. It's like a pile of books.

The stack has many uses, from creating a history of visited pages to entering commands and storing operations that can be undone.

carried out

Internally, the stack will use asliceType, I will expose

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

method.

New()Used as a constructor, it will initialize the internal slice when we start using it.

I will create aItemStackGeneric type, concurrency safety, you can use the following command to generate a stack containing any typegennyTo create a type-specific stack implementation that encapsulates the actual value-specific data structure that contains the data.

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

test

These tests describe the usage of the above implementation.

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

}

Create a specific stack data structure

You can use the following general implementation to generate a type-specific stack by:

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


More tutorials: