golang 怎么设计一个栈

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶。
栈有时又叫LIFO(先进后出)表。 （推荐学习：go）
对栈的操作有Push(进栈)和Pop(出栈)，前者相当于插入，后者相当于删除最后插入的元素。
以下用双向链表和切片实现分别实现栈操作
//stack//用双向链表实现stacktype Element interface {}var header *entry  //链表表头var size int  //栈的长度type entry struct {    previous *entry    next     *entry    element  Element}func newEntry(prev,next *entry,e Element) *entry {    return  &entry{prev,next,e}}//初始化header  表头func NewStack() *entry {    header = newEntry(nil,nil,nil)    header.previous =header    header.next = header    return header}type Stack interface {    Push(e Element)    //向栈顶添加元素    Pop()   Element    //移除栈顶元素    Top()   Element   //获取栈顶元素（不删除）    Clear()  bool       //清空栈    Size()  int            //获取栈的元素个数    IsEmpty() bool   //判断栈是否是空栈}//向栈顶添加元素func (e *entry) Push(element Element)  {    addBefore(header,element)}//移除栈顶元素func (e *entry) Pop() Element {    if e.IsEmpty() {        fmt.Println("stack is empty!")        return nil    }    prevEntry := header.previous    prevEntry.previous.next = header    header.previous = prevEntry.previous    size--    return prevEntry.element}//获取栈顶元素（不删除）func (e *entry) Top() Element {    if e.IsEmpty() {        fmt.Println("stack is empty!")        return nil    }    return header.previous.element}//清空栈func (e *entry) Clear() bool {    if e.IsEmpty() {        fmt.Println("stack is empty!")        return false    }    entry := header.next    for entry != header {        nextEntry := entry.next        entry.next = nil        entry.previous = nil        entry.element = nil        entry = nextEntry    }    header.next = header    header.previous = header    size =0    return true}func (e *entry) Size() int  {    return size}func (e *entry) IsEmpty() bool {    if size == 0 {        return true    }    return false}//在entry节点之前添加func addBefore(e *entry,element Element) Element{    newEntry := newEntry(e.previous,e,element)    newEntry.previous.next = newEntry    newEntry.next.previous = newEntry    size++    return newEntry}//****************************************//****************************************//用切片实现Stacktype  sliceEntry struct{    element []Element}func NewSliceEntry() *sliceEntry {    return &sliceEntry{}}func (entry *sliceEntry)Push(e Element) {    entry.element = append(entry.element,e)}func  (entry *sliceEntry)Pop() Element {    size := entry.Size()    if size == 0 {        fmt.Println("stack is empty!")        return nil    }    lastElement := entry.element[size-1]    entry.element[size-1] = nil    entry.element  = entry.element[:size-1]    return lastElement}func  (entry *sliceEntry)Top() Element {    size := entry.Size()    if size == 0 {        fmt.Println("stack is empty!")        return nil    }    return entry.element[size-1]}func  (entry *sliceEntry)Clear() bool {    if entry.IsEmpty() {        fmt.Println("stack is empty!")        return false    }    for i :=0;i<entry.Size();i++ {        entry.element[i] = nil    }    entry.element = make([]Element,0)    return true}func  (entry *sliceEntry)Size() int {    return len(entry.element)}func  (entry *sliceEntry)IsEmpty() bool {    if len(entry.element) == 0 {        return true    }    return false}func main() {    test1()}//测试双向链表实现的Stackfunc test1() {    stack := NewStack()    for i := 0;i<50;i++ {        stack.Push(i)    }    fmt.Println(stack.Top())    fmt.Println(stack.Size())    fmt.Println(stack.Pop())    fmt.Println(stack.Top())    fmt.Println(stack.Clear())    fmt.Println(stack.IsEmpty())    for i := 0;i<50;i++ {        stack.Push(i)    }    fmt.Println(stack.Top())}//测试切片实现的Stackfunc test2() {    entry := NewSliceEntry()    for i:= 0;i<50;i++ {        entry.Push(i)    }    fmt.Println(entry.Size())    fmt.Println(entry.Top())    fmt.Println(entry.Pop())    fmt.Println(entry.Top(),entry.Size())    fmt.Println(entry.Clear())    for i:= 0;i<50;i++ {        entry.Push(i)    }    fmt.Println(entry.Size())}//两种方法性能比较func test3() {    t := time.Now()    sliceStack := NewSliceEntry()    for i:= 0;i<500000;i++ {        sliceStack.Push(i)    }    fmt.Println(time.Since(t))    t = time.Now()    stack := NewStack()    for i:=0;i<500000;i++ {        stack.Push(i)    }    fmt.Println(time.Since(t))}
更多相关文章

随机推荐
