棧的性質(zhì)
- 只允許一段插入和刪除數(shù)據(jù)
- 先進(jìn)后出
- 棧可以用鏈表實(shí)現(xiàn)也可以用數(shù)組實(shí)現(xiàn)
操作時(shí)間復(fù)雜度
入棧和出棧時(shí)間復(fù)雜度都為Ｏ(1) (因?yàn)橹簧婕安僮鳁ｍ敳康牡谝粋€(gè)元素）
涉及到可擴(kuò)容的棧的時(shí)候，因?yàn)闂M了要擴(kuò)容，數(shù)據(jù)遷移時(shí)間復(fù)雜度為Ｏ(n) 但是前ｎ次插入的時(shí)間復(fù)雜度都是Ｏ(1) 進(jìn)行均攤后殃饿， 時(shí)間復(fù)雜度為O(2) = O(1) 所以不管是否擴(kuò)容 時(shí)間復(fù)雜度都是O(1)
曾經(jīng)（去年） 面試的時(shí)候有個(gè)面試官曾過我， 你知道棧嗎？ 兩個(gè)棧怎么組成一個(gè)先進(jìn)先出的隊(duì)列旺坠， 可是我太年輕那，bb半天也沒有讓人家滿意扮超。
棧的golang代碼實(shí)現(xiàn)
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 {
// 大于當(dāng)前容量取刃， 進(jìn)行擴(kuò)容
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])
}
}
}
