It is now time to look at the implementation of a stack in Go. This will be illustrated in the stack.go source file. Once again, a linked list will be used for implementing the stack. As you know, you will need two functions: one function named Push() for putting things on the stack and another one named Pop() for removing things from the stack. Although it is not necessary, it is useful to keep the number of elements that you have on the stack on a separate variable in order to be able to tell whether you are dealing with an empty stack or not without having to access the linked list itself.
The source code of stack.go will be presented in four parts. The first part follows next:
package main import ( "fmt" ) type Node struct { Value int Next *Node } var size = 0 var stack = new(Node)
The second part of stack.go contains the implementation of the Push() function:
func Push(v int) bool { if stack == nil { stack = &Node{v, nil} size = 1 return true } temp := &Node{v, nil} temp.Next = stack stack = temp size++ return true }
If the stack is not empty, then you create a new node (temp), which is placed in front of the current stack. After that, this new node becomes the head of the stack. The current version of the Push() function always returns true, but if your stack does not have unlimited space, you might want to modify it and return false when you are about to exceed its capacity.
The third part contains the implementation of the Pop() function:
func Pop(t *Node) (int, bool) { if size == 0 { return 0, false } if size == 1 { size = 0 stack = nil return t.Value, true } stack = stack.Next size-- return t.Value, true }
The fourth code segment of stack.go is as follows:
func traverse(t *Node) { if size == 0 { fmt.Println("Empty Stack!") return } for t != nil { fmt.Printf("%d -> ", t.Value) t = t.Next } fmt.Println() }
As the stack is implemented using a linked list, it is traversed as such.
The last part of stack.go is shown in the following Go code:
func main() { stack = nil v, b := Pop(stack) if b { fmt.Print(v, " ") } else { fmt.Println("Pop() failed!") } Push(100) traverse(stack) Push(200) traverse(stack) for i := 0; i < 10; i++ { Push(i) } for i := 0; i < 15; i++ { v, b := Pop(stack) if b { fmt.Print(v, " ") } else { break } } fmt.Println() traverse(stack) }
As you just saw, the source code of stack.go is a little shorter than the Go code of queue.go, primarily because the idea behind a stack is simpler than the idea behind a queue.
Executing stack.go will generate the following type of output:
$ go run stack.go Pop() failed! 100 -> 200 -> 100 -> 9 8 7 6 5 4 3 2 1 0 200 100 Empty Stack!