Go Data Structures: Stack

A stack is an ordered collection of items following the Last-In-First-Out (LIFO) principle. We add and remove items from the same part of the pile, called the top. We cannot remove items from the base. Just like a pile of books.

Stacks have tons of uses, from creating a history of pages visited to commands entered and to store actions that can be undone.

Implementation

Internally the stack will be represented with a slice type, and I’ll expose the

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

methods.

New() serves as the constructor, which initializes the internal slice when we start using it.

I’ll create an ItemStack generic type, concurrency safe, that can generate stacks containing any type by using genny, to create a type-specific stack implementation, encapsulating the actual value-specific data structure containing the data.

// Package stack creates a ItemStack data structure for the Item type
package stack

import (
    "sync"

    "github.com/cheekybits/genny/generic"
)

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

Tests

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

    s.Pop()
    s.Pop()
    if size := len(s.items); size != 0 {
        t.Errorf("wrong count, expected 0 and got %d", size)
    }
}

Creating a concrete stack data structure

You can use this generic implemenation to generate type-specific stacks, using

//generate a `IntStack` stack of `int` values
genny -in stack.go -out stack-int.go gen "Item=int"

//generate a `StringStack` stack of `string` values
genny -in stack.go -out stack-string.go gen "Item=string"