Stack

先进后出，先进队的数据最后才出来。在英文的意思里，stack 可以作为一叠的意思，这个排列是垂直的，你将一张纸放在另外一张纸上面，先放的纸肯定是最后才会被拿走，因为上面有一张纸挡住了它。

实现数组栈 ArrayStack

数组形式的下压栈，后进先出:

主要使用可变长数组来实现。

// 数组栈，后进先出
type ArrayStack struct {
array []string   // 底层切片
size  int        // 栈的元素数量
lock  sync.Mutex // 为了并发安全使用的锁
}

入栈

// 入栈
func (stack *ArrayStack) Push(v string) {
stack.lock.Lock()
defer stack.lock.Unlock()

    // 放入切片中，后进的元素放在数组最后面
    stack.array = append(stack.array, v)

    // 栈中元素数量+1
    stack.size = stack.size + 1
}
//将元素入栈，会先加锁实现并发安全。
//
//入栈时直接把元素放在数组的最后面，然后元素数量加 1。性能损耗主要花在切片追加元素上，
//切片如果容量不够会自动扩容，底层损耗的复杂度我们这里不计，所以时间复杂度为 O(1)。

出栈

func (stack *ArrayStack) Pop() string {
stack.lock.Lock()
defer stack.lock.Unlock()

    // 栈中元素已空
    if stack.size == 0 {
        panic("empty")
    }

    // 栈顶元素
    v := stack.array[stack.size-1]

    // 切片收缩，但可能占用空间越来越大
    //stack.array = stack.array[0 : stack.size-1]

    // 创建新的数组，空间占用不会越来越大，但可能移动元素次数过多
    newArray := make([]string, stack.size-1, stack.size-1)
    for i := 0; i < stack.size-1; i++ {
        newArray[i] = stack.array[i]
    }
    stack.array = newArray

    // 栈中元素数量-1
    stack.size = stack.size - 1
    return v
}

//元素出栈，会先加锁实现并发安全。
//
//如果栈大小为0，那么不允许出栈，否则从数组的最后面拿出元素。
//
//元素取出后:
//    1.如果切片偏移量向前移动 stack.array[0 : stack.size-1]，表明最后的元素已经不属于该数组了，
//    数组变相的缩容了。此时，切片被缩容的部分并不会被回收，仍然占用着空间，所以空间复杂度较高，
//    但操作的时间复杂度为：O(1)。
//    2.如果我们创建新的数组 newArray，然后把老数组的元素复制到新数组，就不会占用多余的空间，
//    但移动次数过多，时间复杂度为：O(n)。
//
//最后元素数量减一，并返回值。

获取栈顶元素

// 获取栈顶元素
func (stack *ArrayStack) Peek() string {
// 栈中元素已空
if stack.size == 0 {
panic("empty")
}

    // 栈顶元素值
    v := stack.array[stack.size-1]
    return v
}

//获取栈顶元素，但不出栈。和出栈一样，时间复杂度为：O(1)。

获取栈大小和判定是否为空

// 栈大小
func (stack *ArrayStack) Size() int {
return stack.size
}

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

一目了然，时间复杂度都是：O(1)。

实现链表栈 LinkStack

链表形式的下压栈，后进先出：

// 链表栈，后进先出
type LinkStack struct {
root *LinkNode  // 链表起点
size int        // 栈的元素数量
lock sync.Mutex // 为了并发安全使用的锁
}

// 链表节点
type LinkNode struct {
Next  *LinkNode
Value string
}

入栈

// 入栈
func (stack *LinkStack) Push(v string) {
stack.lock.Lock()
defer stack.lock.Unlock()

    // 如果栈顶为空，那么增加节点
    if stack.root == nil {
        stack.root = new(LinkNode)
        stack.root.Value = v
    } else {
        // 否则新元素插入链表的头部
        // 原来的链表
        preNode := stack.root

        // 新节点
        newNode := new(LinkNode)
        newNode.Value = v

        // 原来的链表链接到新元素后面
        newNode.Next = preNode

        // 将新节点放在头部
        stack.root = newNode
    }

    // 栈中元素数量+1
    stack.size = stack.size + 1
}

//将元素入栈，会先加锁实现并发安全。
//
//如果栈里面的底层链表为空，表明没有元素，那么新建节点并设置为链表起点：
//stack.root = new(LinkNode)。
//
//否则取出老的节点：preNode := stack.root，新建节点：newNode := new(LinkNode)，
//然后将原来的老节点链接在新节点后面： newNode.Next = preNode，
//最后将新节点设置为链表起点 stack.root = newNode。
//
//时间复杂度为：O(1)。

出栈

// 出栈
func (stack *LinkStack) Pop() string {
stack.lock.Lock()
defer stack.lock.Unlock()

    // 栈中元素已空
    if stack.size == 0 {
        panic("empty")
    }

    // 顶部元素要出栈
    topNode := stack.root
    v := topNode.Value

    // 将顶部元素的后继链接链上
    stack.root = topNode.Next

    // 栈中元素数量-1
    stack.size = stack.size - 1

    return v
}

//元素出栈。如果栈大小为0，那么不允许出栈。
//
//直接将链表的第一个节点 topNode := stack.root 的值取出，
//然后将表头设置为链表的下一个节点：stack.root = topNode.Next，
//相当于移除了链表的第一个节点。
//
//时间复杂度为：O(1)。

获取栈顶元素

// 获取栈顶元素
func (stack *LinkStack) Peek() string {
// 栈中元素已空
if stack.size == 0 {
panic("empty")
}

    // 顶部元素值
    v := stack.root.Value
    return v
}

获取栈顶元素，但不出栈。和出栈一样，时间复杂度为：O(1)。

获取栈大小和判定是否为空

// 栈大小
func (stack *LinkStack) Size() int {
return stack.size
}

// 栈是否为空
func (stack *LinkStack) IsEmpty() bool {
return stack.size == 0
}