欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

golang实现栈操作

程序员文章站 2024-03-19 22:10:46
...

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


相关标签: