栈的性质
- 只允许一段插入和删除数据
- 先进后出
- 栈可以用链表实现也可以用数组实现
操作时间复杂度
入栈和出栈时间复杂度都为Ｏ(1) (因为只涉及操作栈顶部的第一个元素）
涉及到可扩容的栈的时候，因为栈满了要扩容，数据迁移时间复杂度为Ｏ(n) 但是前ｎ次插入的时间复杂度都是Ｏ(1) 进行均摊后， 时间复杂度为O(2) = O(1) 所以不管是否扩容 时间复杂度都是O(1)
曾经（去年） 面试的时候有个面试官曾过我， 你知道栈吗？ 两个栈怎么组成一个先进先出的队列， 可是我太年轻那，bb半天也没有让人家满意。
栈的golang代码实现
type ArrayStack struct {
data []interface{}
top int
}
func NewArrayStack() *ArrayStack {
return &ArrayStack{
data: make([]interface{}, 0, 32),
top: -1,
}
}
func (this *ArrayStack) IsEmpty() bool {
return this.top < 0
}
func (this *ArrayStack) Push(v interface{}) {
this.top += 1
if this.top > len(this.data) -1 {
// 大于当前容量， 进行扩容
this.data = append(this.data, v)
}else {
this.data[this.top] = v
}
}
func (this *ArrayStack) Pop() interface{} {
if this.IsEmpty() {
return nil
}
v := this.data[this.top]
this.top -= 1
return v
}
func (this *ArrayStack) Top() interface{} {
if this.IsEmpty() {
return nil
}
return this.data[this.top]
}
func (this *ArrayStack) Print() {
if this.IsEmpty() {
fmt.Println("empty")
}else {
for i := this.top; i >= 0; i-- {
fmt.Println(this.data[i])
}
}
}
