Generic structs like a stack

Types can have type parameters too. A good example is a stack: a list where you add items on top and take them off the top, like a pile of plates. The last item you put in is the first one to come out. Stacks show up often in coding interviews, for example to check that brackets are balanced. A stack of ints and a stack of strings work the same way, so one generic type can serve both.

package main

import "fmt"

type Stack[T any] struct {
	items []T
}

func (s *Stack[T]) Push(v T) {
	s.items = append(s.items, v)
}

func (s *Stack[T]) Peek() (T, bool) {
	if len(s.items) == 0 {
		var zero T
		return zero, false
	}
	return s.items[len(s.items)-1], true
}

func (s *Stack[T]) Len() int {
	return len(s.items)
}

func main() {
	var nums Stack[int]
	nums.Push(1)
	nums.Push(2)
	top, ok := nums.Peek()
	fmt.Println(top, ok, nums.Len())

	var words Stack[string]
	w, ok := words.Peek()
	fmt.Println(w == "", ok, words.Len())
}

Output:

2 true 2
true false 0

type Stack[T any] struct declares a generic struct type. Its field items is a slice of T. The stack keeps its items in this slice, and the top of the stack is the end of the slice.

The methods write the receiver as *Stack[T], with the type parameter. They use pointer receivers because Push changes the stack.

Peek returns the top item without removing it. On an empty stack there is no item to return, so it returns false as its second value, like the comma-ok form from the Type Switches lesson. It still has to return some T, and var zero T gives the zero value of whatever T is: 0 for an int, "" for a string.

To make a stack, you must say what T is: Stack[int] or Stack[string]. A stack's zero value is ready to use, because append works on an empty slice.

Type safety

nums only accepts ints. Pushing a string is a compile error:

package main

import "fmt"

type Stack[T any] struct {
	items []T
}

func (s *Stack[T]) Push(v T) {
	s.items = append(s.items, v)
}

func main() {
	var nums Stack[int]
	nums.Push(1)
	nums.Push("oops")
	fmt.Println(nums.items)
}

Output:

# command-line-arguments
./main.go:16:12: cannot use "oops" (untyped string constant) as int value in argument to nums.Push

You could also build a stack on []any, which accepts every type. Then the same mistake compiles, and every value you take out needs a type assertion:

package main

import "fmt"

type AnyStack struct {
	items []any
}

func (s *AnyStack) Push(v any) {
	s.items = append(s.items, v)
}

func (s *AnyStack) Pop() any {
	last := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return last
}

func main() {
	var nums AnyStack
	nums.Push(1)
	nums.Push("oops")
	n := nums.Pop().(int)
	fmt.Println(n + 1)
}

Output:

panic: interface conversion: interface {} is string, not int

The mistake is only found when the program runs, and it crashes. The generic Stack[int] catches it before the program runs, and you never need an assertion.

More than one type parameter

A type can have several type parameters. Pair holds a key and a value of two different types:

package main

import "fmt"

type Pair[K comparable, V any] struct {
	Key   K
	Value V
}

func main() {
	p := Pair[string, int]{Key: "Alice", Value: 90}
	fmt.Printf("%+v\n", p)
	q := Pair[int, bool]{Key: 7, Value: true}
	fmt.Printf("%+v\n", q)
}

Output:

{Key:Alice Value:90}
{Key:7 Value:true}

comparable is a constraint built into Go. It allows only types that work with ==, the same types that can be map keys. A key should be comparable, so K uses it, while the value can be anything.

In the exercise, finish Push and Pop for the generic Stack, then use it to make a stack of ints and a stack of strings.