数据结构--栈

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置叫表的末端，或者叫栈顶（top）。由于对栈中所有元素的操作都是在栈顶，所以栈有后进先出（LIFO）的特性。

图 1

栈的基本操作有：

元素入栈操作 push
元素出栈操作 pop
查看栈顶元素 top

入栈是指在栈顶插入元素，出栈是指删除栈顶元素。

栈的实现

通过链表实现

可以使用单链表来实现栈，链表的前端作为栈顶，通过在链表头插入元素来实现 push，删除表头元素来实现 pop，top 操作只是返回链表头部元素的指。

import (
    "container/list"
    "sync"
)
type Stack struct {
    sync.RWMutex
    l *list.List
}
func New() *Stack {
    s := &Stack{
        l: list.New(),
    }
    return s
}
func (s *Stack) Push(v interface{}) {
    s.Lock()
    defer s.Unlock()
    s.l.PushFront(v)
}
func (s *Stack) Pop() interface{} {
    s.Lock()
    defer s.Unlock()
    ele := s.l.Front()
    return s.l.Remove(ele)
}
func (s *Stack) Top() interface{} {
    s.RLock()
    defer s.RUnlock()
    return s.l.Front()
}

通过 slice 实现

使用 slice 实现栈比较简单，先声明一个初始容量比较大的 slice，空栈时栈顶 index(top) 可以设置为 -1，有新元素 x 入栈操作，可以将栈顶index(top) 的值加 1，然后设置 stack[top]=x；元素出栈操作，可以先返回 stack[top]，然后将栈顶 index(top) 的值减 1。

import (
    "sync"
)
type Stack struct {
    sync.RWMutex
    s   []interface{}
    top int
    c   int
}
func New(capacity int) *Stack {
    s := &Stack{
        s:   make([]interface{}, capacity),
        c:   capacity,
        top: -1,
    }
    return s
}
func (s *Stack) Push(v interface{}) {
    s.Lock()
    defer s.Unlock()
    if s.top+1 > s.c {
        panic("stack over flow")
    }
    s.top++
    s.s[s.top] = v
}
func (s *Stack) Pop() interface{} {
    s.Lock()
    defer s.Unlock()
    if s.top == -1 {
        panic("empty stack")
    }
    ele := s.s[s.top]
    s.top--
    return ele
}
func (s *Stack) Top() interface{} {
    s.RLock()
    defer s.RUnlock()
    if s.top == -1 {
        panic("empty stack")
    }
    return s.s[s.top]
}

总结

栈实现简单，效率很高，通常 push 和 pop 都是 O(1) 的操作。错误检测和线程安全方面的考虑可能会拖慢栈的执行效率，对空栈的 pop 和对满栈的 push 可能都会导致程序异常。在golang中实现栈还有一个问题是，golang目前没有支持泛型（generic）或者类型参数（type params），所以编写通用的数据结构只能使用 interface，这样带来的问题是，无法在数据结构的实现中来保证数据类型的安全，使用时需要多加注意。

参考资料

数据结构与算法分析