Implementing a Stack in Go
💡 Stack
A stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).
Stacks are used when you want to have access to elements in a Last-In-First-Out manner (LIFO). They're commonly used in scenarios like keeping track of memory during a recursive function call, undo operations in text editors, or in tree/graph traversal algorithms like depth-first-search.
👨🏫 Refer my previous post about Data structures, if you are new to Data structures.
Overview
STACK
- 📦 items: STACK (items)
- 🚦 methods: PUSH (T), POP, PEEK, LENGTH, TRAVERSE
- ⚡️ extra: PUSH-BOTTOM, POP-BOTTOM, PEEK-BOTTOM, REVERSE
⭐️ In here, we use Go Generics and any data type. You don’t need to have a prior knowledge of Go Generics syntaxes as this is a good example of usage of Generics and a good opportunity to get familiarize with Go Generics syntaxes.
Let’s get started.
Implementation
Stack
type Stack[T any] struct {
items []T
}Factory
func New[T any]() *Stack[T] {
return &Stack[T]{}
}Push
func (s *Stack[T]) Push(v T) {
s.items = append(s.items, v)
}Pop
func (s *Stack[T]) Pop() (T, error) {
l := len(s.items)
var v T
if l == 0 {
return v, ErrEmptyStack
}
v = s.items[l-1]
s.items = s.items[:l-1]
return v, nil
}
var ErrEmptyStack = errors.New("empty stack")Peek
func (s *Stack[T]) Peek() (T, error) {
l := len(s.items)
var v T
if l == 0 {
return v, ErrEmptyStack
}
return s.items[l-1], nil
}
// var ErrEmptyStack = errors.New("empty stack")Length and Traverse
func (s *Stack[T]) Length() int {
return len(s.items)
}
func (s *Stack[T]) String() (str string) {
l := len(s.items)
if l == 0 {
return
}
for l > 0 {
str = fmt.Sprintf("%s%v\n", str, s.items[l-1])
l--
}
return
}⚡️ Let’s see how to implement extra functionalities which are not directly related to this data structure.
Push Bottom
func (s *Stack[T]) PushBottom(v T) {
s.items = append([]T{v}, s.items...)
}👨🏫 Check the drawbacks of this Implementation
Pop Bottom
func (s *Stack[T]) PopBottom() (T, error) {
var v T
if len(s.items) == 0 {
return v, ErrEmptyStack
}
v = s.items[0]
s.items = s.items[1:]
return v, nil
}
// var ErrEmptyStack = errors.New("empty stack")Peek Bottom
func (s *Stack[T]) PeekBottom() (T, error) {
var v T
if len(s.items) == 0 {
return v, ErrEmptyStack
}
return s.items[0], nil
}
// var ErrEmptyStack = errors.New("empty stack")Reverse
func (s *Stack[T]) Reverse() {
l := len(s.items)
if l < 2 {
return
}
for x, y := 0, l-1; x < y; x, y = x+1, y-1 {
s.items[x], s.items[y] = s.items[y], s.items[x]
}
}⭐️ To practice further, add following new methods to the stack
HAS : to verify the value already exists in the stack
REMOVE: to remove the value if exists in the stack
Refer singly linked list data structure and implement a stack using it.
