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
}
}
}