golang实现栈操作

xiaoxiao2021-02-28  13

栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶。 栈有时又叫LIFO(先进后出)表。 对栈的操作有Push(进栈)和Pop(出栈),前者相当于插入,后者相当于删除最后插入的元素。

以下用双向链表和切片实现分别实现栈操作

//stack //用双向链表实现stack type 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 } //**************************************** //**************************************** //用切片实现Stack type 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() } //测试双向链表实现的Stack func 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()) } //测试切片实现的Stack func 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)) }

转载请注明原文地址: https://www.6miu.com/read-1950281.html

最新回复(0)