In this post I will be teaching how to implement your own stack data structure in golang from scratch.
If you would prefer the video format then follow the link below.
Here is the code
type StackIface interface {
Empty() bool
Top() byte
Pop() bool
Push(b byte)
}
type Stack []byte
func (s *Stack) Empty() bool {
return s == nil || len(*s) == 0
}
func (s *Stack) Top() byte {
// CAUTION! we are not handling those cases where stack is empty
// to be handled by caller
if s == nil {
// handle ?
}
ss := []byte(*s)
return ss[len(ss) - 1]
}
func (s *Stack) Pop() bool {
if s.Empty() {
return false
}
ss := []byte(*s)
ss = ss[0:len(ss) - 1]
*s = Stack(ss)
return true
}
func (s *Stack) Push(b byte) {
ss := []byte(*s)
ss = append(ss, b)
*s = Stack(ss)
}
func isValid(s string) bool {
brackets := []string{"()", "{}", "[]"} // can add more such pairs if needed
counter, opening := make(map[byte]byte), make(map[byte]bool)
for _, bracket := range brackets {
counter[bracket[1]] = bracket[0]
opening[bracket[0]] = true
}
var stack Stack
for _, r := range s {
c := byte(r)
if opening[c] {
stack.Push(c)
} else {
// stack keeps track of opening brackets which need to be popped out
if !stack.Empty() && stack.Top() == counter[c] {
stack.Pop()
} else {
return false
}
}
}
return stack.Empty()
}
StackIface Interface:
Declares an interface StackIface with four methods: Empty() bool, Top() byte, Pop() bool, and Push(b byte).
Stack Type:
Defines a type Stack as a slice of bytes.
The methods of the StackIface interface are implemented for the Stack type.
Empty() Method:
Checks if the stack is empty.
Returns true if the stack is either nil or has a length of 0.
Top() Method:
Retrieves the top element of the stack.
Note: The code contains a cautionary comment, indicating that it doesn't handle cases where the stack is empty. This responsibility is left to the caller.
Pop() Method:
Removes the top element from the stack.
Returns false if the stack is empty; otherwise, it pops the top element.
Push() Method:
Adds a byte to the top of the stack.
isValid() Function:
Takes a string s as input and checks whether the string has valid bracket pairs.
Initializes brackets with pairs of opening and closing brackets.
Creates two maps: counter to map closing brackets to their corresponding opening brackets and opening to track opening brackets.
Initializes an empty Stack to keep track of the opening brackets encountered.
Iterates through each character in the input string.
If the character is an opening bracket, it is pushed onto the stack.
If the character is a closing bracket, it checks if the stack is not empty and if the top of the stack matches the corresponding opening bracket. If so, it pops the opening bracket from the stack. Otherwise, it returns false.
After iterating through the entire string, it checks if the stack is empty. If so, it means all opening brackets had matching closing brackets, and the function returns true; otherwise, it returns false.
Subscribe to my Youtube channel
Subscribe to my youtube channel if you are on the lookout for more such awesome content in video format.
Claps Please!
If you found this article helpful I would appreciate some claps 👏👏👏👏, it motivates me to write more such useful articles in the future.
Subscribe to my Newsletter
If you like my content, then consider subscribing to my free newsletter, to get exclusive, educational, technical, interesting and career related content directly delivered to your inbox
Important Links
Thanks for reading the post, be sure to follow the links below for even more awesome content in the future.
twitter: https://twitter.com/dsysd_dev
youtube: https://www.youtube.com/@dsysd-dev
github: https://github.com/dsysd-dev
medium: https://medium.com/@dsysd-dev
email: dsysd.mail@gmail.com
linkedin: https://www.linkedin.com/in/dsysd-dev/
newsletter: https://dsysd.beehiiv.com/subscribe
gumroad: https://dsysd.gumroad.com/
Dev.to: https://dev.to/dsysd_dev/
Instagram: https://www.instagram.com/dsysd.dev/
Hashnode: https://dsysd-dev.hashnode.dev/
Top comments (0)