The Way to Go/

...

/

Solution Review: Implement Stack Data Structure

Solution Review: Implement Stack Data Structure

This lesson discusses the solution to the challenge given in the previous lesson.

We'll cover the following...
Press + to interact
package main
import (
	"fmt"
	"strconv"
)
const LIMIT = 4 // DONOT CHANGE IT!
type Stack struct {
	ix   int // first free position, so data[ix] == 0
	data [LIMIT]int
}
func (st *Stack) Push(n int) {
	if st.ix == LIMIT {	
		return // stack is full!
	}
	st.data[st.ix] = n
	st.ix++		// increment total no. of elements present
}
func (st *Stack) Pop() int {
	if st.ix >0{	// if stack not empty
		st.ix--		// decrease amount of elements present
		element := st.data[st.ix]
		st.data[st.ix] = 0
		return element
	}
	return -1	// if stack already empty
}
func (st Stack) String() string {
	str := ""
	for ix := 0; ix < st.ix; ix++ {
		str += "[" + strconv.Itoa(ix) + ":" + strconv.Itoa(st.data[ix]) + "]"
	}
	return str
}
func main() {
	st1 := new(Stack)
	fmt.Printf("%v\n", st1)
	st1.Push(3)	// function call to Push
	fmt.Printf("%v\n", st1)
	st1.Push(7) // function call to Push
	fmt.Printf("%v\n", st1)
	st1.Push(10) // function call to Push
	fmt.Printf("%v\n", st1)
	st1.Push(99) // function call to Push
	fmt.Printf("%v\n", st1)
	p := st1.Pop() // function call to Pop
	fmt.Printf("Popped %d\n", p)
	fmt.Printf("%v\n", st1)
	p = st1.Pop() // function call to Pop
	fmt.Printf("Popped %d\n", p)
	fmt.Printf("%v\n", st1)
	p = st1.Pop() // function call to Pop
	fmt.Printf("Popped %d\n", p)
	fmt.Printf("%v\n", st1)
	p = st1.Pop() // function call to Pop
	fmt.Printf("Popped %d\n", p)
	fmt.Printf("%v\n", st1)
}

In the above code, look at line 8. As per the requirement to generalize the implementation, we make a constant LIMIT and set its value to 4. This means that our stack can, at maximum hold four values. Now that we have defined the limit of the stack, we make a struct of type Stack at line 10. It has two fields. The first field is an integer field ix that keeps track of how many elements are currently in the stack. The next field is an array of integers data of capacity LIMIT. It keeps track of the elements that are present in a stack. When you declare a Stack type variable, ix will be 0 and the data array will hold four zeros, initially. Now, let’s see how the basic functionalities (push and pop) of the stack are implemented.

Look at the header of method Push at line 15: func (st *Stack) Push(n int). The header makes it clear that only the pointer to the stack object can call this method, and n is the element that is to be pushed in the stack. Now, the question is, would you push every time? No, you can’t push every single time because what if the stack is full (ix equals LIMIT) and you are trying to push an element at the top. In that case, it would give an error. Look at line 16, we start the implementation from this condition: if st.ix == LIMIT. If this condition is satisfied( ix of the stack st is equal to LIMIT), then control will ...