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:


Online technical encyclopedia!