golang之栈实现

stack API为压栈、弹栈、栈是否为空、查看栈顶元素（peek）,查看栈中数据的数量、Flush(清空栈)

栈的实现底层数据结构可以使用数组也可以使用链表：
数组实现栈和链表实现的栈的插入、查询、拿取数据的复杂度都为1。

数组栈的代码

package stack

import "fmt"
/*
* 数组栈，每次插入数据，即压栈，都放入数组的最后一个元素，取的时候，从最后一个元素取，复杂度都是O(1).
* Author:sxy
*/
type Stack struct {
	data  []int
	count int // 这个栈的大小
	top   int // 这个栈的栈顶指针
}

func NewStack(cap int) *Stack {
	return &Stack{
		data:  make([]int, cap, cap),
		count: cap,
		top:   -1,
	}
}

func (s *Stack) Push(n int) bool {
	// 栈数据满了
	if s.top >= s.count {
		return false
	}
	s.top++
	s.data[s.top] = n
	return true
}

func (s *Stack) IsEmpty() bool {
	if s.top < 0 {
		return true
	}
	return false
}

func (s *Stack) Pop() int {
	if s.IsEmpty() {
		return 0
	}
	res := s.data[s.top]
	s.top--
	return res
}

func (s *Stack) Peek() int {
	if s.IsEmpty() {
		return 0
	}
	res := s.data[s.top]
	return res
}

func (s *Stack) Print() {
	if s.IsEmpty() {
		fmt.Println("stack is empty")
	} else {
		for i := s.top; i >= 0; i-- {
			fmt.Println(s.data[i])
		}
	}
}

func (s *Stack) Flush() {
	s.top = -1
}

链表栈的代码

package stack

import "fmt"
/*
* 链式栈，每次插入数据，即压栈，都放入链表的第一个元素，取的时候，从第一个元素取，复杂度都是O(1).
* Author:sxy
*/
type Node struct {
	next *Node
	val  int
}

type LinkedListStack struct {
	top *Node
}

func NewLinkedListStack() *LinkedListStack {
	return &LinkedListStack{top: nil}
}

func (lls *LinkedListStack) Push(val int) bool {
	if lls.IsEmpty() {
		lls.top = &Node{next: nil, val: val}
		return true
	}
	lls.top = &Node{next: lls.top, val: val}
	return true
}

func (lls *LinkedListStack) Pop() int {
	if lls.IsEmpty() {
		return 0
	}
	v := lls.top.val
	lls.top = lls.top.next
	return v
}

func (lls *LinkedListStack) Peek() int {
	if lls.IsEmpty() {
		return 0
	}
	return lls.top.val
}

func (lls *LinkedListStack) IsEmpty() bool {
	if lls.top == nil {
		return true
	}
	return false
}

func (lls *LinkedListStack) Flush() {
	lls.top = nil
}

func (lls *LinkedListStack) Print() {
	if lls.IsEmpty() {
		fmt.Println("empty stack")
	} else {
		cur := lls.top
		for nil != cur {
			fmt.Println(cur.val)
			cur = cur.next
		}
	}
}