This article gives a brief introduction of implementing stacks in Go language.
We will be doing the 3 basic operations related to stacks:
Push
: Inserts an element to the top of the stack
Pop
: Removes an element from the top of the stack, throws a runtime error in case of an empty stack
Top
: Returns the top element of the stack, throws a runtime error in case of an empty stack
Utility functions:
IsEmpty
: Returns a boolean to denote whether the stack is empty
After defining the operations, let's define the interface for a stack.
Note: The example uses int
data type.
type IStack interface {
Push(val int)
Pop()
Top() int
IsEmpty() bool
}
After defining the interface, the next step is to define a struct
which implements the
above interface and can be used as a stack
in different functions.
type Stack struct {}
Now, we will decide on which field to add in the above struct. As this code uses int
stack as example, we will use a slice of int
.
type Stack struct {
elems []int
}
Now that the struct
is defined, we will define all the methods associated with it.
First comes the Push
method.
func (s *Stack) Push(val int) {
s.elems = append(s.elems,val)
}
Next comes the Pop
method.
func (s *Stack) Pop() {
if s.IsEmpty() {
//panics when there is no top element to pop
panic("Cannot remove element from empty stack")
}
s.elems = s.elems[:len(s.elems)-1]
}
Following it with the Top
method.
func (s *Stack) Top() int {
if s.IsEmpty() {
//panics when there is no top element to return
panic("cannot reference top element of empty stack")
}
return s.elems[len(s.elems)-1]
}
And lastly, the IsEmpty
method.
func (s *Stack) IsEmpty() bool {
return len(s.elems) == 0
}
With this, all the methods are defined and our struct is an implementation of the stack interface. Now, let's start with a function that will take care of the initializations and return an implementation of the stack.
func NewStack() IStack {
return &Stack{
elems: make([]int,0) // creates an empty slice of integers
}
}
Example:
func main(){
s := NewStack()
s.Push(1)
fmt.Println(s.Top()) //prints 1
s.Pop()
fmt.Println(s.Top()) //panics
}
Feel free to try out this question on leetcode.com.