DEV Community

Cover image for Implementing your own stack in golang
Dsysd Dev
Dsysd Dev

Posted on

Implementing your own stack in golang

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.

https://www.youtube.com/watch?v=uf24EYeJoaM

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()
}
Enter fullscreen mode Exit fullscreen mode

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.

https://www.youtube.com/@dsysd-dev

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

https://dsysd.beehiiv.com/subscribe

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)