Stack based non-recursive Fibonacci - Go implementation

The following function computes a the last element in a Fibonacci sequence in Go language.

```
package main

import (
"fmt"
)

type Element struct {
Next *Element
Value interface{}
}
type Stack struct {
Top *Element
Count int
}

func (stack *Stack) Push(value interface{}) {
el := Element{
Value: value,
Next: stack.Top,
}
stack.Top = &el
stack.Count++
}
func (stack *Stack) Peek() (value interface{}) {
if stack.Top != nil {
value = stack.Top.Value
}
return
}
func (stack *Stack) Pop() (value interface{}) {
if stack.Top != nil {
value = stack.Top.Value
stack.Top = stack.Top.Next
stack.Count--
}
return
}
func (stack *Stack) Size() int {
return stack.Count
}

func Fibonacci(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}

//for n >= 2 the initial stack has the 0 and 1 values
stack := Stack{}
stack.Push(0)
stack.Push(1)

// loop from n to 2
for n > 1 {
//pop two top elements from stack
term1 := stack.Pop().(int)
term2 := stack.Pop().(int)

//push back the first popped element, this will become term2 on the next iteration
stack.Push(term1)

//push the sum of the two elements, this will be the Top element on the next iteration
stack.Push(term1 + term2)

//move to the next iteration
n--

}

//the top element in stack represents the last element in the Fibonacci sequence for a given n position
return stack.Pop().(int)
}
func FibonacciTest() {
fmt.Println("F0 -> 0", 0 == Fibonacci(0))
fmt.Println("F1 -> 1", 1 == Fibonacci(1))
fmt.Println("F2 -> 1", 1 == Fibonacci(2))
fmt.Println("F3 -> 2", 2 == Fibonacci(3))
fmt.Println("F4 -> 3", 3 == Fibonacci(4))
fmt.Println("F5 -> 5", 5 == Fibonacci(5))
fmt.Println("F6 -> 8", 8 == Fibonacci(6))
fmt.Println("F7 -> 13", 13 == Fibonacci(7))
fmt.

I'm not convinced that the mechanism of using a stack is a good one. Why did you choose that data structure? In Go, a slice would be a much more appropriate structure, and also probably a lot more memory efficient. What you are looking for is a 2-element queue, not a 2-member stack.

The need for you to pop() term1 and then push it back again, is an indication that the stack is the wrong structure.

Consider a much simpler Fibonacci method, that does essentially the same logic as your method, but .... simpler.

func Fibonacci(n int) int {
    // seed the sequence with the next 2 numbers in the sequence
    fib := []int{0, 1}

    // advance the future 2 sequences as necessary.
    for i := 0; i < n; i++ {
        current := fib[0]
        next := fib[1]
        // remove the first member
        fib = fib[1:]
        // add the next member
        fib = append(fib, current+next)
    }

    return fib[0]
}

This uses a Go slice as a queue, shifting the value from the front of the queue, and adding another value to the end of the queue.

A trick is computing the two values "ahead" instead of the two values "before" the "current" item. This allows you to have simpler logic for the first and second results (but at the expense of calculating a single value you will never use).

See this running in the playground

StackExchange Code Review Q#143510, answer score: 3