package main

import (
	"fmt"
	"strconv"
	"strings"
)

// 实现栈 (stack) 数据结构：
// 它的格子包含数据，比如整数 i、j、k 和 l 等等，格子从底部（索引 0）至顶部（索引 n）来索引。这个例子中假定 n = 3，那么一共有 4 个格子。
// 一个新栈中所有格子的值都是 0。
// 将一个新值放到栈的最顶部一个空（包括零）的格子中，这叫做 push。
// 获取栈的最顶部一个非空（非零）的格子的值，这叫做 pop。 现在可以理解为什么栈是一个后进先出 (LIFO) 的结构了吧。
// 为栈定义一个 Stack 类型，并为它定义 Push 和 Pop 方法，再为它定义 String() 方法（用于调试）输出栈的内容，比如：[0:i] [1:j] [2:k] [3:l]。
// 1）stack_arr.go：使用长度为 4 的 int 数组作为底层数据结构。
// 2） stack_struct.go：使用包含一个索引和一个 int 数组的结构体作为底层数据结构，索引表示第一个空闲的位置。
// 3）使用常量 LIMIT 代替上面表示元素个数的 4 重新实现上面的 1）和 2），使它们更具有一般性。

const LIM = 4

type Stack struct {
	ix  int // The first empty element index
	dat [LIM]int
}

func (s *Stack) Push(d int) bool {
	if s.ix >= LIM {
		return false
	}
	s.dat[s.ix] = d
	s.ix++
	return true
}

func (s *Stack) Pop() (d int) {
	if s.ix <= 0 {
		return
	}
	if s.dat[s.ix-1] != 0 {
		d, s.dat[s.ix-1] = s.dat[s.ix-1], 0
		s.ix--
	}
	return
}

func (s *Stack) String() string {
	str := ""
	for ix, v := range s.dat {
		str += "[" + strconv.Itoa(ix) + ":" + strconv.Itoa(v) + "] "
	}
	str = strings.TrimSpace(str)
	return str
}

func main() {
	s := new(Stack)
	s.Push(4)
	s.Push(8)
	s.Push(12)
	s.Push(20)
	fmt.Println(s)
	d := s.Pop()
	fmt.Println("After Pop(): ", d, " Stack is: ", s)
	d = s.Pop()
	fmt.Println("After Pop(): ", d, " Stack is: ", s)
	d = s.Pop()
	fmt.Println("After Pop(): ", d, " Stack is: ", s)
	d = s.Pop()
	fmt.Println("After Pop(): ", d, " Stack is: ", s)
	d = s.Pop()
	fmt.Println("After Pop(): ", d, " Stack is: ", s)
}