Print the next greater element

nextGreaterElement.go

package main

/*
 * Given an array, print the Next Greater Element (NGE) for every element.
 * The next greater element for an element x is the first greater element
 * on the right side of x in the array. Elements for which no greater
 * element exists, consider the next greater element as -1.
 */

import "fmt"

type Stack struct {
	stack []int
}

func NewStack() Stack {
	s := make([]int, 0)
	return Stack{
		stack: s,
	}
}

func (s *Stack) Size() int {
	return len(s.stack)
}

func (s *Stack) IsEmpty() bool {
	return s.Size() == 0
}

func (s *Stack) Top() int {
	return s.stack[s.Size()-1]
}

func (s *Stack) Push(value int) {
	s.stack = append(s.stack, value)
}

func (s *Stack) Pop() int {
	n := s.Size()
	item := s.stack[n-1]
	s.stack = s.stack[:n-1]
	return item
}

func main() {
	inputArray := []int{11, 13, 21, 3}
	printNextGreaterElement(inputArray)
}

// This is the actual solution. This solution doesn't print
// the next greater element in the same order as the inputArray
func printNextGreaterElement(arr []int) {
	s := NewStack()
	s.Push(arr[0])
	for i := 1; i < len(arr); i++ {
		if !s.IsEmpty() {
			elem := s.Pop()
			for elem < arr[i] {
				fmt.Printf("%d -> %d\n", elem, arr[i])
				if s.IsEmpty() {
					break
				}
				elem = s.Pop()
			}
			if elem > arr[i] {
				s.Push(elem)
			}
		}
		s.Push(arr[i])
	}
	fmt.Println(s)
	for !s.IsEmpty() {
		elem := s.Pop()
		fmt.Printf("%d -> %d\n", elem, -1)
	}
}