数据结构与算法-栈

            栈就是先进后出、后进先出的数据结构，也是一种表。在实际的项目中我们也经常碰到这种栈的算法，比如java中方法的调用，利用栈的先进后出、后进先出的特性。为每个调用的线程创建一个方法栈，执行一个方法我们称为栈帧，方法的调用顺序也就是依次将栈帧压入方法栈。当方法执行完毕也就是一个弹出栈操作能够正确的返回到指定的地址。

           栈的操作一般有栈初始化、判断是否为空、判断栈的大小、入栈、出栈、遍历栈元素等。下面是基于golang实现的一个栈代码样例：

 

 

package stack

import (
	"fmt"
)

// 栈 golang 实现
type Element interface{}
type Stack struct {
	Element Element
	Next    *Stack
}

// 判断栈是否为空
func IsEmpty(s *Stack) bool {

	return s.Next == nil
}

// 创建一个栈
func CreateStack() *Stack {

	return &Stack{}
}

// 打印 栈信息
func DisposeStack(s *Stack) {

	if IsEmpty(s) {
		return
	}

	p := s

	for p.Next != nil {

		fmt.Println("result  = ", p.Element)
		p = p.Next
	}
}

// 置空栈
func MakeEmpty(s *Stack) {

	s.Next = nil
}

// 入栈
func Push(s *Stack, e Element) {

	p := &Stack{}
	p.Element = e
	p.Next = nil
	if IsEmpty(s) {
		s.Next = p
	} else {
		q := p.Next
		p.Next = q
		s.Next = p
	}
}

// 出栈操作
func Pop(s *Stack) Element {

	if IsEmpty(s) {
		return nil
	} else {

		p := s.Next
		if p.Next == nil {
			s.Next = nil
		} else {
			q := p.Next
			s.Next = q
		}

		return p.Element
	}
}

// 获取栈顶元素
func Top(s *Stack) Element {

	if IsEmpty(s) {
		return nil
	} else {
		return s.Next.Element
	}
}

// 获取大小
func Size(s *Stack) int {

	if IsEmpty(s) {
		return 0
	} else {

		var size int
		p := s
		for p.Next != nil {
			size++
			p = p.Next
		}
		return size
	}
}