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"
More go tutorials:
- Using NGINX Reverse Proxy to serve Go services
- Making a copy of a struct in Go
- The basics of a Go Web Server
- Sorting a map type in Go
- Go pointers in a nutshell
- Go Tags explained
- Go Date and Time Formatting
- JSON processing with Go
- Go Variadic Functions
- Go Strings Cheat Sheet
- The Go Empty Interface Explained
- Debugging Go with VS Code and Delve
- Named Go returns parameters
- Generating random numbers and strings in Go
- Filesystem Structure of a Go project
- Binary Search Algorithm Implemented in Go
- Using Command Line Flags in Go
- GOPATH Explained
- Build a Command Line app with Go: lolcat
- Building a CLI command with Go: cowsay
- Using Shell Pipes with Go
- Go CLI tutorial: fortune clone
- List the files in a folder with Go
- Use Go to get a list of repositories from GitHub
- Go, append a slice of strings to a file
- Go, convert a string to a bytes slice
- Visualize your local Git contributions with Go
- Getting started with Go CPU and memory profiling
- Solving the "does not support indexing" error in a Go program
- Measuring execution time in a Go program
- Building a Web Crawler with Go to detect duplicate titles
- Go Best Practices: Pointer or value receivers?
- Go Best Practices: Should you use a method or a function?
- Go Data Structures: Set
- Go Maps Cheat Sheet
- Generate implementations for generic types in Go
- Go Data Structures: Dictionary
- Go Data Structures: Hash Table
- Implement Events Listeners in Go through Channels
- Go Data Structures: Stack
- Go Data Structures: Queue
- Go Data Structures: Binary Search Tree
- Go Data Structures: Graph
- Go Data Structures: Linked List
- The complete guide to Go Data Structures
- Comparing Go Values
- Is Go object oriented?
- Working with a SQL Database in Go
- Using environment variables in Go
- Go tutorial: REST API backed by PostgreSQL
- Enabling CORS on a Go Web Server
- Deploying a Go Application in a Docker Container
- Why Go is a powerful language to learn as a PHP developer
- Go, remove the io.Reader.ReadString newline char
- Go, how to watch changes and rebuild your program
- Go, count the months since a date
- Accessing HTTP POST parameters in Go