下压栈，简称栈（Stack）是一种基于后进先出（Last In First Out, LIFO）策略的集合类型的。

链表实现

参考学习一个实现：stack.go，这个是 基于链表的一个实现，链表的使用可以达到：

• 所需空间和集合的大小成正比；
• 由于只操作表头，所需时间为集合大小无关。

//Stack 栈结构
type Stack struct {
	top  *Element
	size uint
}

// Element 元素
type Element struct {
	item interface{}
	next *Element
}

// Len Return the stack's length
func (s *Stack) Len() uint {
	return s.size
}

//IsEmpty 栈是否为空
func (s *Stack) IsEmpty() bool {
	return s.Len() == 0
}

// Push a new element onto the stack
func (s *Stack) Push(item interface{}) {
	s.top = &Element{item, s.top}
	s.size++
}

// Pop Remove the top element from the stack and return it's value
// If the stack is empty, return nil
func (s *Stack) Pop() (item interface{}) {
	if s.size > 0 {
		item, s.top = s.top.item, s.top.next
		s.size--
		return
	}
	return nil
}

数组实现

数组实现的一个麻烦在于无法预知栈在运行中所需的大小，根据Robert Sedgewick的一个策略，可以在先定义一个数组，当栈大小等于数组大小的时候，新建一个倍增数组，然后复制旧数组到新的数组，完成扩容。当栈大小是数组大小的四分之一时，将数组缩减为原来的一半来进行调整。这样的话，数组大小和栈大小之比小于一个常数。放在实现栈的情况下，栈的空间需求总是不超过栈大小乘以一个常数。下面是一个简单实现。

// ArrayStack 能够动态调整数组大小的栈实现
type ArrayStack struct {
	data []interface{}
	size int
}

// NewArrayStack 生成一个数组栈，初始大小为n
func NewArrayStack(n int) *ArrayStack {
	return &ArrayStack{
		data: make([]interface{}, 0, n),
		size: 0,
	}
}

// Len Return the stack's length
func (as *ArrayStack) Len() int {
	return as.size
}

//IsEmpty 栈是否为空
func (as *ArrayStack) IsEmpty() bool {
	return as.Len() == 0
}

// 重新调整数组大小
func (as *ArrayStack) resize(max int) {
	temp := make([]interface{}, as.size, max)
	copy(temp, as.data)
	as.data = temp
}

//Push 入栈
func (as *ArrayStack) Push(item interface{}) {
	if as.size == cap(as.data) {
		as.resize(as.size * 2)
	}
	as.size++
	as.data[as.size] = item
}

//Pop 出栈
func (as *ArrayStack) Pop() (item interface{}) {
	item = as.data[as.size-1]
	as.size--

	if (as.size > 0) && (as.size == cap(as.data)/4) {
		as.resize(as.size / 2)
	}

	return item
}