golang实现栈操作

╰半夏微凉° 2022-05-31 00:45 314阅读 0赞

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶。  
栈有时又叫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))
    }